[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?

[HoustonHokie]

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.

[Guest]

0

The flight was later cancelled

[bonanova]

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