Sharp Bounds for Dynamic Averaging on Cycles

We study a dynamic averaging process on the cycle \(C_n\).

At each discrete time, an edge is chosen uniformly at random, one unit of load is introduced, and the two endpoint loads are replaced by their common average after the new unit has been added.

Starting from the zero configuration, we prove that the expected gap between the largest and smallest loads is \(O(\sqrt n)\), uniformly in time.

Building on the lower-bound argument of Alistarh, Nadiradze, and Sabour for the expected square of the gap, we further show that the expected gap is \(\Omega(\sqrt n)\) in the long run.

This confirms their conjecture that the expected gap is of order \(\sqrt n\).