# Monty Hall (oh no, not again)

Quite frequently, someone on the internet discovers the Monty Hall paradox, and become so enthusiastic that it becomes urgent to publish an article – or a post – about it. The latest example can be http://www.bbc.co.uk/news/magazine-24045598. I won’t blame them, I did the same a few years ago (see http://freakonometrics.hypotheses.org/776, or http://freakonometrics.hypotheses.org/775, in French).

My point today is that the Monty Hall paradox raise an important question, about information. How comes that something to sounds like non-informative can actually be extremely informative. I will not get back on the blue eyes paradox (see http://freakonometrics.hypotheses.org/1963, in French) or the exam paradox (see http://freakonometrics.hypotheses.org/2328, in French one more time), which are related to information, but not with a probabilistic approach. I will stay close to Monty Hall’s paradox today.

This morning, in my probability class, we were looking at a simple exercise (I say simple because it is only the second course of the session). The problem was the following

Consider an urn $A$, with 15 blue balls, and 10 red balls, and an urn $B$, with 10 blue balls, and 15 red balls. We select randomly one urn (with probability 50% for each urn).
We draw a ball, which turns out to be blue, and we put it back in the urn, Now, we draw a (second) ball. What is the probability that this (second) ball is blue?

Ready? Your first thought should be that since we put back the ball, after the first draw, it does not change the probabilities, right? So, why did we say that? It is necessary? (about the last question, yes, when something is mentioned in an exercise, we should use it).

Let’s forget about this second ball story, as an introduction to this problem. What was, actually, the probability for the first ball to be blue? Trivially, it was

$\mathbb{P}(\text{blue}\vert A)\cdot\mathbb{P}( A)+\mathbb{P}(\text{blue}\vert B)\cdot\mathbb{P}( B)$i.e.

$\frac{15}{25}\cdot\frac{1}{2}+\frac{10}{25}\cdot\frac{1}{2}=\frac{1}{2}$

Let us run a code to get that, using simulations:

> n=1000000
> set.seed(1)

First, let us draw the urn, randomly

> urn=sample(1:2,size=n,replace=TRUE)

Then, let us draw the first, and the second ball,

> urns=matrix(c(15,10,10,15),2,2)
> colnames(urns)=c("blue","red")
> sample.urn=(urns[urn,])
> prob.urn=sample.urn/apply(sample.urn,1,sum)
> u1=c("blue","red")[1+(runif(n)<prob.urn[,1])]
> u2=c("blue","red")[1+(runif(n)<prob.urn[,1])]

The probability that the first ball was blue is here

> sum(u1=="blue")/n
[1] 0.499953

and for the second one

> sum(u2=="blue")/n
[1] 0.499221

So, indeed, the probability to have a blue ball is 50%. Now, what was the question? Given that the first ball was blue, what it the probability that the second one is blue? Here, on our simulations, it is

> sum(u2[u1=="blue"]=="blue")/sum(u1=="blue")
[1] 0.5194088

Which is close to 52%.And if you run more simulations, you get

> f=function(seed){
+ set.seed(seed)
+ urns=matrix(c(15,10,10,15),2,2)
+ colnames(urns)=c("blue","red")
+ sample.urn=(urns[urn,])
+ prob.urn=sample.urn/apply(sample.urn,1,sum)
+ u1=c("blue","red")[1+(runif(n)<prob.urn[,1])]
+ u2=c("blue","red")[1+(runif(n)<prob.urn[,1])]
+ return(sum(u2[u1=="blue"]=="blue")/
+ sum(u1=="blue"))
+ }
> Vectorize(f)(1:20)
[1] 0.5194088 0.5200931 0.5203338 0.5192104 0.5196960 0.5206121 0.5195453
[8] 0.5184580 0.5203755 0.5200154 0.5196557 0.5179276 0.5188652 0.5204724
[15] 0.5197437 0.5209244 0.5205770 0.5208725 0.5206228 0.5190711

The probability is always close to 52%, and is (significantly) different from 50%.

Still not convinced that we have some information here that should be used? Imagine that in the first urn, we add 1 blue ball, and 24 red balls; and the opposite in the second one. In that case, if we say that the first ball was blue, it means that it is very likely that the urn chosen was the second one. Let’s look at by it running some simulations

> set.seed(1)
> urns=matrix(c(1,24,24,1),2,2)
> colnames(urns)=c("blue","red")
> sample.urn=(urns[urn,])
> prob.urn=sample.urn/apply(sample.urn,1,sum)
> u1=c("blue","red")[1+(runif(n)<prob.urn[,1])]
> u2=c("blue","red")[1+(runif(n)<prob.urn[,1])]

As before, the probability that the second ball is blue is 50% (because of the symmetry actually)

> sum(u2=="blue")/n
[1] 0.500362

But if I tell you that the first one was blue, the probability that the second one is blue becomes

> sum(u2[u1=="blue"]=="blue")/sum(u1=="blue")
[1] 0.9236433

So even if – somehow – we do not change much by replacing the ball in its urn, we do have here some information, since it was mentioned that the ball was blue. And we should use it. Again, the important point is that the sentence was not “we draw a ball and we put it back”, but “we draw a blue ball, and we put it back”. Now, it we do the maths, everything become simple, and clear (as usual).

The question is here to compute

$\mathbb{P}(B_2=\text{blue}\vert B_1=\text{blue})$

and according to Bayes formula, it is

$\frac{\mathbb{P}(B_2=\text{blue}\cap B_1=\text{blue})}{\mathbb{P}( B_1=\text{blue})}$

Now, to compute those two probabilities, we have to condition on the urn,

$\mathbb{P}({\color{red}\bullet})=\mathbb{P}({\color{red}\bullet}\vert A)\cdot\mathbb{P}( A)+\mathbb{P}({\color{red}\bullet}\vert B)\cdot\mathbb{P}( B)$

Given the urn, since we replace the ball,

$\mathbb{P}(B_2=\text{blue}\cap B_1=\text{blue}\vert\text{urn})=\mathbb{P}(B_2=\text{blue}\vert\text{urn})\cdot\mathbb{P}(B_1=\text{blue}\vert\text{urn})$

i.e.

$\mathbb{P}(B_2=\text{blue}\cap B_1=\text{blue}\vert\text{urn})=\mathbb{P}(B_1=\text{blue}\vert\text{urn})^2$

So if we substitute numerical probabilities to get a blue ball in the previous formula, we get

$\frac{\displaystyle{\frac{1}{2}\left(\frac{15}{25}\right)^2+\frac{1}{2}\left(\frac{10}{25}\right)^2}}{\displaystyle{\frac{1}{2}\left(\frac{15}{25}\right)+\frac{1}{2}\left(\frac{10}{25}\right)}}$

which not the same as

$\frac{1}{2}\left(\frac{15}{25}\right)+\frac{1}{2}\left(\frac{10}{25}\right)$

Here, we get

> {(15/25)^2+(10/25)^2}/((15/25)+(10/25))
[1] 0.52

which confirms our empirical 52%, and note that in the second case (where there was only 1 blue ball in one urn, and 24 in the second one)

> {(24/25)^2+(1/25)^2}/((24/25)+(1/25))
[1] 0.9232

which again is close to the empirical 92.3% we got.

I strongly believe that the mis-intuition we might have is close to the one we can observe in Monty Hall paradox. And unless you write things properly, it is difficult to conclude anything….

PS [48  hours later] thanks @mikeandallie for the animated version of my post

# when Nuns or Hells Angels get in a plane

Today, at lunch, Matthieu told us a nice story (or call it a paradox if you like) about the probability to find you seat empty when you get in a place.

• a plane full of nuns

Assume that you are in the line to get in the airplane, you are the 100th in the line. The first one is scatter brained, he has his head in the clouds, and when he get in the airplane, he cannot remember where he should seat. His strategy is then extremely simple: he seats randomly in the plane. So he picks up randomly a seat, and he waits.

Then come 98 nuns (one by one). And nuns are extremely polite: if there is someone in their seat (the one that is on the ticket they have) then they do not complain, and pick up another seat randomly (among those available, of course). Then you arrive. The question is simple: what is the probability that someone is seated at your seat ?

Any idea…?

Maybe I should give more time to do the maths… and tell another story…

• a plane full of Hells Angels

Consider almost the same problem as the one mentioned above. Except that now, it is not 98 nuns that are getting in the plane, but 98 Hells Angels. So the problem here is that Hells Angels are slightly less polite than nuns. When they find someone seating on the seat they should have, they do not shyly move to another seat, but they grunt and then our scatter brained man (who is actually seating in their seat) has to move somewhere else. And the question is the same: you are the 100th person to get in the plane, what is the probability that someone is seated at your seat ?Any idea….?

The important point is that the problem is exactly the same (at least from a mathematical point of view, maybe not for the stewardess, or from the guy who enter first in the plane). The point is that, at each time, there could be only one person (or less) seating in a seat which is not his or hers (in the sense that if we compare the list of the passenger at any time, and the list of seats taken, there should be only one – or less – difference). The difference in the two story is that in the first case, it will be a nun, while in the second one, it will be our shy guy.

• Let us run simulations

If we do not see how to get that probability analytically, let us run some R code,

> set.seed(1)
> n=100; TEST=rep(NA,100000)
> for(s in 1:100000){
+ OCCUPIED=rep(FALSE,n)
+ OCCUPIED[sample(1:n,size=1)]=TRUE
+ for(j in 2:(n-1)){
+ FREE=which(OCCUPIED==FALSE)
+ if(OCCUPIED[j]==TRUE){OCCUPIED[sample(FREE,size=1)]=TRUE}
+ if(OCCUPIED[j]==FALSE){OCCUPIED[j]=TRUE}
+ }
+ TEST[s]=OCCUPIED[n]==TRUE
+ }
> mean(TEST)
[1] 0.49878

Here, we clearly see that the problem is the same (either with nuns or Hells Angels): we do not care about who will change his/her seat, but we just look at seats that are available… So the program is valid for the two problems (and the solution will then be the same). Another point is that the probability looks extremely simple: one over two !

• an analytical expression

Consider the Hells Angels problem (for notations). Let denote the probability that, at time , our shy guy is sitting in my seat. When he gets in the plane, the probability that he gets to my seat is

Then, the probability that, after ith passenger’s entrance, our guy is sitting in my own seat is (since the initial proof was not correct, I remove it, see below for a nice proof) One can get that

So, we can get the probability that, when I get in, our guy is sitting in my own seat as

Hence, there is one chance out of two that my seat will be free… (which is what we got with Monte Carlo simulations).

But a faster proof is to observe that, in the Hells Angels case, our guy will be kicked out until he reaches either his seat, or mine. Since those two events are equiprobable, there is one chance out of two that he seats in my seat (and since no Hells Angel will seat in mine, only this first guy can). So the probability that someone is in my seat when I get in is one half.

Nice isn’t it ? And thanks Matthieu for the problem  (with his friend Claude’s solution with the Hells Angels, and Olivier and Renaud for their comments) !

# Probabilities, and opening doors (or boxes)

Recently, while we were in the car to Québec city with some PhD students, someone mentioned  the Monty Hall paradox, and we discussed possible extensions… The Monty Hall paradox is usually presented from tv show,

Craig F. Whitaker wrote the problem as follows, in Parade Magazine, September 1990, « Suppose you’re on a game show, and you’re given the choice of three doors: Behind one door is a car; behind the others, goats. You pick a door, say No. 1, and the host, who knows what’s behind the doors, opens another door, say No. 3, which has a goat. He then says to you, “Do you want to pick door No. 2?” Is it to your advantage to switch your choice? ». Actually, Bertrand proposed the same problem, but with boxes instead of doors…. but the problem was the same.

Assume that the candidate chooses door 1 (without loss of generality since the problem is clearly symmetric).  The probability that the car is behind door 2 is . The animator can either open door 2 or door 3:

• if the car is behind door 3, he has to open door 2,
• if the car is behind door 2, he has to open door 3,
• if the car is behind door 1, he can open door 2 or 3, and we assume that the opening is equiprobable,

Assume that the animator says “the second box is empty”, what should the candidate do ?
To formalize the problem let  denote the event that the car is behind door , and  the event that the animator opens door . So, if he opens door 2, the probability that the car is behind door 3 is

where

from the previous discussion, since he cannot open door 1 (the candidate chose it) and the cannot open door 3 (since the car is behind). Further

from equiprobability. And for  we get, similarly

Thus,

while

So the optimal strategy is to open the third door (even if I chose the first one)… It is usually seen as a paradox, but if you consider a much larger number of doors (say 4),

and that the animator opens 2 doors, then should we still change, and open the door that is still closed ? The higher the number of doors, the higher the probability to have something behind the other door…

For instance, with 4 doors, or boxes, if the candidate still chose the first door, and that the animator opens doors 2 and 3, then, the probability that the car is behind the fourth one is

i.e.

that appears at the denominator since we focus on the pair ) while

