Probability question: names in hats

[Aractus]

That's the sort of thing I started out with. But it doesn't take into account how the probability changes, as I mentioned above.

The first one should be 8/9, because he can't take his own name. He only actually has 9 possible picks, player 2, ..., player 10. And player 10 is excluded because that would fail the problem. So it's 8 out of 9.

The second one could be 8/9 again if player 1 took player 2's name, [1, 3, 4, ... , 10]
or 7/8 if he didn't, as his own name then gets excluded.

And so on... the probabilities are all over the place. The tree diagram is horrid. I started it, but... no! There must be a better way.

No that's wrong. I'll explain. I did give the first answer instinctively FYI, and it was on the right track...

These are the rules:

Each of the ten people, in turn, select a name from the hat using the following rule: (the order of the people is not important)

1) They select a piece of paper at random from those remaining in the hat.
2) If the name is not their own name, they keep the piece of paper.
3) If the name is their own name, they pick again randomly, and then return their name to the hat.

First I'll consider how you got to 8/9 for pick 1.

It's a bit counter-intuitive so I'll try to explain: You added probabilities together. However step three reduces the probability of success from step 2 it doesn't improve it. In step 2 you have a 9/10 chance of not picking 10. So the probability is 9/10. But if you're holding onto number 1 you then need to reselect from the remaining 9 numbers, and this time your probability of success is 8/9, and the probability of selecting 10 is 1/9.

So, to recap: Person 1: 9/10 - 1/10 * 1/9  = 8/9.

So now we know how to correctly get to this number, we can work out Person 2's probability. Probability is 8/9 - 1/9 * 1/8 if their number is available or 8/9 if their number is unavailable (i.e. if it was picked by person 1). The probability that their number was picked is 1 in 9 since there are only 9 numbers that person 1 could have picked and kept.

So the probability of success of person 2 is: 8/9 * (8/9 - 1/9 * 1/8) + 1/9 * 8/9.

This formula will continue though to person 8 - person 9 cannot have two guesses otherwise they'll remove number 10, therefore their number cannot be selectable. The increasingly complicated part is the probability that the previous people picked your number. For person 3 there are two people who could have picked it, but only one of them could have done so. So probability that they did is (1/9 + 1/8)/2 (about 12%), and probability that they didn't is (8/9 + 7/8)/2, which of course can also be written as 1 - (1/9 + 1/8)/2

Person 1: 9/10 - 1/10 * 1/9 = .889
Person 2: 8/9 * (8/9 - 1/9 * 1/8) + 1/9 * 8/9 = .877
Person 3: (8/9 + 7/8)/2 * (7/8 - 1/8 * 1/7) + (1/9 + 1/8)/2 * 7/8 = .859
Person 4: (8/9 + 7/8 + 6/7)/3 * (6/7 - 1/7 * 1/6) + (1/9 + 1/8 + 1/7)/3 * 6/7 = .836
Person 5: (8/9 + 7/8 + 6/7 + 5/6)/4 * (5/6 - 1/6 * 1/5) + (1/9 + 1/8 + 1/7 + 1/6)/4 * 5/6 = .805
Person 6: (8/9 + 7/8 + 6/7 + 5/6 + 4/5)/5 * (4/5 - 1/5 * 1/4) + (1/9 + 1/8 + 1/7 + 1/6 + 1/5)/5 * 4/5 = .757
Person 7: (8/9 + 7/8 + 6/7 + 5/6 + 4/5 + 3/4)/6 * (3/4 - 1/4 * 1/3) + (1/9 + 1/8 + 1/7 + 1/6 + 1/5 + 1/4)/6 * 3/4 = .680
Person 8: (8/9 + 7/8 + 6/7 + 5/6 + 4/5 + 3/4 + 2/3)/7 * (2/3 - 1/3 * 1/2) + (1/9 + 1/8 + 1/7 + 1/6 + 1/5 + 1/4 + 1/3)/7 * 2/3 = .532
Person 9: (1/9 + 1/8 + 1/7 + 1/6 + 1/5 + 1/4 + 1/3 + 1/2)/8 * 1/2 = .114

.889 * .877 *.859 * .836 * .805 * .757 * .680 * .532 * .114 = 0.014

So the probability that person 10 gets their number at the end is 1.4%, which is only 0.4% off my original guess - actually only 0.3% off the 8/10*7/8*...*1/2 result.

And just in case this is difficult to follow, here it is colour-coded:


Example:
Person 6: (8/9 + 7/8 + 6/7 + 5/6 + 4/5)/5 * (4/5 - 1/5 * 1/4) + (1/9 + 1/8 + 1/7 + 1/6 + 1/5)/5 * 4/5 = .757

Formula: (Probability their number is selectable * Probability 10 isn't selected) + (Probability their number isn't selectable * Probability 10 isn't selected)