User:Tlogmer/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.

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.

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?"

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

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.

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

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

Here is a proof that there is zero probability that any given bill stays in the sack for all finite numbered days. Let w be the number of bills added each day, and consider some bill that is added on day $t_{0}$ , 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 $n-1$ , is

1-{\frac {1}{(w-1)n+1}}

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

P(t)=\prod _{n=t_{0}}^{t}\left(1-{\frac {1}{(w-1)n+1}}\right).

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

1+x\leq e^{x},

which holds for all x, gives

P(t)\leq \prod _{n=t_{0}}^{t}\exp \left(-{\frac {1}{(w-1)n+1}}\right)

\leq \exp \left(-\sum _{n=t_{0}}^{t}{\frac {1}{(w-1)n+1}}\right)

\leq \exp \left(-\sum _{n=t_{0}+1}^{t+1}{\frac {1}{(w-1)n}}\right)

=\exp \left(-{\frac {1}{w-1}}\sum _{n=t_{0}+1}^{t+1}{\frac {1}{n}}\right)

Here the sum diverges because it is a harmonic series. It follows that

\lim _{t\to \infty }P(t)=0.

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

\Pr \left[\bigcup _{i=1}^{\infty }A_{i}\right].

By Boole's inequality this probability is at most

\sum _{i=1}^{\infty }\Pr[A_{i}]=\sum _{i=1}^{\infty }0=0.

Historical notes

The Monty Hell problem is named after the unrelated Monty Hall problem. In the problem, Marilyn presumably refers to Marilyn vos Savant, who popularized the Monty Hall problem in her column in Parade Magazine.