Probability Problem

[steve_bank]

A variation on a problem posed by Alcoholic Actuary.

100passangers are lined up in order of numerical seat assignments withing to board a plane.
#1 enters and randomly picks a seat.
#2 enters and if his seat is open takes it, if it is occupied randomly picks from the open seats.
The rest of the passengers follow suit.

For n = 3 the possible sequences of seat selections are.

Passengers 1,2,3
1 2 3
2 1 3
2 3 1
3 1 2
3 2 1

Probabilities of passenger seat selection
Passenger 1 seat 1 1/3 seat 2 1/3 seat 3 1/3
Passenger 2 seat 1 2/5 seat 2 2/5 seat 3 1/5
Passenger 3 seat 1 2/5 seat 2 1/5 seat 3 2/5

I don't see how to combine the probabilities to get a general function for any n that gives the probability of the final seat assignments.

Seat 2 selection is conditional on seat 1 selection, and seat 3 selection is conditional depending on seat 2 selection.

I don't see how to write out the conditional probabilities.

 

[Jarhyn]

A variation on a problem posed by Alcoholic Actuary.

100passangers are lined up in order of numerical seat assignments withing to board a plane.
#1 enters and randomly picks a seat.
#2 enters and if his seat is open takes it, if it is occupied randomly picks from the open seats.
The rest of the passengers follow suit.

For n = 3 the possible sequences of seat selections are.

Passengers 1,2,3
1 2 3
2 1 3
2 3 1
3 1 2
3 2 1

Probabilities of passenger seat selection
Passenger 1 seat 1 1/3 seat 2 1/3 seat 3 1/3
Passenger 2 seat 1 2/5 seat 2 2/5 seat 3 1/5
Passenger 3 seat 1 2/5 seat 2 1/5 seat 3 2/5

I don't see how to combine the probabilities to get a general function for any n that gives the probability of the final seat assignments.

Seat 2 selection is conditional on seat 1 selection, and seat 3 selection is conditional depending on seat 2 selection.

I don't see how to write out the conditional probabilities.

So, seat 2 has a 1:n chance of being occupied for passenger 2.

I think you really need to look at 4 seats to get it though.

Passenger 1 has a 1:4 chance of of getting seat 1.

Passenger 2 has a 3:4 chance of getting seat 2, and a 1/3:4 chance, or 1:12 chance, of getting seats 1, 3, or 4.

For Passenger 3 there is a 1:12 chance that passenger 2 is in their seat and a and a 1:4 chance 1 is. Either way, the remaining seats are either 1 and 4 or 3 and 4. Passenger 3 will have 4/12 situations where someone is in their seat so there is a 2:3 chance of getting to sit in seat 3 for passenger 3, a 1:6 chance of sitting in seat 1, and a 1:6 chance of sitting in seat 4.

Because there is a 1/6 chance of passenger 3 being in seat 4, a 1/12 chance of 2 sitting in seat 4 and a 1/4 chance of passenger 1 sitting in seat 4 there is a 2+1+3:12 chance, or 1:2 chance of seat 4 not going to passenger 4.

 

[Alcoholic Actuary]

A variation on a problem posed by Alcoholic Actuary.

100passangers are lined up in order of numerical seat assignments withing to board a plane.
#1 enters and randomly picks a seat.
#2 enters and if his seat is open takes it, if it is occupied randomly picks from the open seats.
The rest of the passengers follow suit.

For n = 3 the possible sequences of seat selections are.

Passengers 1,2,3
1 2 3
2 1 3
2 3 1
3 1 2
3 2 1

Probabilities of passenger seat selection
Passenger 1 seat 1 1/3 seat 2 1/3 seat 3 1/3
Passenger 2 seat 1 2/5 seat 2 2/5 seat 3 1/5
Passenger 3 seat 1 2/5 seat 2 1/5 seat 3 2/5

I don't see how to combine the probabilities to get a general function for any n that gives the probability of the final seat assignments.

Seat 2 selection is conditional on seat 1 selection, and seat 3 selection is conditional depending on seat 2 selection.

I don't see how to write out the conditional probabilities.

231 is not an option. If 2's seat is open he takes it, so if 1 sits in 3's seat the only option is 321. So the set is, in fact complete - person 3 gets their seat 2 out of 4 times (=0.5).

aa

 

[Swammerdami]

Probabilities of passenger seat selection
Passenger 1 seat 1 1/3 seat 2 1/3 seat 3 1/3
Passenger 2 seat 1 2/5 seat 2 2/5 seat 3 1/5
Passenger 3 seat 1 2/5 seat 2 1/5 seat 3 2/5