Once again, we have that

i.e. the opening of a doors bring us no information about our choice, but it will after conditional probability for the remaining door.
More generally, with n doors, if the animator opens  doors,

then

while

And here the result is even more intuitive: we have to open the door that was left closed. Actually, it is possible to see that it can be extend to the case where the are  doors (or boxes), the candidate chooses  doors, and the animator opens  (out of the  remaining doors). Then, behind each door chosen by the candidate, the probability does not change

where i goes from 1 to , while

where i goes from  to .

# Quand peu d’information donne énormément d’information

Une petite histoire empruntée à Alfred (et Nicolas1) suite au repas de mardi, à l’X. Un explorateur débarque un jour sur une petite île, perdue au milieu des mers. Cette île est un peu particulière: elle est peuplée de personnes ayant soit les yeux bleu, soit les yeux noirs (et tout le monde sait qu’il n’y a pas d’autre alternative). Et sous aucun prétexte personne ne doit connaître la couleur de ses propres yeux, sinon la légende dit qu’il doit se suicider avant le coucher du soleil (du jour où il l’apprend). Et s’ils ne le font pas, ils se retrouvent maudit jusqu’à la huitième génération. Cette île vivait en parfaite harmonie depuis plusieurs siècles, lorsque un explorateur débarqua. Il y avait alors 60 habitants sur cette île.

