Shuffling cards and stopping times.

*(English)*Zbl 0603.60006Let G be an arbitrary finite group and consider a probability distribution Q on G. For i.i.d. random elements \(\xi_ 1,\xi_ 2,..\). of G, define the random walk \((X_ k)_{k\geq 0}\) on G with step distribution Q as \(X_ 0=e\) (unit element of G), \(X_ n=\xi_ n,...,\xi_ 1\), \(n\geq 1\). Then the probability distribution of \(X_ n\) is \(Q^{n*}\), the n-fold convolution of Q, defined recursively as \(Q^{n*}(g)=\sum_{h\in G}Q(h)Q^{(n-1)*}(gh^{-1})\), \(n\geq 1\), with \(Q^{0*}(g)=1\) or 0 according as \(g=e\) or \(g\neq e\). It is well known that \(\lim_{n\to \infty}Q^{n*}(g)=U(g)=1/| G|\), \(g\in G\), unless Q is concentrated on some coset of some subgroup of G. A stopping time T of \((X_ k)_{k\geq 0}\) is called a strong uniform time for Q if, whatever \(k<\infty\), \(\Pr ob(T=k,X_ k=g)\) does not depend on \(g\in G\). The authors’ basic result is that for such a T one has
\[
d_ Q(k)\equiv \sup_{A\subset G}| Q^{k*}(A)-U(A)| \leq \Pr ob(T>k),\quad k\geq 0.
\]
This result is used to study repeated shuffling of an n-card deck, which can be viewed as a random walk on the permutation group \(S_ n\). Here the state of the deck is a permutation \(\pi \in S_ n\), meaning that the card originally at position i is now at position \(\pi\) (i). In the ”top in at random” shuffle the top card is removed and inserted into the deck at a random position. For this method of shuffling, using cycle notation for permutations \(\pi\), one has \(Q(i,i-1,...,1)=1/n\), \(Q(\pi)=0\) else, while the \(\xi_ n\) are randomly chosen cycles. By using an appropriate strong uniform time it is proved that (a) \(d_ Q(n \log n+cn)\leq e^{-c}\) for all \(c\geq 0\) and \(n\geq 2\); (b) \(d_ Q(n \log n- c_ nn)\to 1\) as \(n\to \infty\) for all \(c_ n\) such that \(\lim_{n\to \infty} c_ n=\infty.\)

Next, other constructions of strong uniform times are presented for a variety of random walks (including a random walk arising in random number generation, and a random walk arising in the ordinary riffle shuffle, the most commonly used method of shuffling cards). Finally, an explanation is given of a sense in which the method of strong uniform times always works and this is compared to two other techniques (Fourier analysis and coupling).

Next, other constructions of strong uniform times are presented for a variety of random walks (including a random walk arising in random number generation, and a random walk arising in the ordinary riffle shuffle, the most commonly used method of shuffling cards). Finally, an explanation is given of a sense in which the method of strong uniform times always works and this is compared to two other techniques (Fourier analysis and coupling).

Reviewer: M.Iosifescu