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
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) !
OpenEdition suggests that you cite this post as follows:
Arthur Charpentier (February 24, 2011). when Nuns or Hells Angels get in a plane. Freakonometrics. Retrieved September 19, 2024 from https://doi.org/10.58079/ouh5
hi 🙂
could you explain why this argument is necessary ?
FREE=which(OCCUPIED==FALSE)
I’d like to ask a question..
Could you explain why
FREE=which(OCCUPIED==FALSE)
this arguement is necessary ?
Définissons la fonction “Etat” par Etat(i)=1 si les i premières personnes à entrer dans l’avion occupent, en groupe, les i sièges qui leurs sont attribués (sans nécessairement que chacun occupe son siège. Dans le cas des Hells, si Etat(i)=1, chacun occupera son siège. Dans le cas des nonnes, si Etat(i)=1,on pourrait avoir que chacun occupe son siege, ou alors que personne n’occupe son sièges car alors les gens seraient distribués cycliquement), et Etat(i)=0 autrement.
On cherche Pr(Etat(i)=1). On a Pr(Etat(1)=1)=1/n.
Par les probabilités conditionnelles, on a
Pr(Etat(i)=1)=Pr((Etat(i-1)=1) x Pr(Etat(i)=1|Etat(i-1)=1)+Pr(Etat(i-1)=0) x Pr(Etat(i)=1|Etat(i-1)=0)
Maintenant, clairement, Pr(Etat(i)=1|Etat(i-1)=1)=1 et
Pr(Etat(i)=1|Etat(i-1)=0) = 1/(n-i+1)^2
(car pour “réparer” l’état i-1, il faut non seulement que le siège de la personen entrante soit déjà occupé (probabilité de 1/(n-i+1), mais qu’en plus, celle-ci (dans la formulation des nonnes, ou la première personne qui sera déplacée encore, dans celle des Hells) choisisse parmi les (n-i+1) restant le bon, avec encore une fois une probabilité de 1/(n-i+1), d’où le facteur 1/(n-i+1)^2.
Si on désigne par p(i) le terme Pr(Etat(i)=1), on a la récursion
p(1)=1/n
p(i)=p(i-1)+(1-p(i-1))/(n-i+1)^2
Par récurrence, on montre facilement que cela se simplifie à p(i)=1/(n-i+1).
On a donc p(n-1)=1/2.
here it is, with on top the nuns, and below the Hells Angels. The yellow point is the first passenger to get in. Dark points are either nuns or Hells,
Ok, now I understand why they are equivalent !
Nice !
RESPONSE: I was about to draw an animation to illustrate that, the idea is that seat with someone would be the same, on the color will change… maybe I should, because I start to understand that I was not that clear here. Anyway, I still have to work a bit on the calculation, to put down a proper derivation of that result. I am not a big fan of rewritting a post, but people usually don’t look at comment, so I prefer to avoid having an uncorrect post online. Thanks for your comments and your nice proof.
The first part of my first comment was just echoing your sentence:
“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)”
To be totally honest, I don’t see why these two problems are mathematically equivalent.
Well, I just reasoned with a tree: in the Hells Angels’ case, only the shy guy can be at the wrong seat. So we look at its place before I get in the plane. At each time, there are 3 possibilities: he can:
– find its right seat (p1);
– or sit on my seat (p2);
– or sit on one of the Hells Angels seat (p3).
At time (passenger) 1:
p1 = 1/n
p2 = 1/n
p3 = (n – 2)/n
Then at time 2 (conditionnaly on the fact that at the previous time he sat on one of Hells Angels’ seat):
p1 = 1/(n – 1)
p2 = 1/(n – 1)
p3 = (n – 2)/(n – 1)
And then we calculate the sum:
p2(1) +
p3(1)p2(2) +
p3(1)p3(2)p2(3) +
… +
p3(1)p3(2)…p3(n – 2)p2(n – 1)
Hello Arthur,
Nun’s and Hells Angels’ problems are not at all the same to me: suppose our scatter brained guy chooses a nun’s seat; then after the second passenger (the first nun) is entered in the plane, two people are wrong sat (because the nun is polite), a situation that can never occur in the Hells Angels’ case (I agree in that case there can be one person wrong sat at the most).
And we don’t know whether the nuns are polite or not among them: if a nun is already sat at another nun’s seat, would the first one leave her seat (I suppose she would, so the game works) ?
It’s funny you got the good result (in the Hells Angels’ case) by a wrong reasoning: p_n(i) is not equal to p_n(i – 1) times n – (i – 1) + 1 over n – (i – 1). If that equality were true, p_n(n – 2) would be equal to one third, which is quite low.
p_n(i) = p_n(i – 1) + (n – i)/(n(n- 1)) so
p_n(n – 1) = sum from i = 1 to n – 1 of (n – i)/(n(n – 1))
= 1/(n(n – 1)) times sum from i = 1 to n – 1 of i
= 1/(n(n – 1)) times (n-1)n/2
= 1/2
RESPONSE: Hi Olivier, I guess you’re right. I will keep your nice answer, and remove mine… And about the first part, we do not care which none is going to move. It will not change anything. And it is the same for Hells Angels. From my point of view (the last passenger to get in the plane), I do not care if
If you agree that from my point of view, all those problems are equivalent, then whatever we model, we”l get the same probability.
I don’t really understand this sentence: “the probability that it will be taken after the ith passenger’s entrance, that is the probability that he moves there while he was previsouly sitting in one Hells Angels seat, pn(i-1) times 1 over (n-i+1)”. May you explain it in an other way ?
RESPONSE: ok, let me work on it a little bit…
Your simulation assumes there are 100 seats for the first person to choose from. This is not evident in the question.
RESPONSE: you’re right… I should add that there are 100 seats in the airplane…