drunk passenger probability?

For 1 < n < 128, passenger n will take their own seat, unless it's already been taken. Hence, by the time passenger 128 boards, the only possible free seat is 1 or 128.

Leaving aside the equally likely possibilities that passenger 1 took his own seat (in which case seat 128 will be free) and that passenger 1 took seat 128 (in which case it won't be free!), the situation is perfectly symmetrical. Since non-own seats are taken at random, there's no reason to suppose that seat 1 or seat 128 will be more likely to be free, so the probability that the 128th passenger will get the 128th seat is 1/2.

The seat change will always result in a loop, for example drunk person takes seat of A, A takes seat of B, B takes seat of C, C takes seat of drunk person. With more people in the loop, it will get longer and the shortest possible loop is when the drunk person takes his own seat (we'll just consider this a loop with one person to make the counting easier). There can't be two or more loop as there is only one drunk person. We need to calculate the probability where the 128th person is not involved in the loop. I think it's easier to calculate the probability of him involved in the loop and then substracting it from 1. I think the answer should be lower than 50% as there are many passenger and only a single loop. I think it's safe to say that all the possibilities has similar probability as they all represent a single seating possibility

To count the whole possible loops, we need to decide how many people and who are in the loop and their order after the drunk person (we consider the drunk person the 1st person in the order to avoid double counting). So the amount of ways is the sum of

127C0 X 0! = 1

127C1 X 1! = 127

127C2 X 2! = 127 X 126

127C3 X 3! = 127 X 126 X 125

.....

127C126 X 126! = 127!

127C127 X 127! = 127!

While the amount of ways the loop involves the 128th person is (we only need to decide whether the other 126 person is in the loop but still count the order involving the 128th person) the sum of

126C0 X 1! = 1

126C1 X 2! = 126 X 2

126C2 X 3! = 126X125 X 3

....

126C125X126! = 126!126

126C126X127! = 127!

If we pretend to not see the 1 at the top of the first sum, we can divide the lower sum with the first sum as

1+2+3+.....+127/127X127 = 64X127 / 127X127 is a little more than 50%. Adding the 1 we neglected won't change much as it doesn't even amount to 1/127! Of the sum of the rest of the divider party.

We can get the probability of 128th person being in the 128th seat by substracting the above possibility with the probability above. All I can compute is that it's slightly lower than 50% and slightly larger than 1-64/127

I immediately thought of Rencontres numbers but I guess those can't be used.

I'll first find the probability that 128th passenger does NOT get the 128th seat.

His seat can be taken by the drunkard: 1/128

His seat can be taken by the person displaced by the drunkard: (126/128) * (1/127)

Or by the next person displaced: (126/128) * (125/127) * (1/126)

And so on...

edit -- in the 3rd line, I changed 126/127 to 125/127 because no one should get the 1st seat except the 128th passenger.

edit #2 -- no formula or summation is needed. The answer is 50%

If I were to approach this the other way, and directly calculate the chance he DOES get the 128th seat, the calculations would look exactly the same. The last term in each line, 1/n, would simply represent a different thing-- the 1st seat being chosen instead of the last seat.

Since both probabilities p and 1-p are equal, the probability must be 50%.

edit #3 -- we can also use recursion as follows.

For n=2, the answer is clearly 50%.

For n=3, there's a 1/3 chance drunkard gets 3rd person's seat (failure), a 1/3 chance he gets his own seat (success), and a 1/3 chance he gets the 2nd person's seat which leads to the case of n=2.

P(success) = 1/3 + (1/3)(.5) = 1.5/3 = 1/2

In similar fashion we can show how every n devolves to the previous n, until we trace back to n=2.

Leave this open, please? Jury is still out. 50% doesn't seem to be working out.

What bothers me is that, in an effort to prove this by induction, I don't get 50% in the case of 4 passengers. Here are the scenarios, depending on where the drunk sits first:

Drunk takes seat 1:

Prob of 4 taking 4 = 1

Drunk takes seat 2:

Prob of 4 taking 4 = (1/3)(1) + (1/3)(1/2) + (1/3)(0) = 1/2

Drunk takes seat 3:

Prob of 4 taking 4 = (1/3)(1/2) + (1/3)(1/2) + (1/3)(0) = 1/3

Drunk takes seat 4:

Prob of 4 taking 4 = 0

Hence the probability works out to (1/4)(1 + 1/2 + 1/3 + 0) = 11/24, not 1/2. What's going on?

Edit: Oh there it is, gianlino, you're right. All right, I can see the rest of this now. It's indeed 50%

Edit 2: linlyons, your initial figure seemed way off, but nevertheless I had wondered about this problem, until gianlino corrected me. Why don't you try analyzing this where there's only 4 passengers and 4 seats? Or some other small number instead of 128?

Edit 3: For those still working on this problem, the probability in the case of 3, 4, and 5 are:

(1/3)(1 + 1/2 + 0) = 1/2

(1/4)(1 + 1/2 + 1/2 + 0) = 1/2

(1/5)(1 + 1/2 + 1/2 + 1/2 + 0) = 1/2

where each of the sub cases is what seat the 2nd passenger takes. Etc. The pattern should be clear.

50 % is correct.

@ Scythian

Drunk takes seat 3: then 2 takes seat 2 and then

Prob of 4 taking 4 = prob 3 chooses seat 1 instead of 4 = 1/2.

See my first link for a brief Python script simulating this operation 10,000 times. The experimental probability is essentially 1/2, in agreement with some of the existing answers. See the second link for some example runs using only 10 passengers.

1 of 128

Not sure what the correct answer is, but whoever said 1/2 is way wrong.

sorry, but lol at that answer.

peace