Bref, comme le veut la coutume, notre explorateur doit tenir un discours devant ses hôtes. Ne sachant trop que dire, il ne trouve rien d’autre à dire que de s’étonner de voir à l’autre bout du monde un île avec des habitants aux yeux bleus comme les siens (la légende lui avait racontée auparavant, de manière à éviter toute gaffe).
Deux mois plus tard, tous les habitants de l’île sont morts !
Quoi de plus étrange n’est-ce pas… ? Il n’a pourtant pas dit grand chose, si ce n’est une trivialité, à savoir qu’il y a des personnes aux yeux bleus sur l’île (ce que tout le monde devait savoir car s’ils ne connaissaient pas leur propre couleur d’yeux, ils pouvaient observer celle des autres). Pourtant cette micro-information semble avoir suffit à ce que les habitants en déduisent la couleur de leurs yeux !
En effet, le lendemain du discours, tout le monde s’est fait la réflexion suivante “d’après le discours de l’explorateur, il y a au moins une personne aux yeux bleus sur l’île. Or s’il était seul, il se serait rendu compte que tout le monde a des yeux noirs, et donc il aurait du se suicider dans la nuit. S’il ne s’est rien passé, c’est qu’il y a au moins deux personnes dans l’île avec des yeux bleu. Si quelqu’un s’est suicidé, c’est que j’ai les yeux noirs, et je dois me suicider avant le coucher du soleil“. Le deuxième jour, si tout le monde est encore en vie, tout le monde se fait la réflexion suivante “comme personne ne s’est suicidé, il y a au moins deux personnes aux yeux bleus sur l’île. Mais s’ils n’étaient que deux, chacun devrait penser que l’autre est le seul, et donc maintenant il sait qu’il est le second. Ils aurait du se suicider dans la nuit. S’il ne s’est rien passé, c’est qu’il y a au moins trois personnes dans l’île avec des yeux bleu. Si deux personnes se sont suicidé, c’est que j’ai les yeux noirs, et je dois me suicider avant le coucher du soleil“. Etc (je dois continuer ?). Bref, au plus tard, on arrive 60 jours après le discours du navigateur, et si tout le monde est encore en vie, c’est que  tout le monde se fait la réflexion suivante “comme personne ne s’est suicidé, il y a au moins soixante personnes aux yeux bleus sur l’île, c’est à dire que tout le monde a les yeux bleu. Je dois donc me suicider ce soir“.
Pourtant l’explorateur n’a pas franchement donné d’information… et pourtant cette information a suffi à décimer l’île ! Étonnant non ?
1 Nicolas avait raconté une version beaucoup plus connue, que l’on peut retrouvé dans tous les classiques sur les énigmes sous le titre des cocus de Bagdad. L’histoire est assez proche, avec un calife à Bagdad qui, jugeant immoral l’adultère dicte une loi qui stipule que toute femme convaincue d’adultère sera étranglée par son propre mari le lendemain matin même de la découverte par le  mari de la faute. Il faut ajouter que tous les maris voient si leurs voisins sont cocus ou pas, mais ils sont incapables de voir si leur femme les trompe… Et le calife a eu la mauvaise idée de dire que certains hommes étaient cocus… moralité, au bout de quelques jours toutes les femmes qui ont trompé leur mari finissent égorgées. Moralité, il n’y a pas besoin de beaucoup d’information pour agir de manière efficiente…