Saturday, January 13, 2007
The Monty Hell Problem
The Monty Hell problem is a paradox in probability theory involving infinite sequences of actions. As described in a post in the usenet group rec.puzzles, the problem consists of choosing between two alternative strategies for banking your money while spending an eternity confined in Hell. The assumptions of the problem are that each day you are paid $10 in ten $1 bills, but must turn over $1 each day to the Devil to pay for the heat. You are not allowed to handle your money yourself, but instead must choose one of two bankers:
- Monty, who puts each day's bills in a large sack, then chooses one of the bills from the sack uniformly at random (including bills from previous days) to give to the Devil.
- Marilyn, who carefully removes one bill from the stack of ten bills to give to the Devil, and then places the remaining nine bills in her sack.
The goal is to maximize your wealth at the end of your eternal confinement, which occurs on a hypothetical day ω (see Transfinite number), which occurs after all finitely-numbered days.
(The problem is sometimes stated such that Marilyn removes nine bills and only puts one in the sack. Here, for simplicity, they remove the same amount of money daily.)
The paradox: Let us start with the obvious explanation why it doesn't make any difference which banker you choose: after t days, both Monty and Marilyn have 9t dollars. Since these quantities both grow without limit, either will give you infinitely many dollars in the end. There is another explanation that favors Marilyn, and depends on the assumption that dollar bills have individual identities, rather than just being counters for total wealth. Once any particular dollar bill is placed in the sack, on each and every subsequent day, there is a chance that Monty will take that particular dollar bill out again and give it to the Devil. Since there are an infinite number of days thereafter, it would seem that the probability that this will happen eventually is, in fact, 100% (and this intuition is upheld by probability theory, as shown in the appendix). Therefore, each dollar bill that Monty put into the sack will eventually be taken out. None of them will be in the sack on day ω! Monty almost always leaves you with nothing, and you are better off with Marilyn. This is true even though at any finite time Monty and Marilyn have the same number of dollar bills in their sacks.
The paradox is the apparent contradiction between these two answers. The paradox is particularly painful because the obvious explanation requires very little mathematics, making the second answer look suspiciously complex.