×

A phase transition for repeated averages. (English) Zbl 1485.60069

Summary: Let \(x_1,\dots,x_n\) be a fixed sequence of real numbers. At each stage, pick two indices \(I\) and \(J\) uniformly at random, and replace \(x_I,x_J\) by \((x_I+x_J)/2,(x_I+x_J)/2\). Clearly, all the coordinates converge to \((x_1+\cdots+x_n)/n\). We determine the rate of convergence, establishing a sharp “cutoff” transition answering a question of Jean Bourgain.

MSC:

60J05 Discrete-time Markov processes on general state spaces
60J20 Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.)
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Acemoğlu, D., Como, G., Fagnani, F. and Ozdaglar, A. (2013). Opinion fluctuations and disagreement in social networks. Math. Oper. Res. 38 1-27. · Zbl 1297.91130 · doi:10.1287/moor.1120.0570
[2] Aldous, D. and Lanoue, D. (2012). A lecture on the averaging process. Probab. Surv. 9 90-102. · Zbl 1245.60088 · doi:10.1214/11-PS184
[3] BEN-NAIM, E., KRAPIVSKY, P. L. and REDNER, S. (2003). Bifurcation and patterns in compromise processes. Phys. D 183 190-204. · Zbl 1058.91069 · doi:10.1016/S0167-2789(03)00171-4
[4] Berestycki, N. (2011). Emergence of giant cycles and slowdown transition in random transpositions and \(k\)-cycles. Electron. J. Probab. 16 152-173. · Zbl 1228.60079 · doi:10.1214/EJP.v16-850
[5] BERESTYCKI, N., LUBETZKY, E., PERES, Y. and SLY, A. (2018). Random walks on the random graph. Ann. Probab. 46 456-490. · Zbl 1393.60077 · doi:10.1214/17-AOP1189
[6] Berestycki, N., Schramm, O. and Zeitouni, O. (2011). Mixing times for random \(k\)-cycles and coalescence-fragmentation chains. Ann. Probab. 39 1815-1843. · Zbl 1245.60006 · doi:10.1214/10-AOP634
[7] CHATTERJEE, S. and SENETA, E. (1977). Towards consensus: Some convergence theorems on repeated averaging. J. Appl. Probab. 14 89-97. · Zbl 0381.60056 · doi:10.2307/3213262
[8] DIACONIS, P. (1977). Examples for the theory of infinite iteration of summability methods. Canad. J. Math. 29 489-497. · Zbl 0363.40005 · doi:10.4153/CJM-1977-053-1
[9] DIACONIS, P. and SALOFF-COSTE, L. (1993). Comparison techniques for random walk on finite groups. Ann. Probab. 21 2131-2156. · Zbl 0790.60011
[10] DIACONIS, P. and SALOFF-COSTE, L. (2014). Convolution powers of complex functions on \[\mathbb{Z} \]. Math. Nachr. 287 1106-1130. · Zbl 1304.42018 · doi:10.1002/mana.201200163
[11] Diaconis, P. and Shahshahani, M. (1981). Generating a random permutation with random transpositions. Z. Wahrsch. Verw. Gebiete 57 159-179. · Zbl 0485.60006 · doi:10.1007/BF00535487
[12] FELLER, W. (1968). An Introduction to Probability Theory and Its Applications. Vol. I, 3rd ed. Wiley, New York. · Zbl 0155.23101
[13] HÄGGSTRÖM, O. (2012). A pairwise averaging procedure with application to consensus formation in the Deffuant model. Acta Appl. Math. 119 185-201. · Zbl 1273.91408 · doi:10.1007/s10440-011-9668-9
[14] HARDY, G. H. (1949). Divergent Series. Clarendon Press, Oxford. · Zbl 0032.05801
[15] HÖGNÄS, G. and MUKHERJEA, A. (2011). Probability Measures on Semigroups, 2nd ed. Probability and Its Applications (New York). Springer, New York. · Zbl 1213.60007 · doi:10.1007/978-0-387-77548-7
[16] HOOVER, E. M. (1936). The measurement of industrial localization. Rev. Econ. Stat. 18 162-171.
[17] LANCHIER, N. (2012). The critical value of the Deffuant model equals one half. ALEA Lat. Am. J. Probab. Math. Stat. 9 383-402. · Zbl 1277.60178
[18] LUBETZKY, E. and SLY, A. (2010). Cutoff phenomena for random walks on random regular graphs. Duke Math. J. 153 475-510. · Zbl 1202.60012 · doi:10.1215/00127094-2010-029
[19] Marshall, A. W., Olkin, I. and Arnold, B. C. (2011). Inequalities: Theory of Majorization and Its Applications, 2nd ed. Springer Series in Statistics. Springer, New York. · Zbl 1219.26003 · doi:10.1007/978-0-387-68276-1
[20] OLSHEVSKY, A. and TSITSIKLIS, J. N. (2009). Convergence speed in distributed consensus and averaging. SIAM J. Control Optim. 48 33-55. · Zbl 1182.93008 · doi:10.1137/060678324
[21] PILLAI, N. S. and SMITH, A. (2017). Kac’s walk on \(n\)-sphere mixes in \[n\log n\] steps. Ann. Appl. Probab. 27 631-650. · Zbl 1364.60056 · doi:10.1214/16-AAP1214
[22] SALOFF-COSTE, L. and ZÚÑIGA, J. (2008). Refined estimates for some basic random walks on the symmetric and alternating groups. ALEA Lat. Am. J. Probab. Math. Stat. 4 359-392. · Zbl 1171.60008
[23] Schramm, O. (2005). Compositions of random transpositions. Israel J. Math. 147 221-243. · Zbl 1130.60302 · doi:10.1007/BF02785366
[24] SCHUTZ, (1951). On the measurement of income inequality. Am. Econ. Rev. 41 107-122.
[25] SHAH, D. (2008). Gossip algorithms. Found. Trends Netw. 3 1-125. · Zbl 1185.68072
[26] SMITH, A. (2014). A Gibbs sampler on the \(n\)-simplex. Ann. Appl. Probab. 24 114-130. · Zbl 1293.60072 · doi:10.1214/12-AAP916
[27] TEYSSIER, L. (2020). Limit profile for random transpositions. Ann. Probab. 48 2323-2343 · Zbl 1468.60091 · doi:10.1214/20-AOP1424
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.