A phase transition for repeated averages

arXiv1911.02756MaRDI QIDQ6328706FDOQ6328706

Authors: Sourav Chatterjee, Persi Diaconis, Allan Sly, Lingfu Zhang 

Publication date: 6 November 2019

Abstract: Let $x_1,ldots,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.

Mathematics Subject Classification ID

Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.) (60J20) Discrete-time Markov processes on general state spaces (60J05)

This page was built for publication: A phase transition for repeated averages

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6328706)