# zbMATH — the first resource for mathematics

Shuffling cards and stopping times. (English) Zbl 0603.60006
Let 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).
Reviewer: M.Iosifescu

##### MSC:
 60B15 Probability measures on groups or semigroups, Fourier transforms, factorization 60G40 Stopping times; optimal stopping problems; gambling theory 60G50 Sums of independent random variables; random walks
##### Keywords:
random shuffle; stopping time; shuffling
Full Text: