A local central limit theorem for random walks on expander graphs

Rafael Chiclana, Yuval Peres

Published 2022-12-02Version 1

On a regular graph $G=(V,E)$, consider a function $\operatorname{val} \colon V \longrightarrow \{0,1\}$ that labels the vertices of $G$, and let $(X_i)$ be the simple random walk on $G$ started from a vertex chosen uniformly at random. In this work, we show that the Hamming weight of the sequence of bits $(\operatorname{val}(X_i))$ satisfies a local central limit theorem when the graph $G$ is expander. As a consequence, we study the pseudorandomness of random walks on expander graphs against test computed by symmetric functions $f\colon \{0,1\}^t \longrightarrow \{0,1\}$. We also show that the Hamming weight of $(\operatorname{val}(X_i))$ has the same asymptotic behavior as the Hamming weight of the sticky random walk.