# Why is it that shuffling a deck so that all permutations are equally likely requires swapping only later elements?

Apparently, to shuffle a deck of cards so that all permutations are equally can be done by going through the deck in order and swapping the current card with cards that do not appear earlier than the current card.

Also apparently, if one just randomly swaps cards around, not all permutations of cards are equally likely to result from the shuffling. Why is this the case?

-
Can you be specific about "randomly swaps cards around"? Are you picking two random cards independently and switching them, and then repeating that some number of times? – Lopsy Feb 14 '12 at 1:17
By the way, for every arrangement to be equally likely, you need to be picking equally from 52! choices. Because 52! is divisible by 23, you'll have to pick a card from 23 different choices at some point to get a uniform distribution. Depending on your answer to my first comment, though, it's likely that your routine converges to a equal distribution and just never exactly reaches it. – Lopsy Feb 14 '12 at 1:21
Interesting... and by randomly, I mean the next card swap could mean swapping with any card in the deck (not just cards not encountered before). – David Faux Feb 14 '12 at 1:26
Question is referring to the Fisher-Yates shuffle. – Dan Brumleve Feb 14 '12 at 1:29
Problems like this can be easier to understand if you change the value of $n$. Instead of $52$ cards, how do you feel about the possibilities from shuffling only $3$ cards? It doesn't help (me at least) with the intuition, but it does let you actually enumerate all possible shufflings. – alex.jordan Feb 14 '12 at 2:25

