*Cross-Posted from [Math Stackexchange](https://math.stackexchange.com/questions/2464439/upper-bound-lemma-implies-the-ergodic-theorem-for-random-walks-on-groups).*



> 
> **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](https://arxiv.org/abs/1504.05387) 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 (Edit: this is now settled — [The ergodic theorem for random walks on finite quantum groups](https://www.tandfonline.com/doi/abs/10.1080/00927872.2021.1908551?journalCode=lagb20)). 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.



Upper bound lemma implies the ergodic theorem for random walks on groups?
Here is a proof of necessity. 


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.


I’m not sure if this is what you want.


