### Finishing The Game

#### by Abhishek

##
via Coding Horror by Jeff Atwood on 12/31/08

In yesterday’s post, I asked this question:

Let’s say, hypothetically speaking, you met someone who told you they had two children, and one of them is a girl.

What are the odds that person has a boy and a girl?

Most people answer 50%.

Unfortunately, this isn’t correct.

This problem, although seemingly simple, is hard to understand. For cognitive reasons that are not fully understood, while our intuitions regarding *a priori* possibilities are fairly good, we are easily misled when we try to use probability to quantify our knowledge.

The key thing to bear in mind here is that **we have been given additional information**. If we *don’t* use that information, we arrive at 50% — the odds of a girl or boy being born to any given pregnant woman. That’s true insofar as it goes, but it’s the answer to a different, much simpler question, and certainly not the answer to the question we asked.

Our question contains additional information:

- The person has two children.
- One of those children is a girl.

We can use that information to come up with a better, more correct answer. We know this person has two children. What are all possible combinations of two children?

`BB, GB, BG, GG`

We also know that one of the children is a girl. This rules out one of those possible combinations of two children (BB), so we’re left with:

`GB, BG, GG`

Of the remaining three possibilities, *two* include girls.

`GB, BG`

Thus, **the odds of this person having a boy and a girl is 2 out of 3 or 66%**.

I noticed a few comments where people complained that the GB and BG possibilities are the same thing, and should have been reduced to

`BG/GB, GG`

Which equates to 1 out of 2 or 50%.

If you made this mistake, you’re in good company: so did Blaise Pascal, as the book The Unfinished Game: Pascal, Fermat, and the Seventeenth-Century Letter that Made the World Modern describes.

Here’s how Keith Devlin describes the famous letter:

In 1654, the gambler Antoine Gombaud, whose noble title was the Chevalier de Mere, apporached his friend Pascal with some questions about games of chance, including the problem of the unfinished game. After some thought, Pascal found a possible solution but was not completely sure his reasoning was correct. Accordingly, he sent his ideas to Fermat to see if his countryman agreed with the argument. The brief exchange of letters that ensued — and one letter in particular — represented one of the most profound advancements in the history of mathematical thought.

I’ll tell you one thing I learned from this book: **It’s amazing how many early advancements in math were based on gambling**. I guess it’s sort of the same historical relationship between video technology and pornography. Not that there’s anything wrong with that.

The “unfinished bet” I alluded to in my previous post title is the central topic of these letters between Blaise Pascal and Pierre Fermat. Here’s a modernized, slightly simplified version of it:

Two players, Harry and Ted, place equal bets on who will win the best of five coin tosses. In each round, Henry always chooses heads (H), and Ted always chooses tails (T). Suppose they are forced to abandon the game after three coin tosses, with Harry ahead 2 to 1. What is the fairest way to divide the pot?

Let’s enumerate all possible outcomes from the 2 remaining coin tosses.

`HH HT TH TT`

Only 1 these 4 possibilities allows Ted to win. Thus, if the game has to be abandoned, the pot should be split 3/4 to Harry and 1/4 to Ted.

But, since Harry is already ahead 2 to 1, you might argue that it’s nonsensical to consider all those possibilities; as soon as Harry gets that third head, the game is over. Thus, we only need to consider possibilities where the game would actually continue:

`H TH TT`

By this accounting, Harry would get 2/3 of the pot, and Ted 1/3.

Of course, this is wrong. By leaving the game “unfinished” and not enumerating every possibility — we’ve made a mistake. But how?

You don’t need to be a mathematician to prove this. I’m just a crappy programmer, and my crappy code can brute force this answer by simulating the results from thousands of games.

var rand = new Random(); var results = new Dictionary<string, int>(); int tosses = 2; for (int i = 0; i < 10000; i++) { string result = "HHT"; for (int toss = 0; toss < tosses; toss++) { result += (rand.Next(2) == 0) ? "H" : "T"; if (Regex.Matches(result, "H").Count == 3 || Regex.Matches(result, "T").Count == 3) break; } if (results.ContainsKey(result)) results[result]++; else results.Add(result, 1); } foreach (var item in results) { Console.WriteLine(item.Key + " : " + item.Value); }

`HHTTT` |
2,438 |

`HHTTH` |
2,457 |

`HHTH` |
5,105 |

**The unfinished games are not equally likely**. But the final results are definitely clear, and agree with what the finished games predicted: 75% for Harry, and 25% for Ted.

The funny thing about reading this book is recognizing I had already made a mistake awfully similar to the unfinished game once, when writing a card shuffling algorithm.

[advertisement] In charge of a mountain of Windows servers? PA Server Monitor to the rescue! Download the Free Trial! |

voçes são cagão