Trailing the dovetail shuffle to its lair. (English) Zbl 0757.60003

Probability theory started with analyses of gambling problems and then entered into pure mathematical problems and different applications. This paper concerns shufflings of cards, \(n\) in number, mainly according to a Gilbert-Shannon-Reeds-model — the (GSE)-model. The shuffling produces rather complicated permutations \(\pi\) of the symmetric group \(S_ n\) of \(n\) variables and these permutations and their different classes can be represented in different ways. Here a permutation is classified according to its number of its descents, \(\pi(i)<\pi(i+1)\), and its number of rising sequences. One theorem states: If \(n\) cards are shuffled \(m\) times, then the probability for the desk in arrangement \(\pi\) with \(r\) rising sequences is equal to \(B(m,n,r)/2^ m\), where \(B(m,n,r)\) is the binomial coefficient \((2^ m+n-r)\) over \(n\). For the \((G,S,E)\)-model the probability distribution \(Q\) for \(m\) shufflings of \(n\) cards is approximated by the uniform distribution \(U\), and the total variation of the difference is given in the form \[ \max_{A\text{ in } S^ n}| Q^{(m)}(A)-U(A)|=1-G(-2^{-\varphi}/4\sqrt 3)+O(1/n^{1/4}) \] for \(m=(3/2)\log_ 2 n+\varphi\) with the normalized Gaussian distribution function \(G\). The variation distance tends to 1 for small \(\varphi\) and to 0 for large \(\varphi\). The shuffling has been given a relation to an algebraic structure namely to a commutative, semisimple algebra of dimension \(n\).


60C05 Combinatorial probability
60B05 Probability measures on topological spaces
20B30 Symmetric groups
60F99 Limit theorems in probability theory
Full Text: DOI

Online Encyclopedia of Integer Sequences:

Multiplicative order of 2 mod 2n+1.