Given any ordering [math]\sigma[/math] of [math]\{1, 2, \ldots, n\}[/math], we can define [math]\sigma^{-1}[/math], the inverse ordering of [math]\sigma[/math], to be the ordering in which the [math]i[/math]th element is the position occupied by [math]i[/math] in [math]\sigma[/math]. For example, if [math]\sigma = (1, 3, 5, 2, 4, 7, 6)[/math], then [math]\sigma^{-1} = (1, 4, 2, 5, 3, 7, 6)[/math]. (If one thinks of these orderings as permutations, then [math]\sigma^{-1}[/math] is the inverse of [math]\sigma[/math].)

A fall occurs between two positions in an ordering if the left position is occupied by a larger number than the right position. It will be convenient to say that every ordering has a fall after the last position. In the above example, [math]\sigma^{-1}[/math] has four falls. They occur after the second, fourth, sixth, and seventh positions. Prove that the number of rising sequences in an ordering [math]\sigma[/math] equals the number of falls in [math]\sigma^{-1}[/math].

Show that if we start with the identity ordering of [math]\{1, 2,\ldots, n\}[/math], then the probability that an [math]a[/math]-shuffle leads to an ordering with exactly [math]r[/math] rising sequences equals

for [math]1 \le r \le a[/math].

Let [math]D[/math] be a deck of [math]n[/math] cards. We have seen that there are [math]a^n[/math] [math]a[/math]-shuffles of [math]D[/math]. A coding of the set of [math]a[/math]-unshuffles was given in the proof of Theorem. We will now give a coding of the [math]a[/math]-shuffles which corresponds to the coding of the [math]a[/math]-unshuffles. Let [math]S[/math] be the set of all [math]n[/math]-tuples of integers, each between 0 and [math]a-1[/math]. Let [math]M = (m_1, m_2, \ldots, m_n)[/math] be any element of [math]S[/math]. Let [math]n_i[/math] be the number of [math]i[/math]'s in [math]M[/math], for [math]0 \le i \le a-1[/math]. Suppose that we start with the deck in increasing order (i.e., the cards are numbered from 1 to [math]n[/math]). We label the first [math]n_0[/math] cards with a 0, the next [math]n_1[/math] cards with a 1, etc. Then the [math]a[/math]-shuffle corresponding to [math]M[/math] is the shuffle which results in the ordering in which the cards labelled [math]i[/math] are placed in the positions in [math]M[/math] containing the label [math]i[/math]. The cards with the same label are placed in these positions in increasing order of their numbers. For example, if [math]n = 6[/math] and [math]a = 3[/math], let [math]M = (1, 0, 2, 2, 0, 2)[/math]. Then [math]n_0 = 2,\ n_1 = 1,[/math] and [math]n_2 = 3[/math]. 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 [math](3, 1, 4, 5, 2, 6)[/math].

• Using this coding, show that the probability that in an [math]a[/math]-shuffle, the first card (i.e., card number 1) moves to the [math]i[/math]th position, is given by the following expression:
  [[math]] {{(a-1)^{i-1}a^{n-i} + (a-2)^{i-1}(a-1)^{n-i} + \cdots + 1^{i-1}2^{n-i}}\over{a^n}}\ . [[/math]]
• 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.

Let [math]X[/math] denote a particular process that produces elements of [math]S_n[/math], and let [math]U[/math] denote the uniform process. Let the distribution functions of these processes be denoted by [math]f_X[/math] and [math]u[/math], respectively. Show that the variation distance

[math]\parallel f_X - u\parallel[/math] is equal to

Hint: Write the permutations in [math]S_n[/math] in decreasing order of the difference [math]f_X(\pi) - u(\pi)[/math].

Consider the process described in the text in which an [math]n[/math]-card deck is repeatedly labelled and 2-unshuffled, in the manner described in the proof of Theorem. (See Figure and Figure.) The process continues until the labels are all different. Show that the process never terminates until at least [math]\lceil \log_2(n) \rceil[/math] unshuffles have been done.