A counterexample to a mixing-time conjecture for repeated averages on graphs

Nikash Gupta

In the authors' words

The repeated averages process is a stochastic averaging process on graphs whose mixing time is known for several structured families, but no general sharp expression is known for all connected graphs. It was conjectured that the $L^{2} \to L^{1}$ mixing time is of order $∣ E ∣ lo g n / λ_{2}$ . We disprove this conjecture using the graph $G_{n}$ obtained by attaching one leaf to the complete graph $K_{n}$ . We prove that $λ_{2} (G_{n}) = 1$ and that \[ t_{\varepsilon,2\to1}(G_n)=\Theta_{\varepsilon}(\gamma(G_n))=\Theta_{\varepsilon}(n^2), \] with no additional $lo g n$ factor. The example has a strongly localized Fiedler eigenvector: most of its squared $L^{2}$ mass lies on the leaf, while the balancing mass is spread across the clique.

Main resultThe abstract does not state a limitation.

A counterexample to a mixing-time conjecture for repeated averages on graphs

In the authors' words

More on Probability that day

SpaceDiffusion: Over-the-Orbit Diffusion for Space Generate-and-Forward Communications

A Probabilistic Modeling Framework for Transient Debris Outcomes in Low Lunar Orbits

Total Variation Distance between Product Distributions: an Analytic Proxy

The joint exit time and exit location law of a planar Ornstein-Uhlenbeck process on annular sectors and principal axis rectangles

Sharp High-Entropy Bounds for Sums of Independent Discrete Random Variables