Tag Archives: e

How to Measure Euler’s Number by Shuffling Cards.

Previously on this blog, I have talked about Buffon’s Needle, which is a way to measure \pi using random numbers. In this entry, I will be talking about a way to measure another fundamental constant e, also by using random numbers.

To measure e, we will shuffle a deck of cards many times and count the number of shuffles that result in the deck being deranged. This means that no card remains in its original position in the deck. This type of arrangement is called a “derangement”.

We will start by computing the theoretical probability (p) getting a derangement, which turns out to be 1/e or about 36.7%, for a sufficiently large number of cards. We will then experimentally measure e by shuffling cards.

To compute the theoretical probability p, we need to understand two numbers:
The first is the total number of arrangements that the cards can be in (R).
The second is how many of those arrangements are derangements (D).
The theoretical probability is the ratio of those two numbers:
p = D/R
and it approaches 1/e.
(Or you could say R/D approaches e.)

The first number is easy, it’s just the factorial of the number of cards in the deck (n).
R_n = n!
The second number D_n is not as straightforward. We have to count the number of derangements a deck can have.

To show a simple example of counting derangements, let’s look at a deck of only 3 cards:
cards
There are 6 ways to arrange these 3 cards (3! = 6)
A,2,3
A,3,2
2,A,3
3,A,2  (this one is a derangement)
2,3,A  (this one is a derangement)
3,2,A

Only 2 of these arrangements have every card moved from its original position. So the number of derangements for 3 cards is 2. So in this case, the probability of getting a derangement is about 33%.
D_3 = 2
p_3 = D/R = 2/3! = 1/3
That’s close to 1/e, but not quite, because it turns out 3 cards are just not enough to produce that probability. We need more.

In general, with a deck of n cards, we can arrange any number k of those cards in P_{nk} number of ways, where:
P_{nk} = \frac{n!}{(n-k)!}
We can use this formula to count the number of ways there are to rearrange a subset k of the cards, while n-k cards remain in a fixed position (we are counting the number of permutations).

Note that n-k \neq 0, then by definition, the corresponding arrangements will not be derangements. If we can count all of these, then we can subtract this number of arrangements from the total number n! to get the number of derangements.

Let’s see this in action by going back to the deck of 3 cards. If we select all the cards to rearrange, we can get all 6 possible permutations:
P_{3,3} = \frac{3!}{(3-3)!} = \frac{3!}{0!} = 3! = 6
A,2,3
A,3,2
2,A,3
3,A,2
2,3,A
3,2,A

If we select only 2 cards out of the 6 to rearrange, we only get a subset of the arrangements. However if we count how many there are with the formula we get 6 permutations:
P_{3,2} = \frac{3!}{(3-2)!} = \frac{3!}{1!} = 3! = 6
So there are 6 ways to arrange 2 cards (6 ways to hold 1 card fixed). But why do we get 6 permutations here? Well, let’s look at all the ways to do this.
If we select 2 and 3 to rearrange, we get 2 permutations:
A,2,3
A,3,2
If we select A and 3 to rearrange, we get 2 permutations:
A,2,3
3,2,A
And if select A and 2 to rearrange, we get 2 permutations:
A,2,3
2,A,3
Notice however that A,2,3 occurs 3 times, and so there are actually 4 unique arrangements here, and they are not derangements by definition. So we have 6 - 4 = 2 derangements for 6 cards.
But is there a way to count unique arrangements without doing it by hand like we did here? Let’s keep going with this pattern.

If we select only 1 card to rearrange, then that’s trivial, because you can’t rearrange one card.
P_{3,1} = \frac{3!}{(3-1)!} = \frac{3!}{2!} = 3
If selecting A:
A,2,3
If selecting 2:
A,2,3
If selecting 3:
A,2,3
All 3 permutations are the same arrangement!

Then if we select no cards to rearrange, this is also trivial.
P_{3,0} = \frac{3!}{(3-0)!} = 1
If selecting nothing:
A,2,3
That’s just 1 permutation.

