Monty Hell Problem The Paradox Attacks On The Second Solution

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 $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:

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.)

1 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.

Unfortunately, there is a less obvious explanation that favors Marilyn. This explanation depends on the assumption that the contents of Monty's sack on day ω is a set-theoretic limit of the contents on the preceding days, where the limit of a sequence of sets A₁, A₂, ..., is defined to contain some element x only if there is some number N such that x appears in A_n for each . Since it can be shown for any individual dollar bill x that the probability that it remains in the sack forever is zero (see proof below) and since there are only countably many bills, with probability 1 every bill is eventually removed from the sack. Under the assumption that your holdings at the end of time are a limit set defined in this way, 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, non-intuitive answer look suspiciously complex.

2 Attacks on the second solution

Because the second solution is so disturbing, many people attempt to resolve the paradox by finding an error in it. This section will describe some of these approaches, and explain why they are not supported by modern-day set theory and probability theory.

2.1 Everybody dies, but that doesn't mean someday no one will be alive

Consider the following variant of the "Monty" process, which eliminates the probabilities: on day 1, element 1 is placed in the sack. On day 2, element 2 is placed in the sack, and in general, on day t, element t is placed in the sack. Starting on day 101, we also remove elements; on day 101, we remove element 1, and in general, on day t+100 we remove element t. Since there are obviously 100 elements exactly in the sack from day 101 on, it would appear that there must continue to be 100 elements in the sack in the limit.

While it is true that the limit as t goes to infinity of the number of elements in the sack is 100, it is not true that the limit as t goes to infinity of the set of elements in the sack is a set of 100 elements. This is immediate from the definition of a limit of a sequence of sets: there is no element that stays in the sack forever, so the limit is the empty set.

A similar variant on the "Monty" process would be to put bills numbered 10n-9 through to 10n in the sack on day n, and then to take out the bill numbered n. Each bill will enter and leave the sack at determined times; although the number of bills in the sack will increase without limit over time, no identifiable bill can remain indefinitely in the sack.

The general rule is that just because every set in a sequence has some property, it doesn't necessarily mean that the limit (if it exists) also has that property. We can see this in the "Marilyn" process as well—the number of bills in Marilyn's sack on each day is finite, but the number of bills in the limit is not.

This is an astonishing property of set-theoretic limits, and it may surprise the reader to learn that the definition we have been using is in fact the definition universally used in mathematics. The reason this definition is used is that there is no good alternative: if we want to define the limit of the sets of elements of the bag to be some particular 100-element or potentially infinite set, we have to ask which elements are in this limit?

2.2 You can't multiply a zero probability by infinitely many elements

A second objection to the zero-return argument is that it cheats in going from the claim that, for each bill x, the probability that x remains in the bag is zero, to the claim that the probability that there is any bill that remains in the bag is zero. The argument is that, while it might be reasonable to sum up the zero probabilities of finitely many improbable events and conclude that their union also has zero probability, in this case where are summing infinitely many zeroes, and the product of infinity and zero is undefined.

Though there are axiomatizations of probability theory that do not allow summing over infinite sets of events, the usual set of probability axioms due to Kolmogorov explicitly provides countable additivity, which allows such sums as long as the infinite set is countable. So this particular objection requires---at minimum---adopting a non-standard approach to probabilities.

2.3 What if the Devil pays you out of his heating fee receipts?

The second solution assumes that each bill enters Monty's sack only once. But what if your $10 pay comes from the Devil, and he frugally funds some of that pay by recycling your heating fees? In this case each bill may enter the sack infinitely often, and it is not clear what the contents of the sack are in the limit (indeed, depending on how the Devil choose which bills to reuse and when, a limit set may not even exist).

This evades one version of the paradox, but it does not solve it in general. If the problem is explicitly stated so that the heating fees are not returned (say, because these bills are immediately fed to the infernal furnace), then the paradox returns.

3 Solution

The solution to the paradox is to observe that the two contradictory arguments are taking different limits. The obvious answer takes the limit of the number of bills in the sack; the less obvious answer takes the limit of the set of bills in the sack first, and counts them up afterwards. It is surprising, but not inconsistent, that these two different computations yield different answers.

Which answer is correct? This depends on how you interpret the problem. If you concentrate on the fate of individual bills, and are comfortable with set-theoretic limits, you are likely to take the set-theoretic limit first and conclude that Monty leaves you with nothing. This leaves you in the embarrassing situation of having to explain how you could have had increasing wealth forever but suddenly lose it all at the end, and the assurance that this outcome is consistent with modern mathematics may not make you feel much better. If you treat the individual bills as mere tokens representing your total wealth, you are likely to prefer the numerical limit and conclude that Monty leaves you with infinite wealth. But now you are in the still more embarrassing situation of having to explain how you came to hold a sack that contains infinitely many bills, every single one of which you previously lost forever.

The rec.puzzles discussion ultimately favored the zero-wealth outcome, but the issue continues to be contentious. For further discussion, see .

4 Appendix: Proof that each bill leaves the sack with probability 1

Here is a proof that the probability that a bill stays in the sack forever is zero. Let w be the number of bills added each day, and consider some bill that is added on day , where the first day is day 1. The probability that it remains in the bag on day n, given that it is present at the end of day , is

so the probability that it is not removed by day is then

If we let P be the probability that the bill is never removed, then we have P≤P(t) for any t, so if we can show that the limit of P(t) as t goes to infinity is 0, we will have that P is also 0.

Applying the inequality

which holds for all x, gives

Here the sum diverges because it is a harmonic seriesSee harmonic series (music) for the (related) musical concept. In mathematics, the harmonic series is the infinite series : It is so called because the wavelengths of the overtones of a vibrating string are proportional to 1, 1/2, 1/3, 1/4,. It diverges,. It follows that

We have just shown that for each individual bill, the probability that it is never removed tends towards 0. Let A_i be the event that bill i is never removed. Then the event that at least one bill is never removed has probability

By Boole's inequalityIn probability theory, Boole's inequality (also known as the union bound says that for any finite or countable set of events, the probability that at least one of the events happens is no greater than the sum of the probabilities of the individual events. this probability is at most

5 Historical notes

The Monty Hell problem is named after the unrelated Monty Hall problem. In the problem, Marilyn presumably refers to Marilyn vos SavantMarilyn vos Savant (born August 11, 1946) is an American newspaper columnist who deals with mathematical and logical puzzles, as well as more traditional self-help advice and solicitations for her opinion. Her column Ask Marilyn appears in Parade magazine, who popularized the Monty Hall problem in her column in Parade Magazine .

Paradoxes

<Hide>

Home > Monty Hell problem