随机算法 (Fall 2011)/Card Shuffling

Riffle Shuffle

The following is the Gilbert-Shannon-Reeds model of riffle shuffle introduced by Gilbert and Shannon in 1955 and independently by Reeds in 1985.

Riffle Shuffle (Gilbert-Shannon 1955; Reeds 1985)

Given a deck of [math]\displaystyle{ n }[/math] cards, at each round, do as follows. Split the original deck into two decks according to the binomial distribution [math]\displaystyle{ \mathrm{Bin}(n,1/2) }[/math]. Cut off the first [math]\displaystyle{ k }[/math] cards with probability [math]\displaystyle{ \frac{{n\choose k}}{2^n} }[/math], put into the left deck, and put the rest [math]\displaystyle{ n-k }[/math] cards into the right deck. Drop cards in sequence, where the next card comes from one of the two decks with probability proportional to the size of the deck at that time. Suppose at a step there are [math]\displaystyle{ L }[/math] cards in the left deck and [math]\displaystyle{ R }[/math] cards in the right deck. A card is dropped from left with probability [math]\displaystyle{ \frac{L}{L+R} }[/math], and from right otherwise.

The second step actually samples a uniform interleaving of left and right deck. The magician and mathematician Diaconis in 1988 found evidence showing that this mathematical model reasonably approximate the riffle shuffling acted by human.

The above model is equivalent to the following model of inverse riffle shuffle.

Inverse Riffle Shuffle

Label each card with a bit from [math]\displaystyle{ \{0,1\} }[/math] uniformly and independently at random. Place all cards labeled with 0 above all cards labeled with 1, keeping the cards with the same label in the same the relative order as before.

The process of inverse riffle shuffle is depicted as follows.

For each card, the random bits used for labeling the card compose a binary code [math]\displaystyle{ x }[/math], with the [math]\displaystyle{ t }[/math]-th bit (from lower to higher radix) [math]\displaystyle{ x_t }[/math] being the random bit chosen in round [math]\displaystyle{ t }[/math] to label the card.

Lemma

After every round of the inverse riffle shuffle, the cards are sorted in non-decreasing order of their corresponding binary codes.

Proof. By induction. After the first round, all [math]\displaystyle{ 0 }[/math] are above all [math]\displaystyle{ 1 }[/math]s. Assume that the hypothesis is true for the first [math]\displaystyle{ t-1 }[/math] rounds. After the [math]\displaystyle{ t }[/math]-th round, all cards with the highest coordinate [math]\displaystyle{ x_t=0 }[/math] are above all cards with [math]\displaystyle{ x_t=1 }[/math], and by the definition of inverse riffle shuffle, cards with the same highest bit [math]\displaystyle{ x_t }[/math] are kept in the same relative order as they are after the [math]\displaystyle{ (t-1) }[/math]-th round of the shuffling, which due to the hypothesis, means that the cards with the same highest bit [math]\displaystyle{ x_t }[/math] are sorted in the non-decreasing order of [math]\displaystyle{ x_{t-1}x_{t-2}\cdots x_1 }[/math]. By the definition of binary representation, all cards are sorted. [math]\displaystyle{ \square }[/math]

Rapid Mixing of Riffle Shuffle by Coupling

Theorem

The mixing time of inverse riffle shuffle of a deck of [math]\displaystyle{ n }[/math] cards is [math]\displaystyle{ \tau_{\mathrm{mix}}=O(\log n) }[/math].

Consider two instance of shuffling, started with two decks, each in an arbitrary order. We couple the two shuffling processes by coupling their random choices of labelings:

• In each round, we label the same cards (same content, not the same order) in the two decks with the same random bit.

Formally, for each [math]\displaystyle{ i\in[n] }[/math], we uniformly and independently choose a random [math]\displaystyle{ b_i\in\{0,1\} }[/math] as the label of the card [math]\displaystyle{ i }[/math] in each of the two decks in that round. It is easy to see that, each of the two shuffling processes viewed individually follows exactly the rules of inverse riffle shuffle.

Lemma

With the above coupling rule, started with arbitrary two decks of cards, the two decks are the same once all cards in the first (or the second) deck have distinct labels.

Proof. By the definition of the coupling rule, any two identical cards in the two decks always have the same label, since in every round they choose the same random bit. And we have shown that after each round, the labels are sorted in non-decreasing order. Thus, we can conclude: after each round, the sequences of the labels of the two decks are identical (and sorted in non-decreasing order). Therefore, when all cards in the first deck have distinct labels, the second deck have the same set of distinct labels, and the cards are sorted increasingly in their labels in the respective decks. Since any two identical cards have the same labels, the cards in the two decks must be in the same order. [math]\displaystyle{ \square }[/math]

We denote by [math]\displaystyle{ T }[/math] the random variable representing the time that in an inverse riffle shuffle, all cards in the deck have distinct labels. Due to the coupling lemma for Markov chains,

[math]\displaystyle{ \Delta(t)\le\Pr[T\ge t] }[/math].

This bound can be deduced from the birthday problem. After [math]\displaystyle{ t }[/math] round, each of the [math]\displaystyle{ n }[/math] cards is randomly assigned one of the [math]\displaystyle{ 2^t }[/math] possible labels. We know that for some [math]\displaystyle{ 2^t=O(n^2) }[/math], i.e. [math]\displaystyle{ t=2\log n+O(1) }[/math], the probability that no two cards have the same label is [math]\displaystyle{ \gt 1-1/2\mathrm{e} }[/math], i.e. [math]\displaystyle{ \Delta(t)\lt 1/2\mathrm{e} }[/math], thus

[math]\displaystyle{ \tau_{\mathrm{mix}}\le 2\log n+O(1) }[/math].

Note that the state space is the set of all permutations, which is of size [math]\displaystyle{ n! }[/math], whose logarithm is still as large as [math]\displaystyle{ \log (n!)=O(n\ln n) }[/math] due to Stirling's approximation. Thus the riffle shuffle is mixing extremely fast.

This estimation of mixing time is fairly tight. For the case that [math]\displaystyle{ n=52 }[/math], the real mixing rate is as follows.

[math]\displaystyle{ t }[/math]	1	2	3	4	5	6	7	8	9
[math]\displaystyle{ \Delta(t) }[/math]	1.000	1.000	1.000	1.000	0.924	0.614	0.334	0.167	0.003