Title: Sharp phase transition in the repeated averaging process
Abstract: Consider a connected finite graph with a real number assigned to each vertex. At each step, an edge (u, v) is chosen uniformly at random, and the numbers at u and v are replaced by their average. This dynamics, known as the repeated averaging process, arises in many contexts, such as thermal equilibration, opinion dynamics, wealth exchange, and quantum circuits. All numbers eventually converge to the global average, and we study the speed of convergence in the L1 distance (which corresponds, for example, to the Gini index in wealth distributions). On random d-regular graphs, we show that this decay undergoes a sharp phase transition, with the L1 distance dropping abruptly to zero according to a Gaussian profile. Our techniques are robust, and we expect them to extend to more general dynamics on expander graphs. This is joint upcoming work with Dong Yao.
Reza Gheissari
Email