# Convergence to Uniform Distribution of a Random Walk on a Finite Group

I am reading the paper Shuffling Cards and Stopping Times by P. Diaconis and D. Aldous (American Math. Monthly, 1986).

# Context.

Let $G$ be a finite group and $Q$ be a probability distribution on $G$. We get a random walk on $G$ defined as follows: the probability of going from $x\in G$ to $gx\in G$ in one step is $Q(g)$. The $k$-fold convolution of $Q$, written $Q^{k^*}$, is a probability distribution on $G$ defined as follows: $Q^{k^*}(g)$ is the probability of landing at $g$ at the $k$-th step if we start at $e$ (identity) at the zeroth step.

At the bottom of the second page of the paper (near equation 2.2), one reads:

A fundamental result is that repeated convolutions converge to the uniform distribution $U$: $$Q^{k^*}(g)\to U(g) \text{ as } k\to \infty$$ unless $Q$ is concentrated on some coset of some subgroup.

(By "$Q$ is concentrated on $X$ we mean $Q$ vanishes outside $X$").

I am trying to see why the above is true. I know the following result:

If $\Sigma$ is the support of $Q$, that is, $\Sigma=\{x\in G:\ Q(x)>0\}$, then
$\bullet$ The chain driven by $Q$ is irreducible if and only if $\Sigma$ generates $G$.
$\bullet$ Assuming $\Sigma$ generates $G$, the random walk driven by $Q$ is aperiodic if and only if $\Sigma$ is not contained in a coset of a proper normal subgroup.

So if $Q$ is not concentrated in some coset of some proper subgroup, then the chain driven by $Q$ is ergodic, and thus we have a unique stationary distribution. It's easy to check that the uniform distribution is stationary. So the statement given in the aforementioned paper is proven in this direction.

# Question.

I am unable to do the other direction.

That is, if $Q$ is assumed to be concentrated on some coset of some proper (the authors didn't put proper in their writing) subgroup of $G$, then the $k$-fold convolution does not converge to $G$.

Further, the authors mention that Poincare has given a proof using Fourier analysis (Calcul Probabilites, Gauthier-Villars, Paris, 1912). I would really like to learn this proof, but I do not know French. If you know this proof, or any Fourier analytical proof, then I am very grateful if you cna share that.

• By concentrated on $gH$ I assume it means that $Q$ vanishes outside $gH$? – Fimpellizieri May 11 '18 at 18:57
• Yes. I have edited to make that clear. – caffeinemachine May 12 '18 at 3:07
• In $G = S_3$, the uniform distribution $Q$ over the coset $(1~3)\{(),(1~2)\}=\{(1~3),(1~2~3)\}$ satisfies $Q^{\star k}(g) \to \frac{1}{6}$. So I guess that the statement only deals with a sufficient condition. – Sangchul Lee May 14 '18 at 9:14
• If $Q$ is concentrated on some coset of a normal subgroup $H$ of $G$, then at every step, the induced random walk on the quotient $G/H$ is a dirac mass so cannot converge to uniform measure. So it cannot be uniformly distributed "upward", meaning on $G$ itself. – user120527 May 17 '18 at 16:33
• I had a look at Poincare's book, and basically he considers the transition matrix on $\mathbb{R}[G]$ and shows that $1$ is a simple eigenvalue and that others have modulus $<1$ provided the RW is not concentrated on a coset. I did not see any Fourier analysis, it seems to me it's the classical approach. – user120527 May 17 '18 at 16:54

Let $$G$$ be a finite group and $$\nu \in M_p(G)$$ with support $$\Sigma$$. The convolution powers $$\nu^{\star k}$$ converge to the uniform distribution if and only
• if $$\Sigma \not\subset K$$ for any proper subgroup $$K$$ of $$G$$, and
• $$\Sigma\not\subset Hg$$ for any coset of any proper normal subgroup $$H \rhd G$$.