## when Nuns or Hells Angels get in a plane

By arthur charpentier on Thursday, February 24 2011, 17:24 - mathematics - Permalink

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

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

> 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

- 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

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) !

## Comments

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...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...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- - several nuns will move around
- - one nun moves (while the other(s) remain seated)
- - the first guy has been required to move

If you agree that from my point of view, all those problems are equivalent, then whatever we model, we''l get the same probability.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)

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.

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

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.