How does the pigeonhole principle intuitively suggest incorrect computations of probability?

Question

Here is an interesting false computation using the pigeonhole principle.

Suppose I am asked to compute the probability that three successive tosses of a fair coin will have the same result.

It can be readily seen that there are eight possible outcomes, with two of them having the same result three times. Therefore, the probability is 1/4.

However, suppose that I claim that the probability should be 1/2, and here is my reasoning: First, I point out that there are three coin tosses and only two possible outcomes for each toss. Therefore, at least two out of the three tosses are guaranteed to have the same result. I need only point out that the probability of the third toss having the same result is 1/2 to arrive at my conclusion.

Why does this reasoning lead to a wrong result?

Answer 1

This is a really cool variant on the Monte Hall "do you choose the other door" problem, or for bridge enthusiasts, the principle of restricted choice.

Let me rephrase the issue as follows: $A$ is presented with three independent fair-coin randoms (behind three "doors"). The rules of the game are that $A$ must present $B$ with two of those randoms by revealing two doors, and that further, he must reveal two doors with identical values (both heads or both tails). $B$, seeing the doors opened by $A$ (fort example, doors I and II), must decide whether to bet that the random behind third door matches the other two (getting, say, 2:1 odds) or is different (laying 1:2 odds). What should $B$ do?

The point is that if the third value is different, then $A$ was forced to open those two specific doors (just as in Bridge, if the opponent had a singleton J or Q he was forced to play that specific card). On the other hand, if all three values were the same, $A$ could equally well have opened doors I and III, or II and III (just as in Bridge, the opponent holding QJ could equally well have played the Q or J). So the chances of the restricted choice($A$ chose doors I and II because he was forced to) are, in this case, three times greater than the chances of the free choice; that is, the odds that the third door is has a different value behind it are 3:1.

Answer 2

However, suppose that I claim that the probability should be 1/2, and here is my reasoning: First, I point out that there are three coin tosses and only two possible outcomes for each toss. Therefore, at least two out of the three tosses are guaranteed to have the same result. I need only point out that the probability of the third toss having the same result is 1/2 to arrive at my conclusion.

Which toss is this third toss?   You know that "at least two tosses must be the same"; not that the "first two are the same".   These can be the first two, the first and last, the last two, or all three.   That is, the (equally)possible outcomes are:

$$\rm \{SSD, SDS, DSS, SSS\}$$

Answer 3

Therefore, at least two out of the three tosses are guaranteed to have the same result.

Those 2-of-3 elements are not a well defined random variable.

If you go through the formalities of constructing a well defined pair from the three elements, such as taking the smallest one in a predefined ordering, or uniform random selection from all pairs with the same result, the result of the remaining toss will not be an independent coin with probability 1/2.

The probability space of 3 independent coin tosses does not decompose as a Cartesian product of probability spaces (choice of pair) x (choice of outcome for that pair) x (outcome of 3rd toss). If it did then then (choice of pair) would be equivalent to a single coin toss with two outcomes, but there are 3 possible pairs.