6
$\begingroup$

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.

$\endgroup$

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.