×

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