All duplicate permutations, are accounted for here. The number of permutations for P_{3,0} accounts for one of the duplicates in P_{3,1}:
P_{3,1} - P_{3,0} = 3 - 1 = 2
The permutations left in this difference account for 2 of the duplicates in P_{3,2}:
P_{3,2} - (P_{3,1} - P_{3,0}) = 6 - 2 = 4
And you are left with the unique 4 arrangements that are not derangements.
So to get the number of derangements, we just have to subtract this from the total number of arrangements P_{3,3}:
P_{3,3} - (P_{3,2} - (P_{3,1} - P_{3,0})) = 6 - 4 = 2
And so we see that D_3 = 2

We have a pattern here. We can see that by distributing the negative signs in the above equation we get:
D_3 = P_{3,3} - P_{3,2} + P_{3,1} - P_{3,0}

This can be expressed as a sum:
D_3 = \sum\limits_{k = 0}^3 P_{3,k} (-1)^{3-k}
Or more explicitly:
D_3 = \sum\limits_{k = 0}^3 \frac{3!}{(3-k)!} (-1)^{3-k}

It turns out that this pattern holds for decks of any number of cards n (just replace the 3 here):
D_n = \sum\limits_{k = 0}^n \frac{n!}{(n-k)!} (-1)^{n-k}

For a deck of 3 cards, the number of derangements is: D_3 = 2
For a deck of 4 cards: D_4 = 9
For a deck of 5 cards: D_5 = 44
which then give us the probabilities of derangement:
p_3 = 2/3! = 33.3\%
p_4 = 9/4! = 37.5\%
p_5 = 44/5! = 36.7\%
So by 4 cards, we start seeing a probability closer to 1/e.

Now, to get the probability p of getting a derangement for n cards:
p_n = \frac{D_n}{R_n} = \frac{1}{n!}\,\sum\limits_{k = 0}^n \frac{n!}{(n-k)!} (-1)^{n-k}
The n! factors cancel out, and we are left with:
p_n = \sum\limits_{k = 0}^n \frac{1}{(n-k)!} (-1)^{n-k}

Since the order of addition doesn’t matter, we can change the direction of this sum to start at n and end at 0:
p_n = \sum\limits_{k = n}^0 \frac{1}{(n-k)!} (-1)^{n-k}
If we do some relabeling, the relationship to e will become more obvious. Let’s set m = n-k, so we can write:
p_n = \sum\limits_{m=0}^n \frac{1}{m!} (-1)^{m}
This looks like a truncated Taylor expansion of the exponential function e^x.
A Taylor expansion is a way of expressing a function as a polynomial.

The Taylor expansion of the exponential function is:
e^x = \sum\limits_{m=0}^\infty \frac{1}{m!} x^m
If we plug in x = -1 we get:
e^{-1} = \sum\limits_{m=0}^\infty \frac{1}{m!} (-1)^m
which is the limiting case of a deck with infinite cards:
p_\infty = \frac{1}{e}

This equivalence to the Taylor expansion is the reason why as you increase the number of cards, the probability of getting a derangement approaches 1/e.
To put it another way:
\frac{1}{p} = \frac{R}{D} \approx e.

Now that we have seen the theoretical probability, let’s do the experiment.
Take a standard 52 card deck, note the original positions of the cards, then shuffle and see if you have a derangement. Keep shuffling and noting if the result is a derangement. Keep doing this about 40,000 times. Count the total number of shuffles R and the number of derangements D you get.
If you then take the ratio \frac{R}{D} you will get something approaching e.

Just kidding. That would be extremely tedious. Instead, we can have a computer it for us.
eulerfig3

For a deck of 52 cards, it seems to take about 40k shuffles for the ratio of shuffles to derangements to approach e. See the figure above.

The code used to compute e from shuffles is shown below:
Here I used MATLAB code, to take advantage of vectorization and logical array operations. The inputs are cards (the number of cards in a deck) and games (the number of shuffles). Wins (a win is when you get a derangement) are then counted.

 function eulersnum = eulerdeck(cards,games)
 wins = 0;
 series = 1:cards;
 for ii=1:games
  shuffled = randperm(cards);
  wins = wins + ~any(series == shuffled);
 end
 eulersnum = games/wins;
end 

The known value of e is 2.7183…
To get an accurate measurement we should use a deck with a lot of cards, since that will include more terms of the Taylor expansion. We should also shuffle many times to be sure that we capture the probability.
So with a deck of 1000 cards, and 10 trials, each of 1000 shuffles, we measure e to be:
2.7265 \pm 0.1060

Advertisements