Cross posted on Mathoverflow

Ergodic Theorem A random walk on a finite group $G$ driven by a probability $\nu\in M_p(G)$ is ergodic if $\operatorname{supp}(\nu)$ is not concentrated on a proper subgroup $S\subset G$ nor the coset of a normal subgroup $N\triangleleft G$.

In this case the convolution powers of $\nu$ converge to the uniform distribution $\pi$ on $G$:

$$\nu^{\star k}\rightarrow \pi.$$

Where $\|\cdot \|=\frac12\|\cdot\|_{\ell_1}$, $$(\nu\star \nu)(g)=\sum_{t\in G}\nu(gt^{-1})\nu(t),$$ $d_\alpha$ is the dimension of a representation $\rho_\alpha:G\rightarrow \operatorname{GL}(V)$, $$\hat{\nu}(\rho)=\sum_{t\in G}\nu(t)\rho(t),$$ and $T^*$ denotes the conjugate transpose of $T$ in $\operatorname{GL}(V)$, Diaconis & Shahshahani proved the following:

Upper Bound Lemma Where $\operatorname{Irr}(G)\backslash \tau$ is the set of non-trivial unitary irreducible representations on $G$: $$\|\nu^{\star k}-\pi\|^2\leq \frac{1}{4}\sum_{\rho_\alpha\in \operatorname{Irr}(G)\backslash \tau}d_\alpha \operatorname{Tr}[\widehat{\nu}(\rho_\alpha)^k(\widehat{\nu}(\rho_\alpha)^*)^k].$$

The Upper Bound Lemma still holds if the random walk driven by $\nu$ is not ergodic.

Question: Can the Upper Bound Lemma be used to prove the Ergodic Theorem?

Can the Upper Bound Lemma show that for $\nu^{\star k}$ to converge to $\pi$ it is necessary that $\nu$ is not supported on a subgroup (irreducibility)? I suspect aperiodicity (not concentrated on the coset of normal subgroup) might be harder.

My own MSc thesis should be a good reference for some of this.


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.