论文标题
一个新的浆果 - 埃森定理用于扩展器步行
A New Berry-Esseen Theorem for Expander Walks
论文作者
论文摘要
我们证明，$ t $ boolean可值的随机随机变量的总和在常规扩张器上随机步行采样，以总变化距离收敛到离散的正态分布，以$ o（λ/t^{1/t^{1/2-o（1）}）$的速率，其中$λ$是第二大的eigenvalue eigenvalue eigenvalue of the Oblotal Walkrix的绝对价值。据我们所知，在Markov链中已知的浆果 - 埃斯汀边界中，我们的结果是第一个在总变化距离中显示收敛的结果，并且也是第一个对膨胀$λ$的线性依赖性的依赖。相比之下，先前的马尔可夫链浆果 - 贝里（Berry-Esseen）边界显示在较弱的指标（例如kolmogorov距离）中的$ o（1/\ sqrt {t}）$。 我们的结果还改善了伪随身文献中的先前工作，这表明当将近似分布视为二项式分布时，总变化距离为$ O（λ）$。我们通过将二项式分布概括为任意差异的离散正态来实现更快的$ o（λ/t^{1/2-o（1）}）$收敛率。我们使用适当的2态马尔可夫链上的随机步行专门构建离散的正态。因此，我们的约束可以被视为一种规律性的引理，将任意扩张器的研究降低到一小部分特别简单的扩张器。
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/\sqrt{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.
