Probability question: names in hats

[robvalue]

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.

[TheRealJoeFish]

JoeFish is on the case! I will report back with musings during my lunch hour!

[robvalue]

Nice

Just to show why it is 8/9 for the first pick, to get someone from player 2 to 9:

Prob(1st pick) + Prob(own name)*Prob(2nd pick)

=8/10 + (1/10)*(8/9)

=8/10 + 8/90

=72/90 + 8/90

=80/90

=8/9

So it does act as if their own name just wasn't in the hat in the first place. It would have to, or else the probabilities for each of the remaining 9 names wouldn't add up to 1.

[robvalue]

For 3 players, it's very simple. The only way to achieve is picking 2, 1, 3.

Probability = 1/2 * 1/2 = 1/4

For 4 players:

2, 3, 1, 4 = 1/3 * 1/3 * 1/2 = 1/18
or
3, 1, 2, 4 = 1/3 * 1/2 * 1/2 = 1/12

Total = 5/36

As you can see, the two probability lines for 4 players aren't equal like they often are in probability questions, due to the fact that player 2 sometimes has more names to choose from.

Imagine how screwed up that gets analyzing the possibilities for 10 players.

[Whateverist]

This is a question someone posed to me many years ago. It may be well known, and the answer might be on the internet. I would ask that if anyone does go look it up, that they please don't spoil it for everyone else (and me) by posting the solution here.

I have as yet been unable to solve this, not that I've been trying constantly! I put a few hours into it here and there, and I felt I was coming close but came up empty. Here is the question:

There are ten people, who each write their name on a piece of paper. These are then all put into a hat.

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.

The question is: what is the probability that the tenth person is left with their own name in the hat?

Drawing a tree diagram will drive you insane! It's the "putting back your own name" that really makes this a tough puzzle. Regular probability and combination tricks don't apply as neatly.

Sorry if I'm covering familiar ground but I don't want to read any other responses until I try this myself.

Seems to me that there is some chance that every person who went before might have drawn the last person's name.  So when you come to the ninth person there is very little chance either name left in the hat belongs to the tenth person.  But I see no reason to think the probability is zero.  Perhaps this problem calls for a straight up calculation of probability rather than simply logic.  

If you want to know what the probability is of an 80% free throw shooter making all three free throws after getting fouled on a long attempt you would just multiply 8/10 • 8/10 • 8/10 to get 512/1000, so slightly better than 50/50.

So the probability that the last guy gets his own name would be the product of the probabilities of each preceding person not drawing his name. The probability for the first person not to have wound up with the last person's name would be 8 out of nine possible. (I'm excluding his own name since that isn't a possible keeper.) Continuing in this way we get:

Person 1: 8/9
Person 2: 7/8
Person 3: 6/7
.
.
.
Person 9: 1/2

So the probability of the last guy drawing his own name would be the product of all these probabilities =8/9 • 7/8 • ... • 2/3 • 1/2

Since the numerator of each person's probability is cancelled by the denominator the next person's probability the product reduces to 1/9, which is the answer to the problem.

[robvalue]

That was the very first answer I came up with when I tried this Sadly, it's wrong.

You're on the right track, but the probability for the second person depends on whether or not the first guy took his name already. If he took it, his probability is 8/9 again. If it didn't get taken, it's 7/8. Similarly, each pick will depend on whether his own one has been taken.

I can't get my head around how you account for all the combinations as they can all have different probabilities.

[Whateverist]

I still say on average 1 in 10 attempts will end up with this scenario.
That's my gut talking.

Your gut is pretty damn close if my calculation is correct.

[Whateverist]

That was the very first answer I came up with when I tried this Sadly, it's wrong.

You're on the right track, but the probability for the second person depends on whether or not the first guy took his name already. If he took it, his probability is 8/9 again. If it didn't get taken, it's 7/8. Similarly, each pick will depend on whether his own one has been taken.

I can't get my head around how you account for all the combinations as they can all have different probabilities.

Are you sure?  I think it only makes sense to calculate the probability for the second person as 7/8 since there are only 8 names remaining after the first person removed one of the names other than his own.  The second person is only drawing from a hat with nine names in it and he too is unable to keep his own.  So his probability of choosing a name after the first person has drawn and kept a name other than person ten's should be 7/8 I think.

[robvalue]

Say player 1 takes number 2 out the hat.

This leaves the following numbers: 1 3 4 5 6 7 8 9

9 numbers, and 8 of them keep the game going. So 8/9

It's the same deal as for player 1, except he had a redundant extra number (his own).

Now say player 1 takes another number, but not 2:

1 2 x x x x x x x

9 numbers, but one of them is a 2. Which he can't pick. So it's 7/8 to continue.

[Whateverist]

But that's what I'm saying too.  So why shouldn't the probability that the last guy draws his own name be the product of everyone else successfully drawing any name but his?

If I want to know what the probability of drawing (in the dark) a pair of black socks in a drawer that contains 3 black and 2 red socks.  I can find this two ways.  Lets start by naming each individual sock b1, b2 and b3 for the black socks and r1 and r2 for the red ones.  Now list all the possible combinations (reversing the order wouldn't affect the outcome):

1-b1,b2
2-b1,b3
3-b1,r1
4-b1,r2
5-b2, b3
6-b2,r1
7-b2,r2
8-b3,r1
9-b3,r2
10-r1,r2

Only combinations 1, 2 and 5 include a pair of black socks so the P(pair of black socks) is 3/10

The other way to calculate the probability is to take the product of the probability the first draw is black and the probability the second draw is also black (after the first draw):

3/5 • 2/4 = 6/20 = 3/10

So I think multiplying the probability of that each person draws any name except person ten's should get it done.  Am I missing something?