Probability question: names in hats

[Chas]

You're right Chas, but the problem is that the combinations don't all produce the same probability.

I think the solution involves both counting combinations and being able to count up how many there are for each probability. I got stuck into it at one point, but I didn't quite get there.

It's the "not your own name" that throws the wrench in, and the probability for each person changes depending on whether their number has already come up or not.

I did the example for 4 people to show this. There's 2 legal combos, but they have different probs:

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

Every combination has the same probability of occurring.

[TheRealJoeFish]

You're right Chas, but the problem is that the combinations don't all produce the same probability.

I think the solution involves both counting combinations and being able to count up how many there are for each probability. I got stuck into it at one point, but I didn't quite get there.

It's the "not your own name" that throws the wrench in, and the probability for each person changes depending on whether their number has already come up or not.

I did the example for 4 people to show this. There's 2 legal combos, but they have different probs:

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

Every combination has the same probability of occurring.

It doesn't though, and here's why:

Consider the ABCD grouping. If A picks "C" out of the hat, then when B goes to pick he'll have "A", "B", and "D" left in the hat. B can't pick his own name, so B can either pick "A" or "D". Thus, the chance that the first two picks are, say, "CD" is 1/3*1/2 = 1/6.

But, if A picks "B" on the first pick, B has "A", "C" and "D" left in the hat. So, because none of these have to be put back, B has a 1/3 chance of picking each. Thus, the chance of the first two being "BD" is 1/3*1/3 = 1/9.

That's what Rob means when he says the probability changes depending on the previous pick.

[Whateverist]

Can anyone confirm that these are all the combinations in which all but the last person can draw any name but their own when there are 3 people total and for when there are 4 people total?

Let 1 = first person to draw, and a= his name slip; Let 2 = second person to draw, and b = his name slip; and so on.

Then for three people, the combinations in which all but the last person can draw any name but their own:

1b,2a,3c     1c,2a,3b             Of these three combinations there is only 1 in which the last person draws his name, 
1b,2c,3a                              P(last person is left with his own name) = 1/3 for 3 people

For four people, the combinations in which all but the last person can draw any name but their own:

1b,2a,3d,4c     1c,2a,3b,4d     1d,2a,3b,4c             Of these there are only two combinations  
1b,2c,3a,4d     1c,2a,3d,4b     1d,2c,3a,4b             in which the last person draws his name, 
1b,2c,3d,4a     1c,2d,3a,4b     1d,2c,3b,4a             P(last person is left with his own name) = 2/11 for 4 people
1b,2d,3a,4c     1c,2d,3b,4a     


It would be no fun to type up all the combinations I got for 5 people, but I count 51 combinations in which all but the last person draws a person's name other than their own.  Of these I count 9 of them in which the last person draws his own name.  (But I am much less confident in these totals.)  If correct that would make P(last person is left with his own name) = 9/51, or if you like, 3/17 for 5 people

Again, if anyone can confirm my count of combinations I would be obliged.  Rob, you were certainly correct about this being one hell of an unwieldy problem.  I wonder if it will allow for an elegant solution.  I've got nothing so far.

[Chas]

Every combination has the same probability of occurring.

It doesn't though, and here's why:

Consider the ABCD grouping. If A picks "C" out of the hat, then when B goes to pick he'll have "A", "B", and "D" left in the hat. B can't pick his own name, so B can either pick "A" or "D". Thus, the chance that the first two picks are, say, "CD" is 1/3*1/2 = 1/6.

But, if A picks "B" on the first pick, B has "A", "C" and "D" left in the hat. So, because none of these have to be put back, B has a 1/3 chance of picking each. Thus, the chance of the first two being "BD" is 1/3*1/3 = 1/9.

That's what Rob means when he says the probability changes depending on the previous pick.

But it doesn't change the probabilities.  The disallowed choices aren't part of the solution set; they simply don't exist.  Their probability of being chosen is zero.

[ignoramus]

Guys, aren't the first 8 picks completely irrelevant as far as the odds go?
Only one in ten samples will end in the last person whose name is still unpicked and then there's a 50% chance of not being picked anyway.

So basically, it's a one in 20?

[Chas]

Guys, aren't the first 8 picks completely irrelevant as far as the odds go?
Only one in ten samples will end in the last person whose name is still unpicked and then there's a 50% chance of not being picked anyway.

So basically, it's a one in 20?

No, there are many more paths than that.  The number of ways to pick is what determines the probability.

[Chas]

Can anyone confirm that these are all the combinations in which all but the last person can draw any name but their own when there are 3 people total and for when there are 4 people total?

Let 1 = first person to draw, and a= his name slip; Let 2 = second person to draw, and b = his name slip; and so on.

Then for three people, the combinations in which all but the last person can draw any name but their own:

1b,2a,3c     1c,2a,3b             Of these three combinations there is only 1 in which the last person draws his name, 
1b,2c,3a                              P(last person is left with his won name) = 1/3 for 3 people

For four people, the combinations in which all but the last person can draw any name but their own:

1b,2a,3d,4c     1c,2a,3b,4d     1d,2a,3b,4c             Of these there are only two combinations  
1b,2c,3a,4d     1c,2a,3d,4b     1d,2c,3a,4b             in which the last person draws his name, 
1b,2c,3d,4a     1c,2d,3a,4b     1d,2c,3b,4a             P(last person is left with his won name) = 2/11 for 4 people
1b,2d,3a,4c     1c,2d,3b,4a     


It would be no fun to type up all the combinations I got for 5 people,  but I count 51 combinations in which all but the last person draws a person's name other than their own.  Of these I count 9 of them in which the last person draws his own name.  (But I am much less confident in these totals.)  If correct that would make P(last person is left with his won name) = 9/51, or if you like, 3/17 for 5 people

Again, if anyone can confirm my count of combinations I would be obliged.  Rob, you were certainly correct about this being one hell of an unwieldy problem.  I wonder if it will allow for an elegant solution.  I've got nothing so far.

Hmmmm, I miscounted the number of legal picks for 4 people, so my elegant solution is wrong. 

[Whateverist]

Yeah, mine too. So you agree with my count for four people? Man, these numbers are ugly.

[Whateverist]

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.

Yikes, my results don't agree with yours for either 3 people or 4.  I believe there are only three combinations in which the first two people keep a name other than their own and only one of these has the last guy getting his own name.  P = 1/3.  Right?

[Foxaèr]

The probability is the same for the first individual who reaches into the hat, yet the probability does change after that point. There is no same probability. Rather, it changes with each name that is chosen.