Let D be a deck of n cards. We have seen that there are ana-shuffles of D. A coding of the set of a-unshuffles was given in the proof of Theorem 3.9. We will now give a coding of the a-shuffles which corresponds to the coding of the a-unshuffles. Let S be the set of all n-tuples of integers, each between 0 and a−1. Let M=(m1,m2,…,mn) be any element of S. Let ni be the number of i's in M, for 0≤i≤a−1. Suppose that we start with the deck in increasing order (i.e., the cards are numbered from 1 to n). We label the first n0 cards with a 0, the next n1 cards with a 1, etc. Then the a-shuffle corresponding to M is the shuffle which results in the ordering in which the cards labelled i are placed in the positions in M containing the label i. The cards with the same label are placed in these positions in increasing order of their numbers. For example, if n=6 and a=3, let M=(1,0,2,2,0,2). Then n0=2, n1=1, and n2=3. So we label cards 1 and 2 with a 0, card 3 with a 1, and cards 4, 5, and 6 with a 2. Then cards 1 and 2 are placed in positions 2 and 5, card 3 is placed in position 1, and cards 4, 5, and 6 are placed in positions 3, 4, and 6, resulting in the ordering (3,1,4,5,2,6).
(a) Using this coding, show that the probability that in an a-shuffle, the first card (i.e., card number 1) moves to the ith position, is given by the following expression:
an(a−1)i−1an−i+(a−2)i−1(a−1)n−i+⋯+1i−12n−i.
(b) Give an accurate estimate for the probability that in three riffle shuffles of a 52-card deck, the first card ends up in one of the first 26 positions. Using a computer, accurately estimate the probability of the same event after seven riffle shuffles.