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)

[robvalue]

Whateverist:

It seems like you have the same solution paths as me for 3 and 4 people, but you're assuming the probability of each combination is the same. Sadly, they are not. So simply counting them isn't enough. That's what makes this problem harder.

For example, with 3 people, it must be 2, 1, 3

Player 1 can pick either name 2 or name 3. He can't pick his own. So the probability he picks name 2 is 1/2.

You can write it out explicitly including his own number, but you get the same result, as if it wasn't in there:

Prob(pick 2 on first try) + prob(pick own number)*prob(pick 2 on second try)

=1/3 + 1/3 * 1/2

=1/3 + 1/6

=1/2

So now player 2 must pick number 1. The numbers left are 1 and 3. So it's a straightforward 1/2.

Combining these gives 1/2 * 1/2 = 1/4

Similarly for the two lines for 4 people.

@aractus: Thanks, I'll have a look at that lot later.

[Whateverist]

Whateverist:

It seems like you have the same solution paths as me for 3 and 4 people, but you're assuming the probability of each combination is the same. Sadly, they are not. So simply counting them isn't enough. That's what makes this problem harder.

For example, with 3 people, it must be 2, 1, 3

Player 1 can pick either name 2 or name 3. He can't pick his own. So the probability he picks name 2 is 1/2.

You can write it out explicitly including his own number, but you get the same result, as if it wasn't in there:

Prob(pick 2 on first try) + prob(pick own number)*prob(pick 2 on second try)

=1/3 + 1/3 * 1/2

=1/3 + 1/6

=1/2

So now player 2 must pick number 1. The numbers left are 1 and 3. So it's a straightforward 1/2.

Combining these gives 1/2 * 1/2 = 1/4

Similarly for the two lines for 4 people.

But if in deed the probability is 1/4 you must be able to demonstrate 4 distinctly different drawing sequences in which the first two people draw any name but their own and where only one of those results in the third one drawing his own name (or else some multiple of those numbers like 2 out of 8).  I've found just the three: 1b,2a,3c ; 1c,2a,3b ; and, 1b,2c,3a .. where the numbers are assigned to the people by virtue of the order in which they pick and the letter with the same ordinality represents the name slip of each person.  

I think I can convince you these are the only three drawing sequences which satisfy the condition of the problem that none but the last person can keep their own name slip.  Here goes.

As you say, the first person can only keep person two's name slip "b" or person 3's name slip "c". 

If he draws person 2's name slip there are two ways that can go ->  1b,2a,3c  and  1b,2c,3a
If he draws person 3's name slip there is only one way that can go ->   1c,2a,3b  since reversing the last two results in 2b which isn't allowed.

What other possible drawing meets the conditions of the problem?  Since there only are three possibilities to consider the probability is 1/3 that the last guy gets stuck with his own name tag when three people play.

[robvalue]

The remaining sequences just have to bring the total up to 1, they don't have to all be the same probability. Let's see:

2, 3, 1 = 1/2 * 1/2 * 1 = 1/4

3, 1, 2 = 1/2 * 1 * 1 = 1/2

Note how the second line here happens half the time. If player one takes number 3, the other two picks are forced.

So these are the remaining two legal combinations. Total probability, along with the "winning" one: 1/4 + 1/4 + 1/2 = 1

[Whateverist]

The remaining sequences just have to bring the total up to 1, they don't have to all be the same probability. Let's see:

2, 3, 1 = 1/2 * 1/2 * 1 = 1/4

3, 1, 2 = 1/2 * 1 * 1 = 1/2

Note how the second line here happens half the time. If player one takes number 3, the other two picks are forced.

So these are the remaining two legal combinations. Total probability, along with the "winning" one: 1/4 + 1/4 + 1/2 = 1

