In my previous post on card shuffling, I established a basic framework in which we will work. We are given a probability distribution on and we wish to determine when first begins to decay exponentially, where is the -fold convolution of One key feature of card shuffling theory, as well as much of finite Markov chains in general, is that the tools available are often very particular to a small class of problems. There just aren’t very many big hammers around. Even though the theorem described in the previous post was quite general, it was non-quantitative, and so not especially useful in practice.

The standard shuffling technique is called the “riffle shuffle.” In this shuffle, the deck is cut in half, and the two halves are zippered together. We need to come up with a mathematical way of describing the riffle shuffle, and I’ll list three different methods (I’m assuming the deck has cards here, but any will do):

**First Way.** The first thing to think about is how we cut the deck. Mathematically speaking, we will assume the number of cards in the top half of the deck after we cut is binomially distributed. All this means is that to determine the number of cards we cut from the top, flip 52 coins and count the number of heads to figure out how many cards go in the top half. It may seem strange that there is a positive probability of having all 52 cards in the deck sitting in the “top half” but the probability is extremely small and so doesn’t matter so much. For most shufflers, the size of the two “halves” are often quite different. Anyway, suppose that our result is cards in the top half. From here, we think of having 52 boxes lined up and put the cards in them. We pick of the boxes (assuming each box is equally likely) and put the top half of the deck in those boxes, keeping them in the same order. Put the remaining cards in the remaining boxes, keeping them in the same order relative to each other. Stack the cards back up. Note that there are ways to put cards in 52 boxes, so that the probability of any box choice is .