Is the following uniform SMB theorem for random walks on expander graphs true? For simplicity, I will state it for a finite group $G=\langle S \rangle$ and a uniform probability measure $\mu$ on the symmetric generating subset $S$ with cardinality $d$ and spectral gap at least $c>0$.

[Shannon-McMillan-Breiman Theorem] For any $\delta>0$, there is $N$ such that $n\geq N$ implies $$\mu^{*n}(\{ x \in G : -\log\mu^{*n}(x) \in [(1-\delta)H(n),(1+\delta)H(n)]\})>1-\delta,$$ where $H(n)=\int-\log\mu^{*n}(x)\,d\mu^{*n}(x)$ is the entropy of $\mu^{*n}$.

Of course, $\mu^{*n}$ converges to the uniform measure on $G$ and such $N$ exists for each $(G,\mu)$, but I want $N$ to be independent of $|G|$ (but may depend on $d$ and $c$). By Kaimanovich and Vershik's SMB theorem, the above estimate ought hold at some $n$, but I do not have a clue if it ought hold for all $n$ large enough. I'm particularly interested when $n=\Omega(\log|G|)$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.