If you swap the top card with a card chosen randomly with uniform distribution (including the card itself, in which case the "swap" doesn't change anything), then the new top card is any one of the cards with equal probability. Thus every card also has the same probability of not being that card, that is, of being in the subdeck below the top card. Thus the deck will be properly shuffled if the rest of the procedure properly shuffles that subdeck. But the rest of the procedure is precisely the whole procedure applied to that subdeck, so the result follows by induction, the base case being a deck of $1$ card, which is always properly shuffled.

For the second part of the question, as Lopsy wrote, you'd have to say more about what you mean by "randomly swapping cards around".

-

Here's an argument that the other method - where you can pick the swapped card from anywhere in the deck - has a bias.

Let's say that the original last card in the deck is the Ace of Spades. Let's look at the probability, using the revised method where we pick the swapped card out from the entire deck, that the Ace of Spades ends up at the top of the deck.

For this to happen, we need to either pick the Ace of Spades as the swapped card first and then never pick it again, OR never pick it until the end and then swap it with the first card. The probability of this is

$2 \times \large \frac{1}{52} \times \frac{51}{52}^{51}$.

The power in that expression is about $1/e$, so the chance of the Ace of Spades ending up at the top of the deck is $2/e$, or $.736$, times what it should be. This isn't just a tiny fraction away from an equal distribution - this method of shuffling has a statistically significant amount of bias. In other words, you wouldn't catch me playing poker with someone shuffling like this.

-

Another quick heuristic explanation of why the 'at each stage, swap card $i$ with a random card from $1..n$' mechanism doesn't work: at each step (of $n$ steps) you're choosing one of $n$ options, independently of any other choice that's been made; in other words, there are $n^n$ different execution paths for your algorithm to follow, each of which has identical probability. But there are exactly $n!$ different ways your deck can be shuffled, and each of them has to be produced with equal probability by your algorithm; since $n!$ doesn't divide $n^n$, this is impossible - the algorithm will have to generate some permutations with a higher probability than others.

This also explains (roughly) why the Fisher-Yates shuffle works; at the first step there's a one-of-$n$ choice being made, at the second step an (independent) one-of-$(n-1)$, etc, so in the end there are $n\cdot(n-1)\cdot\ldots\cdot 1 = n!$ different execution paths, each of which corresponds uniquely to one of the possible permutations.

-

Suppose you have a deck of cards and a table with 52 slots for the shuffled cards.

When you do the Fischer Yates, you are basically doing this:

Select a random card, put it in slot $1$.

Of the remaining $5$1, select another random card, put it in slot $2$ and continue.

People usually are confused with Fischer Yates, because implementations typically use the deck of cards (the input array) as the set of slots itself, and the act of putting a card in a slot is done by swapping cards (the elements of the input array). This is actually done to make the algorithm $\mathcal{O}(n)$ in the input array case (basically, the 'get random card', becomes $\mathcal{O}(1)$).

The probability that card $j$ goes in slot $k$ is given by (where $n=52$)

$$\frac{n-1}{n}\cdot \frac{n-2}{n-1} \cdots \frac{n-k+1}{n-k+2} \cdot \frac{1}{n-k+1} = \frac{1}{n}$$

(what above computes is: does not go into slots $1$ to $k-1$ and goes in to slot $k$).

Each card is equally likely as any other card to end up in a given slot.

Thus given two permutations $A$ and $B$, both are equally likely to occur.

Note: You might think that probability of getting a specific permutation is $\frac{1}{n^n}$ (or $\frac{1}{n^{n-1}}$) based on the above probability of $\frac{1}{n}$, but it is not. Can you say why?

-

Building on Lopsy's comment

If you do $n$ random swaps, then there are $\frac{52 \times 51}{2}=1326$ equally possible actions each turn, so the probability of each possible final outcome expressed as a rational fraction in lowest terms must have a denominator which divides $1326^n$. Since $1326=2 \times 3 \times 13 \times 17$, only these primes can divide the denominator.

But you want the fraction to be $\frac{1}{52!}$ because you want all permutations to be equally likely, and this denominator also includes the primes $5,7,11,19,23,29,31,37,41,43,47$. So for finite $n$ you cannot get this exact fraction.

-

I think your first paragraph refers to the following.

Suppose you want to do the cycle $(4\ 7\ 2\ 9\ 3)$. You can use $$(4\ 7\ 2\ 9\ 3)=(2\ 9)(2\ 3)(2\ 4)(2\ 7)$$ so that all you are doing is swapping 2 with a number bigger than 2 - that is, swapping the current card with a later card.

Now, what I did with this cycle is clearly possible with any cycle.

Every permutation is a product of disjoint cycles, so given a permutation, do this with each cycle, first with the cycle containing the lowest number, then among the other cycles the one with the lowest number, etc. For example, $$(5\ 12\ 4\ 9\ 10)(7\ 2\ 1)(8\ 3\ 11\ 6)=(1\ 7)(1\ 2)(3\ 11)(3\ 6)(3\ 8)(4\ 9)(4\ 10)(4\ 5)(4\ 12)$$ so you swap card 1 with later cards, then card 3 with later cards, then card 4 with later cards.

-

One possible interpretation of "randomly swaps cards around" is that you perform the following operation some $m$ times (for some fixed $m$): randomly choose a pair of cards from the deck (say of $n$ cards) and swap their positions. This certainly won't work, though, because you'll have either an odd or an even permutation of the original deck, depending on whether $m$ is odd or even. So let's say instead of fixed $m$ the number of swaps is a random variable $M$ (independent of the choices of cards to swap). Random swapping can be considered as a Markov chain where the state space consists of the $n!$ permutations of the deck. Let $P$ be the transition matrix of this Markov chain. If $\text{Pr}(M=m) = c_m$, the probability distribution of states at the end of the process is a row of $F(P) = \sum_m c_m P^m$. We want all these rows to be $[1/n!, \ldots, 1/n!]$, i.e. $F(P) = E$ where $E$ is the $n! \times n!$ matrix with all entries $1/n!$.

I'll suppose $M$ is bounded, so $F(z) = \sum_m c_m z^m$ is a polynomial, say of degree $d$. Since this is a probability generating function, $F(1) = 1$ and all $c_m \ge 0$. $E$ has eigenvalues $0$ (with multiplicity $n!-1$) and $1$ (with multiplicity $1$). In order for $F(P)$ to have these eigenvalues, what we need is that $F(\lambda) = 0$ for all eigenvalues $\lambda$ of $P$ except for $1$ (which has multiplicity $1$). However, if $P$ has a positive eigenvalue other than $1$ this will not be possible, since if all $c_m \ge 0$ and not all are $0$, $F(\lambda) > 0$ when $\lambda > 0$. Now unfortunately I don't know in general whether $P$ has such eigenvalues, but it does for $n=4$ and $5$. So there is no way to get a random shuffle of, say, a 5-card deck by "randomly swapping cards around" a random number of times, and I conjecture that the same is true for any $n \ge 4$. On the other hand, you can get a random shuffle of a $3$-card deck in this way: with probability $1/2$ you do one random swap and with probability $1/2$ you do two.

-