Why Track the Whole Deck?
A shuffle changes an arrangement of cards, so a natural state is the complete order of the deck. This choice retains the information needed to describe the next shuffle: from any current ordering, one can apply the specified operation and calculate the probability of each resulting ordering. The model is a Markov chain when the random choice used for the next shuffle is fresh and the rule does not depend on earlier arrangements.
Consider a deck of \(m\) distinct cards. Its possible arrangements are the \(m!\) ordered lists containing each card exactly once. A state records which card is in each position; it is not just the identity of one selected card or the number of cards of a particular type. The state space can grow quickly, so small decks are useful for seeing how the transition rule is built without needing to display a large matrix.
To make the conditional statement precise, work on a probability space \((\Omega,\mathcal{F},\mathbb{P})\). Let \(\mathcal{F}_n\) contain the initial order and all random choices made through shuffle \(n\). If the next shuffle uses a random choice independent of \(\mathcal{F}_n\), its distribution is the same at every step, and the result is a function only of the current order and that choice, then the full order has the Markov property. The next result gives the transition probabilities directly.
Proof. Fix \(n\), a current order \(x\), and a possible next order \(y\). Given \(\mathcal{F}_n\), the current order \(X_n\) is known. The event \(X_{n+1}=y\) is therefore the event \(F(X_n,U_{n+1})=y\). On the event \(X_n=x\), this is the event \(F(x,U_{n+1})=y\). Independence of \(U_{n+1}\) from \(\mathcal{F}_n\) gives \(\mathbb{P}(X_{n+1}=y\mid\mathcal{F}_n)=\mathbb{P}(F(x,U_{n+1})=y)=p_{xy}\) whenever \(X_n=x\). This conditional probability depends on the past only through \(X_n\), and the same distribution of \(U_{n+1}\) and the same rule \(F\) are used at every step. Thus the process is Markov and time-homogeneous. For a fixed \(x\), the events \(\{F(x,U_{n+1})=y\}\), as \(y\) ranges over \(S\), are disjoint and together include every possible outcome of the shuffle. Their probabilities are nonnegative and sum to one. Hence each row of \(P\) sums to one. \(\square\)
For a shuffle with finitely many possible operations \(u\), write \(w_u=\mathbb{P}(U_{n+1}=u)\). The same argument gives the useful counting rule \(p_{xy}=\sum_{u:F(x,u)=y}w_u\). If several operations lead to the same order, their probabilities must be added. This rule is a direct consequence of the theorem: the possible operations form disjoint outcomes, and the event of reaching \(y\) consists of all operations that produce \(y\).
Worked Example: A Random Swap in a Two-Card Deck
Label the two distinct cards \(A\) and \(B\). At each step, swap their positions with probability \(\tfrac13\), and leave the deck unchanged with probability \(\tfrac23\). Use state order \(AB,BA\). Find the transition matrix and the distribution after one shuffle when the deck starts in order \(AB\).
From \(AB\), staying gives \(AB\) with probability \(\tfrac23\), and swapping gives \(BA\) with probability \(\tfrac13\). From \(BA\), staying gives \(BA\) with probability \(\tfrac23\), and swapping gives \(AB\) with probability \(\tfrac13\). Thus
Both rows sum to one: \(\tfrac23+\tfrac13=1\) for the first row and \(\tfrac13+\tfrac23=1\) for the second. The initial distribution is the row vector \(\mu_0=(1,0)\), because the deck starts in \(AB\) with probability one. The one-step distribution is
Check: the two probabilities in \(\mu_1\) sum to \(\tfrac23+\tfrac13=1\). Directly from the shuffle rule, the deck stays \(AB\) with probability \(\tfrac23\) and becomes \(BA\) with probability \(\tfrac13\), agreeing with the matrix calculation.
Enumerating Transitions for Three Cards
With three distinct cards, there are six full orders. A \(6\) by \(6\) matrix would be cumbersome to display, but a transition row can still be calculated by listing the operation outcomes. Fix a state ordering whenever a full matrix is needed; the order of coordinates in a distribution must match the order of states used for the matrix. For a small model, a table of transition rows often shows the same information more clearly.
Worked Example: Choose a Pair and Swap It
Let \(S\) consist of all permutations of \(A,B,C\). At each step, select one of the three pairs of positions, \(\{1,2\}\), \(\{2,3\}\), or \(\{1,3\}\), uniformly, and swap the cards in those positions. List the transitions from every state and find the distribution after one step if the initial order is equally likely to be \(ABC\) or \(ACB\).
There are three possible operations, each with probability \(\tfrac13\). Swapping different pairs in a three-card order produces different resulting orders. The transition rows are therefore:
| Current order | Possible next orders, each with probability \(\tfrac13\) | Row sum |
|---|---|---|
| \(ABC\) | \(BAC, ACB, CBA\) | \(\tfrac13+\tfrac13+\tfrac13=1\) |
| \(ACB\) | \(CAB, ABC, BCA\) | \(\tfrac13+\tfrac13+\tfrac13=1\) |
| \(BAC\) | \(ABC, BCA, CAB\) | \(\tfrac13+\tfrac13+\tfrac13=1\) |
| \(BCA\) | \(CBA, BAC, ACB\) | \(\tfrac13+\tfrac13+\tfrac13=1\) |
| \(CAB\) | \(ACB, CBA, ABC\) | \(\tfrac13+\tfrac13+\tfrac13=1\) |
| \(CBA\) | \(BCA, CAB, BAC\) | \(\tfrac13+\tfrac13+\tfrac13=1\) |
Each row is a probability distribution because it lists the results of all three equally likely pair choices. In the specified initial distribution, \(ABC\) and \(ACB\) each have probability \(\tfrac12\). From \(ABC\), the possible next orders are \(BAC, ACB, CBA\), each with probability \(\tfrac13\). Their unconditional probabilities contributed by this initial state are each \(\tfrac12\cdot\tfrac13=\tfrac16\). From \(ACB\), the possible next orders are \(CAB, ABC, BCA\), also each contributing \(\tfrac12\cdot\tfrac13=\tfrac16\). Together, these two sets contain all six orders, so the one-step distribution assigns probability \(\tfrac16\) to each.
Check: the six resulting probabilities sum to \(6\cdot\tfrac16=1\). Also, each of the two possible starting states contributes total probability \(\tfrac16+\tfrac16+\tfrac16=\tfrac12\), exactly its initial probability.
The example illustrates why counting operations matters. The probability of a resulting order is the total probability of all operations that produce it, not a probability assigned by counting only the other possible arrangements. When different operations can give the same result, their probabilities combine; when all outcomes are distinct, each outcome retains the probability of its operation.
Worked Example: Move a Uniformly Selected Card to the Top
Use three cards and the same state space of all six orders. At each step, choose one of the three positions uniformly, remove the card in that position, and place it first, leaving the relative order of the other cards unchanged. Find the transition probabilities from \(BCA\), and compute the one-step distribution when the initial order is \(BCA\) with probability one.
From \(BCA\), choosing position \(1\) leaves the order \(BCA\). Choosing position \(2\) moves \(C\) to the front and gives \(CBA\). Choosing position \(3\) moves \(A\) to the front and gives \(ABC\). Each position is selected with probability \(\tfrac13\), so the transition probabilities from \(BCA\) to \(BCA,CBA,ABC\) are each \(\tfrac13\); the probabilities to the other three orders are zero.
In the state order \(ABC,ACB,BAC,BCA,CAB,CBA\), the initial distribution is \(\mu_0=(0,0,0,1,0,0)\). The only occupied row after multiplying by the transition matrix is the row for \(BCA\), so
Check: the three nonzero entries correspond exactly to \(ABC,BCA,CBA\), the three outcomes listed from \(BCA\). Their sum is \(\tfrac13+\tfrac13+\tfrac13=1\).
What the Model Assumes—and a Common Error
The theorem’s assumptions describe the mechanism, not merely the notation. The next random operation must be independent of the information available before that operation, and the same rule must be used at each step for a time-homogeneous transition matrix. If a shuffle procedure uses a hidden instruction carried over from the previous step, the full deck order alone might not determine the next transition probabilities. One can sometimes resolve this by including that instruction in the state, but without it the stated Markov model is not justified.
Similarly, observing only one card’s position is not generally the same as recording the full order. For instance, the same position of card \(A\) can occur with different orders of the other cards, and a shuffle rule that treats positions differently may give different next-step probabilities from those orders. The full-order state avoids that loss of information for the shuffle rules defined here.
Common mistake: assigning probability by the number of resulting orders. In the pair-swap example, a mistaken calculation might say that from \(ABC\) there are only two “other” orders, so each should have probability \(\tfrac12\), while the current order has probability zero. That is wrong: the rule selects one of three pairs, and the three pair choices give \(BAC, ACB,\) and \(CBA\), respectively. The correct probabilities are \(\tfrac13\) for each of those three orders and zero for \(ABC\). The check is \(\tfrac13+\tfrac13+\tfrac13=1\). Probabilities come from the specified random operation, not from the number of arrangements one first notices.
To build a shuffle chain reliably, list the full state space, specify each random operation and its probability, apply every operation to each current order, and add probabilities when operations produce the same next order. Then check that every row sums to one. Only after those checks should the transition matrix be used to update an initial distribution.
Check Your Understanding
Use the stated shuffle rules and show the operations that support each answer.
- For a two-card deck, swap the cards with probability \(\tfrac14\) and otherwise leave them in place. Write the transition matrix in state order \(AB,BA\) and check each row sum.
- In the three-card pair-swap example, starting from \(CBA\), list the three possible next orders and their probabilities.
- For the move-to-top rule, starting from \(ACB\), what orders result from choosing positions \(1\), \(2\), and \(3\), respectively?
- State the independence and time-homogeneity conditions that let the full deck order satisfy the Markov property in the theorem.
- Explain why the probability of a next order must add the probabilities of all shuffle operations that produce it.