So, according to you, seat #1 is taken by passenger #1 1/3 of the time, by #2 2/5 of the time and by #3 2/5 of the time.
Altogether seat #1 is taken 17/15 of the time. (5/15 + 6/15 + 6/15)
Does this seem correct, or even sensical, to you?

One mistake frequently made is to find that there are, say, 5 possibilities and then incorrectly assume that each occurs with probability 1/5.

Instead, passenger #N (N > 1) gets his own seat with probability (101-N)/(102-N).
He gets seat #1, #(N+1), #(N+2), ... #100 each with probability 1/((101-N)*(102-N))
Or, with 3 seats instead of 100, passenger #2 gets his own seat with p = 2/3; he gets seat #1 or #3 with p=1/(2*3) each.

I don't see how to write out the conditional probabilities.

The beauty of aa's puzzle is that you don't need to. A short-cut leads to the p=1/2 answer.

 

[steve_bank]

A variation on a problem posed by Alcoholic Actuary.

100passangers are lined up in order of numerical seat assignments withing to board a plane.
#1 enters and randomly picks a seat.
#2 enters and if his seat is open takes it, if it is occupied randomly picks from the open seats.
The rest of the passengers follow suit.

For n = 3 the possible sequences of seat selections are.

Passengers 1,2,3
1 2 3
2 1 3
2 3 1
3 1 2
3 2 1

Probabilities of passenger seat selection
Passenger 1 seat 1 1/3 seat 2 1/3 seat 3 1/3
Passenger 2 seat 1 2/5 seat 2 2/5 seat 3 1/5
Passenger 3 seat 1 2/5 seat 2 1/5 seat 3 2/5

I don't see how to combine the probabilities to get a general function for any n that gives the probability of the final seat assignments.

Seat 2 selection is conditional on seat 1 selection, and seat 3 selection is conditional depending on seat 2 selection.

I don't see how to write out the conditional probabilities.

231 is not an option. If 2's seat is open he takes it, so if 1 sits in 3's seat the only option is 321. So the set is, in fact complete - person 3 gets their seat 2 out of 4 times (=0.5).

aa

#1 picks 2, #2 picks 1 or 3.

I cha, 1 can pick 1m2m or 3.nged the problem

 

[steve_bank]

I moved over here hoping somebody who knows more about probability theory than I do drops in.

The philosophy forum is for what somebody thinks is a clever logic problem.

 

[Alcoholic Actuary]

A variation on a problem posed by Alcoholic Actuary.

100passangers are lined up in order of numerical seat assignments withing to board a plane.
#1 enters and randomly picks a seat.
#2 enters and if his seat is open takes it, if it is occupied randomly picks from the open seats.
The rest of the passengers follow suit.

For n = 3 the possible sequences of seat selections are.

Passengers 1,2,3
1 2 3
2 1 3
2 3 1
3 1 2
3 2 1

Probabilities of passenger seat selection
Passenger 1 seat 1 1/3 seat 2 1/3 seat 3 1/3
Passenger 2 seat 1 2/5 seat 2 2/5 seat 3 1/5
Passenger 3 seat 1 2/5 seat 2 1/5 seat 3 2/5

I don't see how to combine the probabilities to get a general function for any n that gives the probability of the final seat assignments.

Seat 2 selection is conditional on seat 1 selection, and seat 3 selection is conditional depending on seat 2 selection.

I don't see how to write out the conditional probabilities.

231 is not an option. If 2's seat is open he takes it, so if 1 sits in 3's seat the only option is 321. So the set is, in fact complete - person 3 gets their seat 2 out of 4 times (=0.5).

aa

#1 picks 2, #2 picks 1 or 3.

I cha, 1 can pick 1m2m or 3.nged the problem

While I appreciate your struggles with communication, I apologize as this is unintelligible to me. You are correct, if #1 picks 2, then there are two choices remaining (213 or 312). But if #1 picks 1, or #1 picks 3, the game is finished and the outcomes are 1 each (123 or 321) #2 cannot take seat 1 if his seat is available so 231 is out. This leaves us with 4 possible outcomes - 2 of which end up with #3 in the right seat.

aa

 

[Alcoholic Actuary]

I moved over here hoping somebody who knows more about probability theory than I do drops in.

The philosophy forum is for what somebody thinks is a clever logic problem.

Got it. I know I'm likely considered the world's most okayest probabilityer but I have spent a lifetime studying this stuff, and this problem is the tip of the iceberg in my day to day work.

aa

 

[Jarhyn]

Probabilities of passenger seat selection
Passenger 1 seat 1 1/3 seat 2 1/3 seat 3 1/3
Passenger 2 seat 1 2/5 seat 2 2/5 seat 3 1/5
Passenger 3 seat 1 2/5 seat 2 1/5 seat 3 2/5

