How is a “riffle shuffle” mathematically defined?

According to http://mathworld.wolfram.com/RiffleShuffle.html : (1) 8 out-shuffles return an ordinary deck of 52 cards to its original order. (2) 7 riffle shuffles are needed to get to close to random. [Hence 8 riffle shuffles would be even better, I think.] So clearly the "riffle shuffles" of (2) are not meant to be identical to "out-shuffles". But then how is a "riffle shuffle" of (2) mathematically defined?

-

A riffle shuffle is defined to take the deck, cut it into an initial segment $A$ and a final segment $B$, and then mix $A$ and $B$ together, preserving the ordering within $A$ and $B$.

There is a standard model of a random riffle shuffle due Gilbert: Let there be $n$ cards in the deck. The probability that the deck is cut at position $k$ is $\frac{1}{2^n} \binom{n}{k}$; then all $\binom{n}{k}$ shuffles of $A$ and $B$ are equally likely. The first condition says that, with high probability, the cut point is near $n/2$, with an error of $\approx \sqrt{n}$. The second condition says that, when I have $a$ cards in my left hand and $b$ in my right, the odds that the next card will drop from the left hand is $a/(a+b)$, so the thicker pack of cards drops faster.

This condition is a decent model for real shuffling, according to experiments by Diaconis. IIRC, these experiments only used two shufflers, Diaconis and a friend, and Diaconis is a practiced magician, so one might wonder if this is a fair sample. We had an undergrad, Alex Cope, who was paying random people here at Michigan to shuffle cards and checking them against the model; he doesn't seem to have published his work yet. ADDED JULY 2014 Cope's data still doesn't seem to be public, but you can read an analysis of it here.

It is also a very convenient theoretical model because there is a very simple description for the inverse process: To produce the inverse of a random shuffle, go through the deck and random place each card in your left hand or your right, according to an independent coin flip; then stack up the decks in your two hands.

For lots more on this model, including the 7 shuffles to randomize result, see Trailing the Dovetail Shuffle to its Lair by Bayer and Diaconis.

-

Aigner & Ziegler explore this fully in Chapter 24 of their Proofs From The Book.

Essentially, a riffle shuffle is a permutation $\pi$ such that the sequence $(\pi(1),\dots,\pi(52))$ is precisely two interleaved increasing sequences.

Consider a deck of 10 cards, as an easier case, and suppose they started in sorted order: 1 at the top, 10 at the bottom. If we cut the deck in half perfectly and interleave one-by-one, the result is $(1,6,2,7,3,8,4,9,5,10)$. Notice we can pick out $(1,2,3,4,5)$ and $(6,7,8,9,10)$ as the two increasing sequences, so there's actually a bijection between the result of the shuffle and the set of ways to cut the deck and then interleave the halves.

-

Out-shuffles and in-shuffles are carefully defined. If you want to randomize a deck, you have to assume the shuffles are not perfect or to assume you randomize between in an out. You would have to check the references. They may have a model of a random riffle, such as each packet is randomly one or two cards.

-
My math would highly probably not be enough for studying that reference. Maybe a further question here: "not perfect" itself is difficult to be defined IMHO, i.e. there may be widely different degrees of imperfectness, and that could eventually influence the claim of "7" in (2) to such an extent that the claim as such would be questionable, I "guess". –  Mok-Kong Shen Sep 24 '12 at 14:01

An out-shuffle is when you cut the deck in half and then interleave the cards alternately from each half, starting with the top half. If the cards are initially numbered 1…52, then after an out-shuffle, they are in the order 1, 27, 2, 28, 3, …, 51, 26, 52.

An in-shuffle is the same thing, but the first card comes from the top of the bottom half of the deck instead of the top of the top half, so the order after the shuffle is 27, 1, 28, 2, 29, …, 25, 52, 26.

Note that the out-shuffle leaves the top and bottom cards fixed, but the in-shuffle has no fixed points.

It is easy to get the computer to calculate that the out-shuffle has order 8, and the in-shuffle has order 52.

-