Serving the Quantitative Finance Community

 
User avatar
Wilbur
Topic Author
Posts: 0
Joined: August 12th, 2004, 7:39 pm

Airplane Passengers

December 21st, 2004, 2:07 pm

100 people are in line to board Airforce One. There are exactly 100 seats on the plane.Each passenger has a ticket. Each ticket assigns the passenger to a specific seat. The line of passengers boards Airforce 1, one at a time.GW is the first to board the plane. He cannot read, and does not know which seat is his.In order to cover up his inability, he picks a seat at random and pretends that it is his proper seat.The remaining passengers board the plane one at a time. They all know that GW cannot read, but none of them has the guts to point it out, so they play along with GW.If one of them finds their seat empty, they will sit. If they find that their seat is already taken, they will pick a seat at random.This continues until everyone has boarded the plane and taken a seat.What is the probability that the last person to board the plane sits in their proper seat?What is the expected number of people sitting in their proper seats?
 
User avatar
zerdna
Posts: 1
Joined: July 14th, 2002, 3:00 am

Airplane Passengers

December 21st, 2004, 5:02 pm

is it by any chance P(last passenger gets last seat)=99/100E(number of passengers with their seats)=49.51 ?it seems simple but the answer is hard to believe
Last edited by zerdna on December 20th, 2004, 11:00 pm, edited 1 time in total.
 
User avatar
PlainVanilla
Posts: 0
Joined: June 24th, 2004, 8:46 am

Airplane Passengers

December 21st, 2004, 5:20 pm

50/50 or 1/2 that he sits on the proper seat. (The solution is much like- what the probability that you see a dinosaur . answer 50/50... Ok, this part is a joke).For the second part I would rather write 100- sum(i from 2 to 100)(1/i)=95. But this is a complete guess
 
User avatar
alexandreC
Posts: 0
Joined: June 9th, 2004, 11:35 pm

Airplane Passengers

December 21st, 2004, 5:57 pm

humm for a first and intuitive guess,P(last passenger gets his own sit)=1/2E(number of passengers with their seats) = about 95A
Last edited by alexandreC on December 20th, 2004, 11:00 pm, edited 1 time in total.
 
User avatar
alexandreC
Posts: 0
Joined: June 9th, 2004, 11:35 pm

Airplane Passengers

December 21st, 2004, 5:58 pm

repeated post deleted
Last edited by alexandreC on December 20th, 2004, 11:00 pm, edited 1 time in total.
 
User avatar
zerdna
Posts: 1
Joined: July 14th, 2002, 3:00 am

Airplane Passengers

December 21st, 2004, 6:26 pm

agreed, 0.5 is correct
Last edited by zerdna on December 20th, 2004, 11:00 pm, edited 1 time in total.
 
User avatar
Aaron
Posts: 4
Joined: July 23rd, 2001, 3:46 pm

Airplane Passengers

December 22nd, 2004, 2:20 am

