2022/12/15 by Louis Golowich, Golowich, Louis · 3 citations
Mathematics · #Advanced Combinatorial Mathematics #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Markov Chains and Monte Carlo Methods #Probability (math.PR) #Random Matrices and Applications
paper · pdf · doi:10.48550/arxiv.2212.08134
openalex publication_date 2022/12/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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(λ/t1/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(λ/t1/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.