Take a deck of 52 cards and shuffle it well. What is the probability that at least one card will be in the same position as when you started? To answer that question, we first have to define derangements and subfactorials.
A derangement is a permutation of a set that leaves no element where it started. For example, the set {1, 2, 3} has two derangements: {2, 3, 1} and {3, 1, 2}. The arrangement {2, 1, 3}, for example, is not a derangement because it leave 3 in place. The number of derangements of a set with n elements is !n, the subfactorial of n. (Note that factorial puts the exclamation point after the number and subfactorial puts the exclamation point in front. This is unfortunate notation, but it’s commonly used.)
It turns out !n is given by
Note that the expression in parentheses is the power series for exp(-x) evaluated at x = 1 and truncated after the nth term. It follows that for positive n, you can calculate !n by first computing n!/e and rounding the result to the nearest integer.
If a permutation is randomly selected so that all permutations are equally likely, the probability that a permutation is a derangement is !n / n!. As n increases, this probability rapidly approaches 1/e. That means that for moderately large n, the probability that a random permutation will leave at least one element fixed is approximately 1 -1/e or about 63%. So there’s about a 63% chance that at least one of the cards is in the same position after shuffling the deck.
The approximation above says that !n / n! ≈ 1/e. How good is that approximation? The error is the error in truncating the series for exp(-x). This is an alternating series, so the absolute error is bounded by the first term left out. In other words, the error is less than 1/(n+1)!. So for n = 52, the error is on the order of 10-70. Even for n as small as 10, the error is on the order of 10-8.
This says that the probability that at least one card stays in its original position after the deck is shuffled hardly depends on the size of the deck. For example, if the deck had 20 cards or 100 cards rather than 52, the probability of at least one card being unmoved after the cards are shuffled would be essentially the same.
Extra credit
So far we only looked at the probability of no card staying in the same place (or the complementary probability, at least one card not staying in the same place.) What is the probability that exactly k cards stay in the same place after shuffling? This is given by
As n increases, this probability approaches 1/(k! e).
See Nonplussed! by Julian Havil for more details.
This is a quote from my brother:
”
This type of problem is a perfect use of the complimentary trick: the prob of an event is 1 minus the probability of all other events. Namely, in this case the prob that at least one card is in the same place is 1 minus the probability that no cards are in the same place. For a deck of 52 this is 1 – (51/52)^52
In general the closed form solution is 1 – (n-1/n)^n
“
sorry, I accidentally submitted before I finished.
I agree that the complementary trick makes the problem simpler for having at least one problem in place, but your 1/e solution is better generalized to the exactly k cards being in the same place.
So, this is a good illustration of the elegant solution only getting you so far before it becomes messy and your heavy-duty derivation being more useful
Joel, I’m afraid I have to disagree with your brother in part. I agree that the the probability of at least one card staying in place is 1 minus the probability that no cards stay in the same place. But the formula 1 – (n-1/n)^n is incorrect because the cards are not independent.
Comment about the expression D(n) = ((n-1)/n)^n.
As noted above, D(n) does not equal the probability that every card is displaced form its natural position. Look at the case n=2, for instance. The two permutations of the cards are [ab] and [ba]. So the probability that every card is displaced is 1/2 , which disagrees with the value D(2)=1/4.
However, if n is large, then D(n) is an excellent approximation to the exact
probability no card is displaced. This is because D(n) approaches 1/e as n goes to infinity. Note that when n is large, then the placements of card i and card j are more nearly independent of one another.
“If a permutation is randomly selected so that all permutations are equally likely…”…most real world shuffles are nowhere near close to being uniform distribution of permutations. That is, D(n) is great for this random permutation idea, but terrible for real world shuffling. No one throws the card sin the air and picks them up.
The riffle shuffle is the most common way, and if done poorly there is a good chance that some stay in the same place (like those at the ends). But even with a ‘reliable’ riffle shuffle, you still have problems. See Aldous, David; Diaconis, Persi (1986), “Shuffling Cards and Stopping Times”, American Mathematical Monthly (The American Mathematical Monthly, Vol. 93, No. 5) 93 (5): 333–348. (links on the wikipedia page for ‘Shuffling’)
A nice post
The expected number of unmoved cards is always exactly 1 since it is the sum of prob(card i unmoved) = n x 1/n
This suggests that number of unmoved cards is approximately Poisson (1), as the formulas John gives suggest as well
For those interested in the Poisson heuristic David Aldous has an awesome book