Monty Hell problem

:A different article treats the Monty Hall problem.

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 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 - rac{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 - rac{1}{(w-1)n+1} ight).

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

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} expleft(- rac{1}{(w-1)n+1} ight)

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

:leq expleft(- sum_{n=t_0}^{t} rac{1}{(w-1)n+1} ight)

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

:leq expleft(- sum_{n=t_0+1}^{t+1} rac{1}{(w-1)n} ight)

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

:= expleft(- rac{1}{w-1} sum_{n=t_0+1}^{t+1}rac{1}{n} ight)

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

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

Related Topics:
Diverges - Harmonic series

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

:lim_{t o infty} P(t) = 0.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

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

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

:Prleft.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

By Boole's inequality this probability is at most

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

:sum_{i=1}^{infty} Pr = sum_{i=1}^{infty} 0 = 0.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~