A New Berry-Esseen Theorem for Expander Walks

We prove that the sum of t boolean-valued random variables sampled by a random walk on a regular expander converges in total variation distance to a discrete normal distribution at a rate of O(λ/t 1/2-o(1) ), where λ is the second largest eigenvalue of the random walk matrix in absolute value. To the best of our knowledge, among known Berry-Esseen bounds for Markov chains, our result is the first to show convergence in total variation distance, and is also the first to incorporate a linear dependence on expansion λ. In contrast, prior Markov chain Berry-Esseen bounds showed a convergence rate of O(1/ √ t) in weaker metrics such as Kolmogorov distance.

Our result also improves upon prior work in the pseudorandomness literature, which showed that the total variation distance is O(λ) when the approximating distribution is taken to be a binomial distribution. We achieve the faster O(λ/t 1/2-o(1) ) convergence rate by generalizing the binomial distribution to discrete normals of arbitrary variance. We specifically construct discrete normals using a random walk on an appropriate 2-state Markov chain. Our bound can therefore be viewed as a regularity lemma that reduces the study of arbitrary expanders to a small class of particularly simple expanders.