A phase transition for repeated averages
Sourav Chatterjee, Persi Diaconis, Allan Sly, Lingfu Zhang
Abstract
Let x1,…,xn be a fixed sequence of real numbers. At each stage, pick two indices I and J uniformly at random, and replace xI, xJ by (xI+xJ)/2, (xI+xJ)/2. Clearly, all the coordinates converge to (x1+⋯+xn)/n. We determine the rate of convergence, establishing a sharp “cutoff” transition answering a question of Jean Bourgain.
Topics & Concepts
MathematicsCutoffSequence (biology)CombinatoricsConvergence (economics)Phase transitionRate of convergenceDiscrete mathematicsElectrical engineeringBiologyGeneticsEngineeringEconomicsEconomic growthChannel (broadcasting)PhysicsQuantum mechanicsMathematical Dynamics and FractalsStochastic processes and statistical mechanicsComplex Systems and Time Series Analysis