Probability question: names in hats

[Whateverist]

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 * 8/9 - 8/9 * 1/9 * 1/8) = 7/9
3. 7/8 * (7/9 * 7/8 - 7/9 * 1/8 * 1/7) = 6/9
4. 2/3 * (2/3 * 6/7 - 2/3 * 1/7 * 1/6) = 5/9
5. 5/9 * (5/9 * 5/6 - 5/9 * 1/6 * 1/5) = 4/9
6. 4/9 * (4/9 * 4/5 - 4/9 * 1/5 * 1/4) = 3/9
7. 1/3 * (1/3 * 3/4 - 1/3 * 1/4 * 1/3) = 2/9
8. 2/9 * (2/9 * 2/3 - 2/9 * 1/3 * 1/2) = 1/9
9.                           1/9 * 1/9 = 1/(9*9)

1/81 = .01234567890123456789012345678901234567890123456789...

It's still approximately 1%, thus my original guess was pretty damn close. This time I'm SURE it's correct, due to its eloquence.

But please show what your procedure (which I'm not sure I completely understand*) returns as an answer for the two cases for which the answer is known: 3 players and 4 players.


*I believe you mean that the probability for just one person playing would be 8/9 and for two, 7/9.  But we can ignore these results as noise since we understand the game doesn't work at all for 1 or 2 persons.  But I admit I'm not at all sure what you are showing here.

Is it just a procedure for finding the probability for ten people .. or can you stop it at any point to find the answer for less people?  If that is the way it works then your probability for three people, 6/9, would actually be the probability that the last person does not draw his own name .. and that agrees with my reckoning.  But your result for four players in the fourth line does not agree with what I find based on an elaboration of the actual sample space.

[robvalue]

Whatever: I'd recommend drawing out a probability tree for the three player case.

Just put in branches that are possible, following the rules of the game. You'll come up with two initial branches, one of which splits into another two. I'll draw it if you like

There is no need to consider possibilities that the rules of the game don't allow. Although you could put all 6 on the tree, and then cross 3 out.

[Whateverist]

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.

.
.

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!

But why are you keeping track of mis-draws?  A player's turn isn't over until he draws a strip he can keep.  I'm saying the sample space should only keep track of allowable draws.  Whenever any other draw is made it is essentially just noise but of no consequence. The probability should not be tracking the number of times a player draws a strip, only the number of times he draws an allowable strip.

And with that I'm off to work on the roof today.  We've had record rains which led to leak in my closet coming from the skylight above the bathroom in the next room.  I've got to get some flashing and paint to make sure that does't happen again when the rains return.

[robvalue]

Huh?

Whu?

I'm not!

When I say 2, 3, 1 I mean that is what the three players end up with.

[robvalue]

This is the complete probability tree for every legal outcome:



The solution is found by adding together the probabilities of those that end with player 3 getting a 3. So that's just the top one, 1/4.

Try it out! It will happen about 1/4 of the time

[robvalue]

To put it another way:

To "win", you have to make two successful pulls. You have to pull a 2 from the 2 and a 3; then you have to pull the 1 from the remaining 1 and 3. That's two 50% shots you have to win. Overall 25%.

If you pick wrong first (3), with 50% chance, you lose. The game is over; but anyhow the only combination left is 3, 1, 2.

If you pick a 2 first but then miss and pull a 3, you lose; that's two 50% picks so 25%. Total 75% chance to lose.

[Whateverist]

Have you tried it yourself enough to think 1/4 is strongly indicated over 1/3? I may have to try it later when I have the time.

[robvalue]

I have not, but I'm extremely confident in my calculations.

This isn't like a normal puzzle where you have branches or probability spaces that all have the same probability. So just counting up ways it can happen doesn't work, like for example counting the ways you can get a total of 8 on two dice.

If experiment contradicts the theory, I shall be interested and most surprised! It would cause me major concern over my mathematical abilities, if I've got this 3 person example wrong. In fact, I think actually doing the puzzle as an experiment would help you see exactly why it's 1/4. (Unless I've made some catastrophic error. Of course, that's always possible.)

I tell you what, I was going to code the 10 man puzzle anyway. So I'll code the 3 man one as well and get some data that way.

EDIT: I just realized another one I could explain it. I'm going to draw another diagram.

[Whateverist]

I don't know what to think of that idea of assigning 50% probability to 3,1,2 sequence just because there is an equal chance the first person might draw the third person's name strip or that of the second person. If the first person does draw the third person's name first it is also equally likely that the second person will initially draw either the first person's name strip or his own. But if the second person draws his own name strip he just draws again.

No good. I'm too sleepy to think about it properly now regardless. Good luck. How long have you been haunted by this brain worm exactly?

[robvalue]

I had forgotten about it for a long time, I just remembered it recently. It was about.... 10 years ago I heard it!

OK, I've drawn a series of 5 diagrams. The first diagram starts off with the full probability tree, if players could just pick any number and stick with it. It gives the expected result, that each of the possible results has a probability of 1/6. (1/3 * 1/2 * 1).

Then I've gone through and removed, bit by bit, the possibilities that the rules forbid. I've removed the whole branch that starts with player 1 picking 1, because he cannot. Then I've removed the branch for player 2 picking 2, because again he cannot.

Because several options are being removed, this causes the probability of the remaining options to increase. They must now total to 1, from each branch. So 3 options of 1/3 each drop down to 2 with 1/2; and 2 options of 1/2 each will drop down to 1 option with probability 1 (certainty). And it doesn't alter the probabilities of getting to those points in the first place.

---

---