A Phase Transition For Repeated K-Averages

Abstract

Let $x_1,\dots ,x_n$ be a fixed sequence of real numbers. At each stage, pick $k$ integers $\{I_i{\}}_{1\le i\le k}$ uniformly at random without replacement and then for each $i\in \{1,2,\dots ,k\}$ replace $x_{I_i}$ by $(x_{I_1}+x_{I_2}+\cdots +x_{I_k})/k$. It is easy to observe that all the co-ordinates converge to $(x_1+\cdots +x_n)/n$. In this article, we extend the result of \cite{chatterjee2019note} by establishing order of decay of the expected $L^2$ distance. Furthermore, we establish the mixing time to be in between $\frac{n}{k\log k}\log n$ and $\frac{n}{k-1}\log n$.

2 Pages