Probability question: names in hats

[robvalue]

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.

[downbeatplumb]

Well if there are only ten people and each person keeps going until they get a paper without their name on, then the answer is zero chance because his name would already have been picked by one of the others. Or am I wrong?

[robvalue]

No, the nine people can each have their own names between them.

As a simple example, person 1 has the name of person 2, person 2 has the name of person 3, ... , person 9 has the name of person 1.

So the problem can be somewhat simplified in that manner. You're looking for the probability that exactly this happens. The first 9 people draw their own names, in some combination.

It's a lot fucking harder than it sounds

[Mr.wizard]

1/90? Maybe?

[robvalue]

Maybe! How did you get it?

I don't know what the answer is.

[ignoramus]

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

[Mr.wizard]

Maybe! How did you get it?

I don't know what the answer is.

Aww you don't know the answer!? I just took the number of players 10 and multiplied it by the number 9 possible choices for each pick. I'm probably wrong but I was hoping you could tell me, lol.

[ignoramus]

When it gets down to 2 names left, (and one is yours), the second last person will always have a 50% chance of picking yours.
So whatever the odds are up until that point, double it again. IE, it will twice as rare for this scenario to eventuate.

[robvalue]

Hehe

I tried several approaches. I simplified the puzzle down to just 3 people, so that the calculation is easy. Then up to 4 people, to see if there was some sort of iterative formula. I didn't find one, although there could be.

The annoying thing is that each pick changes some of the probabilities...

Like if player 1 picks the name of player 2, player 2 then has 8/9 chance of picking a player from 1 to 9. But if player 1 picks a higher number, player 2 has a 7/8 chance, because his own name is effectively not for grabs. And so on. They have a ripple effect through each other which I found very hard to put into a general formula.

Maybe there is a simple way of doing it that I just haven't thought of. But it seemed like a total disaster.

Usually, with this kind of thing, you get an easily countable number of branches on a probability tree, with the same probability. But they don't work like that here, as far as I can see.

You could also approach it in reverse: find the probability that one of the first 9 take player 10's name. This will then be (1-probability it is left).

So probability player 1 takes it is 1/9, since he can't take his own. But then the chances of player 2 depends again on whether his name as already been picked or not...

[Aractus]

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.

Right OK.

I'm going to assume that you meant to say in Step 3 that they keep the piece of paper if it isn't their name, right?

I think it's basically this: (8/10)*(7/9)*(6/8)*(5/7)*(4/6)*(3/5)*(2/4)*(1/3)*(1/2) - i.e. 1%.