Let P(n) be the expected number of passengers sitting in their correct seats, if there are n seats and passengers. We want P(100).P(1) = 1. With only one seat, GW has to pick the right one. With n seats, think of GW picking one person in line (including himself) at random. If he picks himself (1 chance in n) everyone gets their correct seat. If he picks the kth person in line (k = 2 to n), 2 people are in the wrong seats (GW and person k) and k - 2 (the ones between GW and person k) are in the correct seats. The problem is now identical to the original, except that there are only n - k seats and passengers and if the first passenger picks the "correct" seat (GW's) it doesn't count as correct so you get only n - k - 1 additional passengers in the right seats instead of n - k.Therefore, P(n) 1 (the chance GW picks his own seat) plus 1/n (for each possible k) times the sum of k - 2 + P(n - k) - 1/(n - k + 1) from k = 2 to n. This makes P(n) approximately equal to n - (e - 1)*ln(n), or 92 for n = 100. I also agree the last passenger's chance is 1/2. Let Q(n) be the chance the last passenger gets her own seat if there are n seats and passengers. Q(2) is obviously 0.5. Assume Q(k) = 0.5 for k = 2 to n - 1. There are three possible things GW can do: pick his own seat (probability = 1/n, now the chance the last passenger gets his own seat is 1), pick the last passenger's seat (probability = 1/n, now the chance the last passenger gets his own seat is 0) and pick any other seat (probability (n-2)/n, now the chance the last passenger gets his own seat is 0.5). This clearly averages to 0.5.
Last edited by Aaron on December 21st, 2004, 11:00 pm, edited 1 time in total.
 
User avatar
alexandreC
Posts: 0
Joined: June 9th, 2004, 11:35 pm

Airplane Passengers

December 22nd, 2004, 12:34 pm

Excelent reasoning, by Aaron.QuoteOriginally posted by: AaronThis makes P(n) approximately equal to n - (e^n - 1)*ln(n), or 92 for n = 100. the aproximation formula i got was(of course, we can neglect the 1/n term, for n big)this gives 93.36 for n=100, just a bit different from my earlier 95 (computed with no help of machines)Alex
Last edited by alexandreC on December 21st, 2004, 11:00 pm, edited 1 time in total.
 
User avatar
Aaron
Posts: 4
Joined: July 23rd, 2001, 3:46 pm

Airplane Passengers

December 22nd, 2004, 1:57 pm

I had a typo (since corrected) in my message, the e^n should be merely e. Now the difference in our formulae is I have n - 1.71828*ln(n) and you have n - 1.4427*ln(n).I will double check my approximation.
Last edited by Aaron on December 21st, 2004, 11:00 pm, edited 1 time in total.
 
User avatar
alexandreC
Posts: 0
Joined: June 9th, 2004, 11:35 pm

Airplane Passengers

December 22nd, 2004, 2:28 pm

QuoteOriginally posted by: AaronI had a typo (since corrected) in my message, the e^n should be merely e. Now the difference in our formulae is I have n - 1.71828*ln(n) and you have n - 1.4427*ln(n).I will double check my approximation.Its ok if our aproximations lead to different formulas, as my reasoning was different from yours.(I made approximations earlier on in the exercise, compared to you - so i am quite positive your approximation is better than mine.)Alex
Last edited by alexandreC on December 21st, 2004, 11:00 pm, edited 1 time in total.
 
User avatar
zerdna
Posts: 1
Joined: July 14th, 2002, 3:00 am

Airplane Passengers

December 22nd, 2004, 3:11 pm

all right, i'll try to redeem my yeasterday's the "tough day after christmas party" post by giving i think an easier solution for the first part. The following should be obvious -- when the last guy comes in, there could be only two empty seats -- #1(Georges) or his own #100. Empty seat could not be say #10, because othewise the number 10 guy would have taken it. Since everyone whose seat was ever taken could have sat in GW seat with the same probability as in #100, the last will see his seat vacant in half of the cases and in half he will seat at GWs.
Last edited by zerdna on December 21st, 2004, 11:00 pm, edited 1 time in total.
 
User avatar
Aaron
Posts: 4
Joined: July 23rd, 2001, 3:46 pm

Airplane Passengers

December 22nd, 2004, 3:51 pm

While two approximations can differ and both be correct, in a problem like this we should agree in the limit. I actually computed the numbers in Excel, and we are both wrong.My exact recursive fomula was:which can be rewritten as:using the approximations that the sum of 1/k from 1 to n is about equal to ln(n+.5) - ln(0.5) and the sum from ln(k) from 1 to n is about n*(ln(n)-1); and assuming P(n) is of the form n - a*ln(n), we get:which I convinced myself last night had a stable solution at a = e - 1. However, I when I checked it in Excel, that turned out to be false. [n-P(n)]/ln(n) increases slowly and I can't find an obvious limit. However, the answer of 92 for n=100 is still accurate.
Last edited by Aaron on December 21st, 2004, 11:00 pm, edited 1 time in total.
 
User avatar
Aaron
Posts: 4
Joined: July 23rd, 2001, 3:46 pm

Airplane Passengers

December 22nd, 2004, 10:52 pm

I realized the calculation can be simplified if I wait even longer to approximate. I now agree with AlexandreC's first approximation of 95.Using my logic, but continuing with the analysis gives a simple:This is exact. A closed form approximation is P(n) = n - ln(n-.44) + ln(0.56). The exact answer for P(100) is 94.82. The solution is easy to explain (once you've got it). Write it as:(1 - 1/1) + (1 - 1/2) + (1 - 1/3) + . . . + (1 - 1/(n-1)) + 1 There are n 1's, which add up to n, and I've subtracted 1/k for k = 1 to n-1. The first term is zero, so I can rewrite this as:(1 - 1/2) + (1 - 1/3) + . . . + (1 - 1/n) + 1/nThese are the probability that each person will get the correct seat, starting from the back of the line (1 - 1/2 = 1/2), up to the person standing behind GW (she misses only if GW picks her seat, with probability 1/n), to GW (1/n of picking the correct seat).
Last edited by Aaron on December 22nd, 2004, 11:00 pm, edited 1 time in total.
 
User avatar
Aaron
Posts: 4
Joined: July 23rd, 2001, 3:46 pm

Airplane Passengers

December 22nd, 2004, 11:16 pm

QuoteOriginally posted by: zerdnaall right, i'll try to redeem my yeasterday's the "tough day after christmas party" post by giving i think an easier solution for the first part. The following should be obvious -- when the last guy comes in, there could be only two empty seats -- #1(Georges) or his own #100. Empty seat could not be say #10, because othewise the number 10 guy would have taken it. Since everyone whose seat was ever taken could have sat in GW seat with the same probability as in #100, the last will see his seat vacant in half of the cases and in half he will seat at GWs.Redemption indeed, this is a very clear solution. However, I would make one thing explicit: once someone picks either GW's seat or #100, the game is over. If she picks GW's seat, passenger 100 will get his own seat. If she picks passenger 100's seat, passenger 100 will never get his own seat. Although we don't know which passenger will make this choice, it could be anyone from GW to passenger 99, we know that whoever does make it has equal chances of each choice.I know zerdna knows this, but he chose to leave it implicit, which confused me when I first read it.
 
User avatar
zerdna
Posts: 1
Joined: July 14th, 2002, 3:00 am

Airplane Passengers

December 23rd, 2004, 12:51 am

Aaron is being accurate of course, and i indeed thought it's very obvious. I guess what's important in this solution is that from prospective of the last guy there is a complete symmetry in the game between the only two seats available to him.