The Ellsberg Paradox

Yesterday, at Waterloo Ignorance Day, one speaker mentioned the Ellsberg paradox, which I hadn't heard of before. Believe it or not, it is named for Daniel Ellsberg, who would later become famous for releasing the Pentagon Papers.

Here it is: you have an urn with 90 well-mixed balls. There are R red balls, Y yellow balls, and B black balls. You know only the following information: R = 30, and Y+B = 60. You now get to choose between

Gamble A: win $100 if you draw a red ball vs.
Gamble B: win $100 if you draw a black ball.

You are also given a choice between

Gamble C: win $100 if you draw a red or yellow ball.
Gamble D: win $100 if you draw a black or yellow ball.

Which choices do you prefer? A over B or B over A? And C over D or D over C?

A Neat Problem on Card Arrangements

Here's a neat problem on card arrangements. I learned about it on reddit. Here's the easiest way to state it:

Given a deck of 52 cards shuffled randomly -- a deal -- what is the probability that, somewhere in the deck, there is an Ace adjacent to a King?

Try to figure it out before looking at the analysis below.

At first glance, it doesn't seem so easy. For example, if we fix the positions of the Kings, then the Aces could appear on either side of a King, giving (it seems) 8 possibilities for an Ace to appear. This suggests that the number of deals where an Ace fails to be adjacent to a King is

(52 choose 4) : choose positions where the Kings are
* (4!) : choose the relative order of the 4 Kings
* (40 choose 4) : choose the positions for the Aces: not where the Kings are, or on either side of them
* (4!) : choose the relative order of the Aces
* (44!) : choose the positions of the remaining 44 cards.

This gives a probability of no Ace adjacent to a King of 9139/19458, or about 0.4697.

Unfortunately, this naive analysis is wrong. Why? If we're trying to compute the number of deals where an Ace fails to be adjacent to a King, we didn't consider the fact that in many deals, there will be two or more Kings adjacent to each other, thus increasing the number of places where Aces could go. Similarly, Kings could appear at the beginning or end of the deck. So the real probability of no Ace adjacent to a King should be somewhat higher than we computed.

Of course, we could go through all the possibilities of how many adjacent spots there are. But that is an awful calculation. I asked Ian Goulden, a professor in the Combinatorics & Optimization department at Waterloo, and he came up with this lovely argument - which I've modified slightly:

We start by choosing all the cards that are neither Kings nor Aces. There are 44 other cards, and so there are 44! ways of arranging them. Now we're going to insert the Aces. But to do so, we'll first figure out how the Aces are arranged by breaking them up into contiguous nonempty blocks. For example, you might have three Aces in a row, and then a 4th Ace somewhere later on. There can be 1, 2, 3, or 4 contiguous blocks; let the number of blocks be k (and we'll have to sum on k from 1 to 4).

Once we have the number of blocks, we need to assign the number of Aces in each block. It's not hard to see that this can be done in (3 choose k-1) ways. For example, for k = 1, there is only one way: put all 4 Aces in a single block. For k = 2 we can have the first block with 1 Ace, and the second with 3; or the first with 2 and the second with 2; or the first with 3 and the second with 1, etc. Finally, we can put the Aces themselves into these blocks in 4! ways. Now that we have the Aces in the blocks, we need to insert them into the 44 cards. There are 45 gaps between these 44 cards where we can insert the k blocks (including a gap to the left of each card and one at the right end), so that gives (45 choose k) ways of doing this.

We now have 48 cards laid out, and it remains to insert the 4 Kings. We'll do this in order: the King of Hearts first, the King of Spades next, then Diamonds, then Clubs. When we insert the first King, we can't put it immediately to the left of each block (there are k places); nor can we put it to the right of each Ace. So there are 49 positions, of which (4+k) are ruled out. So there are only 45-k places to put the King of Hearts. Then there are 46-k places to put the King of Spades, 47-k places for the King of Diamonds, and 48-k places for the King of Clubs.

Thus, the total number of deals where no King is adjacent to an Ace is
(44!) * Σ_k=1⁴ (3 choose k-1)(4!)(45 choose k)(45-k)(46-k)(47-k)(48-k) =
41435794890014187172891516774574832972049361890932487618560000000000. Dividing this by 52! we get 300684703/585307450, or about 0.5137, as the probability that no King is adjacent to an Ace. So the probability that in a random deal there will be a King adjacent to an Ace is 284622747/585307450, or about .4863.

As a check, this agrees with a paper of David Singmaster entitled "The probability of finding an adjacent pair in a deck", Mathematical Gazette 75 (1991), 293-299. Goulden's formula is much simpler and more elegant than Singmaster's.

Generalizing the ideas above, Ian Goulden considered the more general situation where you have N cards, C cards in the first group, D cards in a second disjoint set, with C ≤ D. Then the probability that no card in the first group is adjacent to a card in the second in a random deal of N cards is given by

Σ_k=1^C (C-1 choose k-1)*(N-C-k choose D)*(N-C-D+1 choose k)/( (N-D choose C)*(N choose D)).

Thanks to Ian Goulden for letting me post his beautiful solution.