Cohen, Peri and Ta-Shma (STOC'21) considered the following question: Assume the vertices of an expander graph are labelled by $\pm 1$. What "test" functions $f : \{\pm 1\}^t \to \{\pm1 \}$ can or cannot distinguish $t$ independent samples from those obtained by a random walk? [CPTS'21] considered only balanced labelling, and proved that all symmetric functions are fooled by random walks on expanders with constant spectral gap. Furthermore, it was shown that functions computable by $\mathbf{AC}^0$ circuits are fooled by expanders with vanishing spectral expansion.

We continue the study of this question and, in particular, resolve all open problems raised by [CPTS'21]. First, we generalize the result to all labelling, not merely balanced. In doing so, we improve the known bound for symmetric functions and prove that the bound we obtain is optimal (up to a multiplicative constant). Furthermore, we prove that a random walk on expanders with constant spectral gap does not fool $\mathbf{AC}^0$. In fact, we prove that the bound obtained by [CPTS'21] for $\mathbf{AC}^0$ circuits is optimal up to a polynomial factor.