bonanova Posted February 7, 2011 Report Share Posted February 7, 2011 Peter Winkler's charming puzzle of the lost boarding pass, recently posted admits to an interesting generalization, which follows. Same setup - 100 seats, 100 passengers. First passenger to board, for whatever reason, sits in a randomly chosen seat. Subsequent passengers take their assigned seats if they are available, else choose other seats, also chosen at random. How well does this process do in placing passengers in their correct seats? We know the answer for the last [100^{th}] passenger to board. What about the others? In general, if we don't know where Bob is in the boarding line, only that he's not the first to board, what is his expectation for getting his assigned seat? Related question: What is the expected number of passengers [out of 100] that will end up in their assigned seats? Quote Link to comment Share on other sites More sharing options...

0 HoustonHokie Posted February 8, 2011 Report Share Posted February 8, 2011 If you know which position you are in line, it's pretty easy to determine your probability of getting the right seat. Assume passengers are numbered 1 to N, with passenger 1 being the guy who lost his boarding pass. If you define P(n) as the probability that passenger n gets his correct seat, then: P(1) = 1 / N P(2) = (N - 1) / N P(3) = (N - 2) / (N - 1) ... P(N) = 1 / 2 (which was demonstrated in the previous puzzle). If you don't know which position you are in line, then your individual expectation of getting your correct seat is the average of P(2) -> P(N), which approaches 1 for large values of N. For N = 100, the expectation is 0.9577 for the random passenger. Call this value P(avg). The expected total number of passengers seated correctly is 1 / N + P(avg) * (N - 1). The 1 / N term describes the first passenger and the P(avg) * (N - 1) describes all the rest. For the case where there's 100 passengers, 94.82 are expected to be seated correctly. Again, as N gets large, the ratio of the expected number of passengers seated correctly to N approaches 1. Intuitively, this makes sense, because even though the first passenger is increasingly likely to take the wrong seat as N increases, he is also increasingly likely not to take "your" seat, especially if you're near the front of the line. Quote Link to comment Share on other sites More sharing options...

0 Guest Posted February 8, 2011 Report Share Posted February 8, 2011 0 The flight was later cancelled Quote Link to comment Share on other sites More sharing options...

0 bonanova Posted February 10, 2011 Author Report Share Posted February 10, 2011 If you know which position you are in line, it's pretty easy to determine your probability of getting the right seat. Assume passengers are numbered 1 to N, with passenger 1 being the guy who lost his boarding pass. If you define P(n) as the probability that passenger n gets his correct seat, then: P(1) = 1 / N P(2) = (N - 1) / N P(3) = (N - 2) / (N - 1) ... P(N) = 1 / 2 (which was demonstrated in the previous puzzle). If you don't know which position you are in line, then your individual expectation of getting your correct seat is the average of P(2) -> P(N), which approaches 1 for large values of N. For N = 100, the expectation is 0.9577 for the random passenger. Call this value P(avg). The expected total number of passengers seated correctly is 1 / N + P(avg) * (N - 1). The 1 / N term describes the first passenger and the P(avg) * (N - 1) describes all the rest. For the case where there's 100 passengers, 94.82 are expected to be seated correctly. Again, as N gets large, the ratio of the expected number of passengers seated correctly to N approaches 1. Intuitively, this makes sense, because even though the first passenger is increasingly likely to take the wrong seat as N increases, he is also increasingly likely not to take "your" seat, especially if you're near the front of the line. 94.82 - that's what I got. Some other expectations for correct seating as a function of N: ------+--------------- 10 71.64% 100 94.82% 1000 99.24% 10000 99.89% 100000 99.99% N expected Quote Link to comment Share on other sites More sharing options...

## Question

## bonanova

Peter Winkler's charming puzzle of the lost boarding pass, recently posted

admits to an interesting generalization, which follows.

Same setup - 100 seats, 100 passengers. First passenger to board, for whatever

reason, sits in a randomly chosen seat. Subsequent passengers take their assigned

seats if they are available, else choose other seats, also chosen at random.

How well does this process do in placing passengers in their correct seats? We know

the answer for the last [100

^{th}] passenger to board. What about the others?In general, if we don't know where Bob is in the boarding line, only that he's

not the first to board, what is his expectation for getting his assigned seat?

Related question: What is the expected number of passengers [out of 100] that

will end up in their assigned seats?

## Link to comment

## Share on other sites

## 3 answers to this question

## Recommended Posts

## Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.