Question

Consider the following approach to shuffling a deck of \(n\) cards. Starting with any initial ordering of the cards, one of the numbers \(1,2, \ldots, n\) is randomly chosen in such a manner that each one is equally likely to be selected. If number \(i\) is chosen, then we take the card that is in position \(i\) and put it on top of the deck-that is, we put that card in position 1 . We then repeatedly perform the same operation. Show that, in the limit, the deck is perfectly shuffled in the sense that the resultant ordering is equally likely to be any of the \(n !\) possible orderings.

Short answer

In the given shuffling method, each card has a fixed probability \(p_i = \frac{1}{n}\) of being chosen. We showed that for each iteration, the probability of obtaining a new arrangement after one iteration depends on the current arrangement and the probabilities of selecting different card positions. After infinitely many iterations, we demonstrated that the probability of obtaining any arrangement B remains constant and is symmetric for all possible orderings. As a result, in the limit, each of the \(n !\) possible orderings is equally likely with a probability of \(P(B_j) = \frac{1}{n !}\), proving that the deck is perfectly shuffled.

Step-by-step solution

Define the variables

Let's denote the initial arrangement of n cards as \(A_0\). At each subsequent iteration, let's denote the arrangement as \(A_i, i=1, 2, \ldots\). Now let's define \(p_i\) as the fixed probability of choosing the card in position \(i\). Since we choose any number \(1,2, \ldots, n\) with equal probability, \(p_i = \frac{1}{n}\) for all \(i\).

Calculate the probability of obtaining a new arrangement after one iteration

To calculate the probability of obtaining a new arrangement after one iteration, we need to consider all possible cases of moving a card to the top of the deck. For each case separately, we can calculate the new arrangement's probability by multiplying the current arrangement probability and the probability of selecting the card in a specific position. Then we sum all these probabilities to get the overall probability of the new arrangement. Let Q be a new arrangement obtained from A after a single iteration. $$ P(Q|A) = \sum_{i=1}^n \frac{1}{n} P(A|Q, i) $$ Where \(P(A|Q, i)\) is the probability of obtaining the initial arrangement A knowing we have chosen the card in position i.

Determine the probability that the deck is perfectly shuffled infinitely

We want to show that after an infinite number of iterations, the deck is perfectly shuffled such that each of the n! possible orderings is equally likely. Denote the probability of obtaining any arrangement B after infinitely many iterations as P(B). The main idea is to show that the probability P(B) remains the same for any ordering B as we keep iterating, which proves that the deck becomes perfectly shuffled. Consider the probability of obtaining arrangement B after k+1 iterations: $$ P(B|A_{k+1}) = \sum_{i=1}^n \frac{1}{n} P(A_k|B, i) $$ Now let's use the fact that for infinitely many iterations, \(P(B)=P(A_k)\), and rewrite the equation: $$ P(B) = \sum_{i=1}^n \frac{1}{n} P(B|Q, i) $$ This equation states that the probability of obtaining any arrangement B is equal to the average of probabilities of obtaining B after selecting cards in positions 1 to n, which holds for every iteration.

Show that the probability of obtaining any ordering is 1/n!

Since P(B) holds for any ordering B, due to the symmetry of the process, this implies that the probability P(B) remains the same for any B as we keep iterating. Therefore, in the limit, the deck is perfectly shuffled, and the probability P(B) for each of the n! possible orderings must be equal. Let there be m distinct orderings in the limit. Then: $$ \sum_{j=1}^m P(B_j) = 1 $$ Since all orderings are equally likely in the limit, we have: $$ P(B_j) = \frac{1}{m} \Rightarrow m = \frac{1}{P(B_j)} $$ We know that there are n! possible orderings. Therefore, we have: $$ m = n! \Rightarrow P(B_j) = \frac{1}{n!} $$ Thus, we have shown that in the limit, the deck is perfectly shuffled in the sense that the resultant ordering is equally likely to be any of the \(n !\) possible orderings.

Key concepts

Random Permutation

The process of shuffling a deck of cards can be viewed as creating a random permutation of the deck. A permutation is simply an arrangement of objects in a specific order. When it comes to a deck of cards, a random permutation is the result of shuffling the cards such that each possible arrangement has an equal chance of occurring.

For instance, if we have a deck of three cards labeled A, B, and C, there are 3! (which means 3 factorial) or 6 different ways to arrange these cards: ABC, ACB, BAC, BCA, CAB, and CBA. A good shuffle would make each of these arrangements equally likely.

In the card shuffling problem, each card's position is affected randomly, leading ideally to an outcome where all possible orderings are equally probable. This is the essence of a random permutation in the context of probability and card shuffling.

Probability Models

The concept of probability models provides a mathematical framework to predict the likelihood of various outcomes. In our card shuffling example, each shuffle is a random experiment with a number of possible outcomes. Each of these outcomes is an arrangement of the deck of cards.

A probability model for this experiment assigns a probability to each of these outcomes. In a fair shuffle, where each card has an equal chance of being placed in any position, the model is one of uniform distribution; that is, each distinct arrangement is equally likely.

When we apply a probability model to the shuffling process, we can quantify expectations about the randomness and fairness of the shuffle through mathematical analysis. The application of probability models ensures that our predictions about the shuffling process are not just based on intuition but on established statistical principles.

Combinatorial Probability

Delving into the idea of combinatorial probability allows us to handle problems that involve counting and probability simultaneously. It integrates the rules of counting from combinatorics with the principles of probability.

Combinatorial probability is central to understanding our card shuffling problem as it requires counting the total number of possible outcomes (like the 6 arrangements in the three-card example). These countable outcomes form the sample space—the set of all possible outcomes. For a full deck of playing cards, which typically has 52 cards, the sample space is incredibly large, specifically 52! possible orderings.

Once we have the total number of outcomes, we can use combinatorial probability to determine the likelihood of any single outcome or set of outcomes. For instance, the chance of obtaining any specific permutation when shuffling the deck is one over the factorial of the number of cards: \( \frac{1}{n!} \).

Limit Theorem

A limit theorem in probability is a concept that describes the behavior of a sequence of random events as the number of trials or observations approaches infinity. For card shuffling, the relevant limit theorem would assert that after a significant number of shuffles, the probability distribution of the arrangements converges to a certain limit.

In our exercise, we used a probability model to predict that with enough iterations of shuffling, any arrangement of the deck becomes equally likely. This conclusion is drawn from applying a limit theorem, which suggests that as the number of shuffles () increases indefinitely, the distribution of card arrangements approaches uniformity—each of the \(n!\) possible orderings becomes equally probable.

Understanding limit theorems helps in grasping how random processes behave over a long period or many repetitions. In real-world terms, this means that given enough shuffles, no card has a higher chance to be in one position over another, and every card has journeyed through a random walk to arrive at a position as part of a perfectly shuffled deck.