So, according to you, seat #1 is taken by passenger #1 1/3 of the time, by #2 2/5 of the time and by #3 2/5 of the time.
Altogether seat #1 is taken 17/15 of the time. (5/15 + 6/15 + 6/15)
Does this seem correct, or even sensical, to you?

One mistake frequently made is to find that there are, say, 5 possibilities and then incorrectly assume that each occurs with probability 1/5.

Instead, passenger #N (N > 1) gets his own seat with probability (101-N)/(102-N).
He gets seat #1, #(N+1), #(N+2), ... #100 each with probability 1/((101-N)*(102-N))
Or, with 3 seats instead of 100, passenger #2 gets his own seat with p = 2/3; he gets seat #1 or #3 with p=1/(2*3) each.

I don't see how to write out the conditional probabilities.

The beauty of aa's puzzle is that you don't need to. A short-cut leads to the p=1/2 answer.

In the three seat arrangement, seat 2 has a 1:3 chance of being taken before person 2, and so person 2 has a 2:3 chance kf sitting in seat 2.

This means their remaining chance of sitting in seat 1 or 3 is 1:3, split evenly across their selections, 1:6 for each seat.

1 similarly has a 1:3 chance of ending up in seat 3.

Combine these for 2+1:6, to discover the probability in total of someone claiming #3's seat first.

 

[Alcoholic Actuary]

Spoiler: Solution v2.0

For N seats on a plane the first person on the plane either ends the problem with (1/N) probability of taking their own seat, or (1/N) probability of taking yours (equal probability of each case). Then with ((N-2)/N) probability reduces the problem to the same situation with a smaller plane. P(N) = ((1/N) x 1) + ((1/N) x 0) + (((N-2)/N)) x P(N-1)). Eventually we will get down to some person taking seat 2 or 3 or 4 which we solved for = 0.5, so let's conjecture a solution where P(N-1) = 0.5. The formula simplifies to ((2/2N) + ((N-2)/2N) = (N/2N) = 0.5 - doesn't matter how many seats.

Plug in any N >=2.

aa

 

[steve_bank]

I used Scilab to generate permutations and stared at them for a while. Posting permutations for n=5 would be too much.

Restating the problem. N passengers are lined up in order of their initial seat assignments. #1 picks a seat randomly. The following pick randomly from open seats until #n is left.

What is the probability of passenger n ending up with seat n?

Back to basics. First enumerate the number of possible outcomes. Then enumerate the number of results with seat n as the last open seat.


Looking at n = 4, if passenger 1 picks seat 1 there are six possible outcomes, (n-1)!. The total possible outcomes are n*(n-1)!, the probability space.

When passenger 1 selects seat 1 there are 2 chances for passenger 4 to end up with seat 4,
(n-1)*(n-2)! The total number of occurrences is (n-1)*(n-2!) .


Probability passenger n gets seat n = (n-1)*(n-2!) / (n*(n-1)!)

For n > 1

n = 2
(2-1)*(2-2)!) / (2*(2-1)!) = 1/2

1 2

2 1


n = 3
(3-1)*(3-2)!) / (3*(3-1)!) = 2/6

1 2 3
1 3 2

2 1 3
2 3 1

3 1 2
3 2 1

n = 4
(4-1)*(4-2!) / (4*(4-1)!) = 6/24

1 4 3 2
1 4 2 3
1 3 4 2
1 3 2 4
1 2 4 3
1 2 3 4

2 4 3 1
2 4 1 3
2 3 4 1
2 3 1 4
2 1 4 3
2 1 3 4

3 4 2 1
3 4 1 2
3 2 4 1
3 2 1 4
3 1 4 2
3 1 2 4

4 3 2 1
4 3 1 2
4 2 3 1
4 2 1 3
4 1 3 2
4 1 2 3


From that I'll work on AA's version showing for any n p = 1/2.

 

[steve_bank]

Spoiler: Solution v2.0

For N seats on a plane the first person on the plane either ends the problem with (1/N) probability of taking their own seat, or (1/N) probability of taking yours (equal probability of each case). Then with ((N-2)/N) probability reduces the problem to the same situation with a smaller plane. P(N) = ((1/N) x 1) + ((1/N) x 0) + (((N-2)/N)) x P(N-1)). Eventually we will get down to some person taking seat 2 or 3 or 4 which we solved for = 0.5, so let's conjecture a solution where P(N-1) = 0.5. The formula simplifies to ((2/2N) + ((N-2)/2N) = (N/2N) = 0.5 - doesn't matter how many seats.

Plug in any N >=2.

aa

No thanks, I need the mental exercise.

 

[steve_bank]

Typo

Probability passenger n gets seat n = (n-1)*(n-2!) / (n*(n-1)!)

should be (n-1)*(n-2)! / (n*(n-1)!)