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


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.


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.

  • $\begingroup$ By concentrated on $gH$ I assume it means that $Q$ vanishes outside $gH$? $\endgroup$ – Fimpellizieri May 11 '18 at 18:57
  • $\begingroup$ Yes. I have edited to make that clear. $\endgroup$ – caffeinemachine May 12 '18 at 3:07
  • 1
    $\begingroup$ 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. $\endgroup$ – Sangchul Lee May 14 '18 at 9:14
  • 2
    $\begingroup$ 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. $\endgroup$ – user120527 May 17 '18 at 16:33
  • 1
    $\begingroup$ 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. $\endgroup$ – user120527 May 17 '18 at 16:54

The comprehensive statement is:

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$.

Proof here (Theorem 1.3.2).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.