I don't follow what you're doing here.  But before we jump to probabilities can you show me explicitly what drawing sequences you think satisfy the problem?  What is the sample space? (I assume you do not include sequences in which any but the last keeps his own name as they aren't allowed to keep them anyway, right?)

Fill in the blanks please: { _____ , _____ , _____ , _____ }

[robvalue]

There are only 3 possible sequences which don't violate the rules that you can't pick your own number (except for the last guy):

2, 1, 3: probability 1/4

2, 3, 1: probability 1/4

3, 1, 2: probability 1/2

That's it. That's all the ways it can happen. They don't all have equal probabilities. And only the first one satisfies the criteria of player 3 drawing his name.

All I've done is extracted these 3 sequences from the possible 6 permutations of 1, 2, 3 by excluding the ones where player 1 or player 2 take their own number.

I've excluded 1, 2, 3

1, 3, 2

And

3, 2, 1

These three can't happen.

[Aractus]

HA! I just worked out the proper solution. I'd neglected to put probability of n being selected into the formula correctly. Funnily enough adding it simplifies the formula hugely. Thus:

1.      9/10 - 1/10 * 1/9  = 8/9
2. 8/9 * (8/9 - 1/9 * 1/8) = 7/9
3. 7/9 * (7/8 - 1/8 * 1/7) = 6/9
4. 2/3 * (6/7 - 1/7 * 1/6) = 5/9
5. 5/9 * (5/6 - 1/6 * 1/5) = 4/9
6. 4/9 * (4/5 - 1/5 * 1/4) = 3/9
7. 1/3 * (3/4 - 1/4 * 1/3) = 2/9
8. 2/9 * (2/3 - 1/3 * 1/2) = 1/9
9.        8/9 * 1/9 * 1/2  = 8/162

1/81  = .01234567890123456789012345678901234567890123456789...
8/162 = .04938271604938271604938271604938271604938271604938...

This time I'm SURE it's correct, due to its eloquence.

[robvalue]

Nice. I shall check that out when my brain's up to it.

It would be interesting to run a simulation to estimate the probability. Maybe I'll code it.

[Whateverist]

There are only 3 possible sequences which don't violate the rules that you can't pick your own number (except for the last guy):

2, 1, 3: probability 1/4

2, 3, 1: probability 1/4

3, 1, 2: probability 1/2

That's it. That's all the ways it can happen. They don't all have equal probabilities. And only the first one satisfies the criteria of player 3 drawing his name.

All I've done is extracted these 3 sequences from the possible 6 permutations of 1, 2, 3 by excluding the ones where player 1 or player 2 take their own number.

I've excluded 1, 2, 3

1, 3, 2

And

3, 2, 1

These three can't happen.

Wait, are you saying that the 3,1,2 sequence is twice as likely to occur as either the 2,1,3 or the 2,3,1 sequence?  Lets see about that.

A:  1,2,3
B:  1,3,2
C:  2,1,3
D:  2,3,1
E:  3,1,2
F:  3,2,1

These at least have an equal chance of occurring if we ignore the requirement that sequences A,B & F require a redraw.  Now do we know whether the rejected slip is put back in before the redraw?  (Does any of this really matter?  If so, I'm beginning to hate this problem.)  Without knowing about what to do with the rejected slip it is hard to know how to proceed from here.

But setting that concern aside, I don't see how you can say sequence E is twice as likely to occur as either sequence C or D.  The way I analyze the experiment/game is this:

N players place a strip of paper with their name on it into a hat.  (Let's assume their names are as distinct as they are.)
They then take turns drawing, but only keep the first strip which does not contain their own name.  Mis-draws are returned to the hat.
The only player who might be stuck with his own name strip in this game is the last to draw.
The question is: what is the probability the last person indeed draws his own name?

By my analysis, a game with n players can take many more than n draws but never more than n allowable draws.  The sample space is therefore limited to the sequences composed only of allowable draws.  These, I believe, are equally likely without regard to the number of unallowed draws which might occur in the course of the game.  I think this is where we disagree.  Is that so?

[robvalue]

Yes, that's exactly what I'm saying.

Once we enforce the rules of the game, there is a probability of 1/2 that player 1 picks number 3. He can pick either 2, or 3.

(It can be made explicit as 1/3 + 1/3 * 1/2 = 1/2)

Once he has picked that number, player 2 is left with numbers 1 and 2. He can't pick his own number, so he must pick number 1. And then player 3 must pick number 2.

So half the time, player 1 picks number 3. Every time that happens, we always get 3, 1, 2

But if player 1 takes the number 2 instead (the other half of the time), there are two equally likely possibilities:

2, 3, 1

And

2, 1, 3

So those two share the probability. They get 1/4 each.

This is a very nonstandard puzzle!