Talk:Monty Hell problem
|
|
| Contents |
(untitled)
Perhaps there will be disagreement over the categorization of this problem as falsidical. The classifications that were recently made in the Paradox article won't be changed till any discussion of this question has settled down, if ever. Dandrake 19:39, 15 Oct 2003 (UTC)
- I agree with you now. Looking over the explanation, I see that the rec.puzzles explanation had fooled me. Thanks for clearing that up. Perhaps we should de-emphasize the antimony status — the problem was fixed by cleaning up the axioms, right? Paullusmagnus 20:10, 15 Oct 2003 (UTC)
Right. They figured out how to talk about infinite processes without in some sense getting to infinity. And since the antinomy (gotcha -- ain't it hard not to write antimony?) is dead by more than a century, it doesn't deserve much attention, if any, in the article. The article would be better for some editing by whoever first gets around to it. Dandrake 23:56, 15 Oct 2003 (UTC)
The current version of Monty Hell problem says, "Considering both definitions, the solution favoring Marylin uses the first definition (and the use of physical money in the problem favors this interpretation), while the Moloch vs Monty argument uses the second. If only one of the two definitions is used, there is no contradication."
If this is correct, then we have a serious antinomy in probability theory, don't we? A function that is monotonically increasing and everywhere greater than zero (not to mention increasing without limit) gives us zero at infinity when analyzed with probability theory. This not just a little recreational problem; it is important enough that we ought to provide a reference to the published literature on the subject.
"...So it is tempting to assume that a similar failure of intution applies in this case, and that infinitely many probability-zero events might sum to a nonzero expected number of bills. Modern probability theory excludes this assumption, because it takes as an axiom that probabilities are additive even for countably infinite sets of events."
This raises two questions. First, the probability calculation makes no assertion about the amount of money in the bag. If you naively attempt to calculate the expected amount at infinity, you get zero times infinity, which is not zero or anything else.
All right, that's naive, as I said; you really want the infinite sum of (probability of a bill's being there times a bill's value (which is unity)). If the probability of each bill's presence is zero, the answer is obvious. But in fact, at no time is the probability zero for any bill whatever. Zero is a limiting value. Is it axiomatic that these limiting values can be simply summed over an infinite interval? Is there a theorem to that effect?
Perhaps the problem is that the summation of these limiting values is still too naive. What you actually want (sorry to be too hurried to write it in LaTeX) is the limit as t -> infinity of the sum of p(i,t)*v(i) for i = i to M(t). Where p(i,t) is the probability that bill i is in the bag at time t; v(i) is the value of bill i, which is unity; and M(t) is the number of bills in the bag at time t.
This is not a difficult limit to calculate, since it's precisely (identically, in the strict sense) the same as the simpleton's calculation of how much Monty or Marilyn has in the bag.
Dandrake 19:26, 16 Oct 2003 (UTC)
Let us compare the two approaches to calculating Monty's pile. The simpleton's analytic approach says that Monty's money <math>M(t) = 9t<math>. In the limit this is
<math>\lim_{t\to\infty} 9 t<math> which is, identically,
<math>\sum_{t=1}^\infty 9<math>, which is infinite.
The argument from probability is that the expected total in the bag at any time is
<math>\sum_{i=0}^n p(i)v(i)<math> where <math>p(i)<math> is the probability that bill <math>i<math> is in the bag, <math>v(i)<math> is the value of the bill, and <math>n<math> is the number of bills that have ever been added to the bag. The amount in the bag at the end of time is the limit of that quantity.
<math>v(i)<math> is present to emphasize that we are calculating an expectation. As it is a constant, and unity at that, it will be omitted from here on.
So far there is no problem. Even when there are (countably) infinitely many terms, the sum is valid in probability theory. Now, since <math>p(i)<math> is zero in the limit for all <math>i<math>, the conclusion is drawn that in the limit this is a summation of all zero terms, and the sum is zero.
This is a problem. In fact, <math>p(i)<math> is not a constant, but a function of time <math>p(i,t)<math>, which is nowhere zero. (One can formulate the problem with the function having zero value for <math>t < i/9<math> to represent the fact that the bill is not in the bag before it's placed there, but it is simpler to leave the function undefined for those values and set up the summation accordingly.)
Correctly, the money in the bag at the end of time is represented by
<math>\lim_{t \to \infty}\sum_{i=1}^{10t} p(i,t)<math>
The argument for Marilyn's method is, in effect, to replace that formula by
<math>\sum_{i=1}^\infty \lim_{t \to \infty} p(i,t)<math> .
Once this implicit step is brought into the open, it is clearly not valid.
If there is a reduction of the correct formula to a simple closed form, it hasn't been shown yet. Deriving that, and showing that the result is different from the simpleton's analytic formula, is an exercise for those who consider the paradox not to be falsidical. Dandrake 03:19, 17 Oct 2003 (UTC) (Corrected Dandrake 19:40, Oct 17, 2003 (UTC))
Since the reduction of the correct formula hasn't been shown yet, I'll show it: the summation reduces to 9t. Proof is left as an exercise for the reader, as is the computation of the limit. Dandrake 19:40, Oct 17, 2003 (UTC)
I'm pulling out everything below here and replacing it with a new discussion. Please be very wary of putting any of the arguments for the obvious solution back in as factual unless you can back up your intuitive reasoning about the set limit process with formal arguments (this does not mean substituting the numerical limit process and talking about that---everybody here agrees that the number of bills in the bag diverges). Populus 21:58, 17 Oct 2003 (UTC)
Solutions
One suggested solution is that it is better to bank with Marilyn than with Monty. With Marilyn, no bill that enters the sack ever comes out again, leaving you with infinite wealth upon your eventual release. With Monty, it can be shown that the probability that any particular bill stays in the sack forever is zero, which implies that the probability that there are any bills at all left in the sack when you leave Hell is also zero.
This contradicts the intuitive reasoning that the final total must be greater than any previous day's total because each day sees a net increase in the number of bills, creating a paradox.
An argument against this reasoning considers the bank account of Moloch, who provides the heat at no expense to himself, charging a dollar a day and keeping it all as profit. Every day till eternity, Monty's account is nine times as large as Moloch's. When Moloch becomes infinitely rich, so must Monty, who is nine times as rich.
In Quine's terminology the Monty Hell Problem may be classed as a falsidical paradox, meaning the its reasoning is flawed. (Before the introduction of formal, consistent ways of dealing with the infinite, it would have been an antinomy, pointing out the flaws in some conventional thinking about infinite quantities)
In this particular case, there are two natural ways to define the limit: as a set process in which each bill is tracked separately, and a bill remains "in the limit" only if it is never removed; or as a numerical process in which the total number of bills is tracked, and the limit is defined as the limit of the day-to-day balance. By the second process, Marylin and Monty clearly both add $9 to the sack each day. By the first process, one comes to the conclusion that Monty's bag is empty at the end of time. However, one comes to the same conclusion if one considers a sack where each bill is removed 100 days after it was put in. Clearly, the sack will always contain 100 days worth of bills, even though no bill remains there forever. The intuitive result, that Marylin and Monty are equally favorable choices, is the correct one.
Further discussion
A key step in the argument for Marilyn's approach is the "which implies". We have the true statement that the probability of any bill's staying in the account forever is zero; or more precisely, it converges to zero in the limit. From this we infer that the probability that anything will be left after infinite time is zero. This inference is invalid. For a simple counterexample, suppose that at time t one puts a bill with serial number t into a sack, and at time t+3 one takes it out again. Every bill eventually comes out of the sack, but that does not mean that the sack will become empty; at time t=100 bills 98, 99, and 100 are in the sack. These bills will all be gone by time t=103, but by that time, new bills will be in the sack, which clearly never becomes empty. Or a more practical example: just because all humans are mortal, we cannot conclude that humanity will eventually become extinct. Everyone dies, but that does not mean that there will be a time when everyone is dead.
Many such perfectly sensible inferences fail, when dealing with infinite processes. For instance, some whole numbers are even and some are not; hence there must be more whole numbers than even numbers; all the more so for perfect squares. But it has been known at least since the time of Galileo that the number of squares is the same as the number of whole numbers; see Galileo's paradox. Or see Hilbert's paradox of the Grand Hotel. So it is tempting to assume that a similar failure of intution applies in this case, and that infinitely many probability-zero events might sum to a nonzero expected number of bills. Modern probability theory excludes this assumption, because it takes as an axiom that probabilities are additive even for countably infinite sets of events.
The above argument may be disputed, however, on theoretical grounds. (As it is in the Talk page).
Regarding the Harmonic Series
If a bill is put into the bag at time 1, the probability that it is removed at time t is
- <math>{1\over 9t}\prod_{i=1}^{t-1} \big({1 - 1/9i }\big)<math>
The probability that it is removed eventually is
- <math>P = \sum_{t=1}^\infty {1\over 9t}\prod_{i=1}^{t-1} \big(1 - 1/9i \big)<math>
If there's any useful way in which this resembles a harmonic series, I don't see it. I also don't know how to show that P=1. I haven't seen any version of the article that successfully argues that each bill does eventually come out of the bag; all the arguments posted so far have been appears to authority or handwaving.
I think this article needs more facts and less argument.
Regarding the limit at infinity vs the value at infinity
- "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."
It seems that the distinction between "the probability that the bill is never removed" (P) and "the tendency as the number of days goes to infinity that the bill is not removed by that day" (<math>lim_{t \to \infty} P(t)<math>) is the matter of contention of the entire paradox. So in the proof of it, doesn't it seem useless to make that be the step that we gloss over? Without more substantial hand-waving than that found in the You can't multiply a zero probability by infinitely many elements section, I can't imagine anyone being prepared to accept these results. I am not qualified to comment on how to apply the axioms of probability theory, but the proof offered in the appendix does not stand on its own. The biggest thing I learned in my Calculus I class was that the distinction between the limit and the value is essential. (p.s. this is my first wikipedia adventure and I am finding it most enjoyable -- thanks! User_talk:galexander if I'm reopening an old debate that is settled to everyone's satisfaction)
Galexander 22:08, 13 Dec 2003 (UTC)
It's not glossing over (or at least it shouldn't be—if it looks like glossing over we might need to clarify the article further). Let A(t) be the event that the bill is not removed by time t. Let A be the event that it is never removed. Then A is a subset of A(t) for any t, so Pr[A] ≤ Pr[A(t)] for any t. But Pr[A(t)] goes to zero in the limit, so for any x > 0 there is some t for which Pr[A(t)] < x. It follows that Pr[A] is less than any positive x, which means that it's zero.
Populus 00:36, 14 Dec 2003 (UTC)
That looks fairly convincing but I'm having a hard time accepting that being &le ; a function for all values is the same as being equal to the limit in any sense. What you just claimed looks equivalent to: f ≤ 1/x for all x>0 and 1/x goes to 0 at the limit, therefore f = 0. It kind of makes sense but it reminds me of Zeno's paradox. How do you squeeze out of existence those infinitely many values between 1/(really big number) and 0? I can't say it's wrong but it doesn't pass my smell test.
Galexander 19:05, 14 Dec 2003 (UTC)
Maybe it would help to look at it backwards. Suppose I tell you that 0 <= f <= 1/x for all x. Clearly, f = 0 is a solution to this (infinite) set of inequalities. But perhaps there are other solutions? Suppose c > 0 is a solution. Then let x = ceiling(2/c). We then have c <= 1/x <= c/2, a contradiction.
So the answer to "how do you squeeze out the infinitely many values between 1/bi and 0" is that each 1/bigger squeezes out a few more, and that none survive being squeezed out by everybody (which is what we just showed). Populus 02:56, 16 Dec 2003 (UTC)
Re: Regarding the Harmonic Series
The formula
- <math>P = \sum_{t=1}^\infty {1\over 9t}\prod_{i=1}^{t-1} \big(1 - 1/9i \big)<math>
can be computed partially with the following QBasic program:
REM MONTY HELL PROBLEM DIM sum AS DOUBLE DIM summand AS DOUBLE DIM factor AS DOUBLE DIM prod AS DOUBLE DIM t AS LONG CLS sum = 0 prod = 1 FOR t = 1 TO 20971520 'modify this number at will IF RND < .0001 THEN PRINT "t="; t, "sum="; sum IF t > 1 THEN factor = 1 - 1 / 9 / (t - 1) ELSE factor = 1 END IF prod = prod * factor summand = 1 / 9 / t * prod sum = sum + summand NEXT PRINT sum END
These are the results:
| Number of days in hell | Probability that the first bill will have been removed by this time |
| 5 | 0.231508 |
| 10 | 0.285019 |
| 20 | 0.336479 |
| 40 | 0.384911 |
| 80 | 0.430155 |
| 160 | 0.472232 |
| 320 | 0.511278 |
| 640 | 0.547470 |
| 1280 | 0.580997 |
| 2560 | 0.61204915 |
| 5120 | 0.64080265 |
| 10240 | 0.66742666 |
| 20480 | 0.69207925 |
| 40960 | 0.71490247 |
| 81920 | 0.73603525 |
| 163840 | 0.75560164 |
| 327680 | 0.77371770 |
| 655360 | 0.79049093 |
| 1310720 | 0.80602084 |
| 2621440 | 0.82039960 |
| 5242880 | 0.83371253 |
| 10485760 | 0.84603863 |
| 20971520 | 0.85745106 |
When these data points are plotted on a graph, the resulting curve looks like it is going to approach 1 asymptotically. --AugPi 02:40, 5 Apr 2004 (UTC)
Suppose there is a monotonically decreasing series of positive numbers s1, s2, s3, s4, ... such that
- <math> \sum_{i=1}^\infty s_i = \infty, <math>
e.g. the harmonic series. Suppose that si is the probability that a certain bill is removed on day i. Then the probability that this bill has been removed by day t is
- <math> P_R(t) = \sum_{i=1}^t s_i \prod_{j=1}^{i-1} (1 - s_j) <math>
and the probability that it has not been removed by day t is
- <math> P_{NR}(t) = \prod_{i=1}^t (1-s_i) <math>.
It can be proved by mathematical induction that
- <math> P_R(t) + P_{NR}(t) = 1 <math>
for all t. Notice that
- <math> P_R(t) = \sum_{i=1}^t s_i P_{NR}(i-1) <math>.
Induction Basis:
- <math> P_R(1) + P_{NR}(1) = \sum_{i=1}^1 s_i P_{NR}(0) + \prod_{i=1}^1 (1-s_i) <math>
- <math> = s_1 P_{NR}(0) + (1-s_1) = s_1 + (1 - s_1) = 1. <math>
Notice that
- <math> P_{NR}(0) = \prod_{i=1}^0 (1-s_i) = 1. <math>
This is because the product of no factors is the multiplicative identity.
Induction Step: Assume that <math> P_R(t) + P_{NR}(t) = 1 <math>. Then what is the value of <math> P_R(t+1) + P_{NR}(t+1) <math> ?
- <math> P_R(t+1) + P_{NR}(t+1) = \sum_{i=1}^{t+1} s_i P_{NR}(i-1) + \prod_{i=1}^{t+1} (1 - s_i) <math>
- <math> = s_{t+1} P_{NR}(t) + P_R(t) + (1 - s_{t+1}) P_{NR}(t) <math>
- <math> = P_{NR}(t) [s_{t+1} + (1 - s_{t+1})] + P_R(t) <math>
- <math> = P_{NR}(t) + P_R(t) = 1 <math>
Therefore <math> P_{NR}(t) + P_R(t) = 1 <math> for all t, quod erat demonstrandum.
It is true for any x that
- <math> 1 + x \le e^x. <math>
These two functions are tangent to each other at point (0,1). Everywhere else the exponential function is greater than its linear approximation. This can be seen easily by plotting these two functions on a graph, e.g. graphing calculator. Therefore
- <math> 1 - x \le e^{-x} <math>
is also true, for all x.
Then
- <math> P_{NR}(t) = \prod_{i=1}^t (1-s_i) \le \prod_{i=1}^t e^{-s_i} = e^{-\sum_{i=1}^t s_i} <math>
But
- <math> \sum_{i=1}^\infty s_i = \infty <math>
as had been assumed earlier for the series si, so
- <math> P_{NR}(\infty) \le e^{-\infty} = 0. <math>
But it was proven above that
- <math> P_R(t) + P_{NR}(t) = 1 <math>
for all t, so that
- <math> P_R(\infty) = 1 <math>.
The formula
- <math>P = \sum_{t=1}^\infty {1\over 9t}\prod_{i=1}^{t-1} \big(1 - {1 \over 9 i} \big)<math>
can be expressed as
- <math> P = \sum_{t=1}^\infty s_t \prod_{i=1}^{t-1} (1 - s_i) = P_R(\infty) <math>
where
- <math> s_i = {1 \over 9 i} <math>
which is one-ninth of the harmonic series and whose sum is
- <math> \sum_{i=1}^\infty s_i = {1 \over 9} \sum_{i=1}^\infty {1 \over i} = {1 \over 9} \infty = \infty <math>
This means, given what was proven above earlier, that
- <math> P=1 \ <math>.
--AugPi 04:18, 5 Apr 2004 (UTC)
Hi all! I stumbled into this page by accident, and I'm just wondering a couple of things:
- The question seems to be, that "when you get out of hell, how many bills do you have". At the same time we're talking about infinity - if there is a day you get out, then the total days spent in is finite, and thus equal amout of cash in the sack in both scenarios.
- The "not one bill stays in the sack forever"-point makes me wonder, what difference does that make? If you look at the situation at any given point, there will always be bills that have not left the sack. For example, if we suppose the bills get mould after time and must be changed, maybe every 20 years. For each bill in your sack you get a new one. The fact that the bills aren't exactly the same doesn't change anything? You could argue that for each 10 bills you receive each day one "replaces" the one you have given away yesterday.
Ok, if I get answers to those, thank you! --62.237.40.154 14:05, 11 Jun 2004 (UTC)
- We formally define a "day at infinity" that occurs after all finite days. See ordinal number.
- This is a common confusion caused by thinking of bills as fungible. As explained in the text, if you think of them as individual physical objects, you have to explain how you can have a sack with infinitely many bills in it at the end when every particular bill that might be in the sack has already been removed. The more formal explanation is that it makes a difference whether you take the set limit first and then compute the size or compute the sizes of all the sets and then compute the limit; the problem is phrased to encourage the first interpretation, and the paradox comes from the fact that the two processes give different limits. Populus 18:43, 12 Jun 2004 (UTC)
I'll stick my nose in here and make what seems to me a very straightforward argument, which means that it's most likely either faulty or irrelevant. *grin* On day ω, you get out of hell. You may or may not get paid this day, it's uncertain. Let's assume you didn't, nor was a fee collected. You did get paid the day before, ω-1. You also got paid on ω-2, ω-3, and so on. On day ω-1, one bill was removed at random and you were paid 10 bills, all of which remained in the bag at the end, since no further cash was drawn. On day ω-2, one bill was removed at random and you were paid 10 bills, at least nine of which remained. The first ten have probability 1 of staying. The next ten have probability .9 of staying. If one continues on, one sees that you have 10+10(.9)+10(.9^2)+... bills in the bag. While the first bills had probability 0 of surviving, the bills near day ω had high probability of surviving. Even when you're in the realm of infinity, you can walk a finite distance, it's just that nothing in the finite will notice it since you're still in the realm of infinity. If you somehow step into the finite days, you can apply the finite day logic and then just take the steps back in the realm of infinity. Like I said, it seems straightforward to me, so it's probably either faulty of irrelevant, but I'd be interested in whatever criticisms may come of it. -FunnyMan 07:03, Jul 15, 2004 (UTC)
Short answer: limit ordinals like ω don't have predecessors, so there is no day ω-1. Populus 21:26, 11 Jan 2005 (UTC)
"You can't multiply a zero probability by infinitely many elements" proof attempt
Let a be a positive integer and P be the set of all positive integers. The probability that an arbitrary element <math>p \in P<math> equals a is: <math>\frac{1 \mbox{ (a=p)}}{\infty \mbox{ (size of P)}} = 0<math>
If we sum this probability over P (which is assumed valid since <math>P \subset \mathcal{Z}<math> is countable), we get that the size of <math>P \cap \{a\}<math> is zero.
Yet, we also clearly see <math>P \cap \{a\}=\{a\} \mbox{ as } \{a\} \subset P<math> and thus that the size is one. This is a contradiction. Hence, either the calculation of the probability or the sum of that probability was invalid.
Anybody see something wrong with that? I know I was a little sparse on the probability calculation, but it's pretty simple. -FunnyMan 20:52, Feb 2, 2005 (UTC)
- Whoops, I had some broken notation in there. It's fixed now. -FunnyMan 21:37, Feb 2, 2005 (UTC)
This problem hurts my brain, primarily the logic center. I'm thinking of being a math major/stat minor, but not after reading this! Since I can't make up my mind, I'm going to invalidate it in another way: An infinite amount of money is worthless because of inflation, so either way you go, infinite (worthless) or zero (poor), it doesn't really matter! :D DevastatorIIC 19:52, Jun 11, 2005 (UTC)