# Upper Bound Lemma implies the Ergodic Theorem for Random Walks on Groups?

Cross-Posted from Math Stackexchange.

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.

Note that the sum over the non-trivial irreducible representations is equal (up to a constant) to $\|\nu^{\star k}-\pi\|_{\ell_2}^2$ and so can detect convergence.

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.

Background: It is possible to prove an Upper Bound Lemma for finite quantum groups, however finding necessary and sufficient conditions for convergence to uniform (convergence to the Haar state) is an open problem. If the Upper Bound Lemma can yield the necessary and sufficient conditions for convergence in the classical case, perhaps something similar might be possible in the quantum case.

• I guess in some sense the upper bound lemma cannot show a necessary condition, by virtue of the very fact that it is an upper bound. But I don't see why you want to use it? It is trivial that irreducibility and aperiodicity are necessary. The hard part of the ergodic theorem is the sufficiency. – Nate Eldredge Oct 20 '17 at 13:08
• @NateEldredge It is an upper bound but equal to a two-norm and so can detect convergence (added). I have also added a little background as to why I am interested in this problem. – JP McCarthy Oct 20 '17 at 13:15

First suppose $\nu$ is concentrated on a proper subgroup $S$. Then consider the module $\mathbb C[G/S]$. It is not the trivial module and contains the trivial module with multiplicity $1$. Therefore, it contains a non-trivial irreducible constituent $\rho_a$. By Frobenius reciprocity, there is a vector $v$ in the representation space of $\rho_a$ fixed by $S$. Therefore, any convex combination of elements of $S$ fixes $v$. It follows since $\rho_a$ is unitary that $\widehat{\nu}(\rho_a)^k(\widehat{\nu}(\rho_a)^*)^k$ fixes $v$ and hence has an eigenvalue of $1$ and this will prevent your right hand side, which is the $\ell_2$-norm, from converging to $0$.
Suppose now that it is concentrated on a coset of a proper normal subgroup $N$. Let $\rho_a$ be a non-trivial irreducible unitary representation of $G/N$, which we view as a representation of $G$. If $m=[G:N]$, then for any $k>0$, $\widehat{\nu}(\rho_a)^{km}(\widehat{\nu}(\rho_a)^*)^{km}$ is the identity matrix and so its trace will not go to zero.