Probability question: names in hats

[Whateverist]

What I don't understand about this would fill a book. If the first branches of the tree (from the left) represent the four names the first person might draw, why is 1/4 written on the bottom most of these branches? Does that represent the case in which the first player draws his own name? If so a couple of questions come up for me. First, why track that possibility at all since it can't count toward a sequence that resolves the game either as a win or a loss? (By the way which are you counting as a win, last guy draws his own name -or- last guy does not draw his own name?) Second, if it isn't a sequence the game can actually include, why value at a probability of 1/4?

That, again, is only the tip of the ice berg regarding what I don't understand about either the problem or your solution.

[Aractus]

The probability tree I posted should be easy to follow as each line is drawn from the number selected. So the far left, the first choice represents a choice of any of the numbers 1-4, and if 4 is selected winning is impossible. If 1 is selected then person 1 needs to reselect hence "1b". The number 1 is returned after their selection (i.e. after 1b and where person 2 can chose from).

Here's an edited picture with the self-selected number returned to the Xb picks, if it makes it any clearer:



When playing the actual game you will keep playing beyond the losing positions, but they're already losing positions so there's no point in considering further possibilities for them as they're already at a losing point. You really need to go to 5 numbers to see the pattern properly though because as I mentioned for N players number N-1 can't be available past the N-2nd selection (i.e. if the 3rd selection is between 3 and 4 then player 3 must select 4 and return 3 to be selected by 4 in this example).

[robvalue]

Whateverist: Did you agree with my 3 player model, as I explained with all the diagrams whittling the probability tree down? I have confirmed the answer is correct, just wondering if I explained it properly.

Emjay: The messing about with the person's own name seems weird when calculating probabilities, but you can actually just work it out as if that name isn't there. But this drops the total, affecting the bottom of the fraction.

For example, player 1 has 10 numbers to choose from. But we can ignore his own one. So he actually has just 9, which are 2 up to 10

Each of these has an equal probability, so each one is 1/9

It can be shown explicitly that this is correct, even including the number 1. The probability he picks a particular number can be calculated by him getting it right away, or else picking his own number and then picking the desired one second time. Since these are exclusive events, we can add the probabilities. So to get a specific number (say 3 for example)

Prob(gets 3) = prob(gets 3 on first pick) + prob(gets own number) * prob(gets 3 on second pick)

On the second pick, his own name is no longer there, so we're down to 9 possibilities.

=1/10 + 1/10 * 1/9

So 1/10 of the time he gets a 3 right away; a further 1/10 of the time he pulls his own number, and then 1/9 of the time following this he'll get a 3 as the second pick.

=1/10 + 1/90

=9/90 + 1/90

=10/90

=1/9

So after all that, it comes out as exactly the same as if we had just ignored his number completely. So on a probability tree, people's own picks need not be included, but you must account for the number of possibilities being lessened by removing it.

We can see how player 1s pick affects player 2. If player 1 pulls number 2, then player 2 is left with 1, 3, 4, ... , 10. This is 9 numbers, any of which he can pick. So the probability of picking a particular on is 1/9 again. This is a bit disconcerting as it's the same probability as for player 1 picking a number!

If player 1 takes any other number than 2, player 2 then has his own number plus 8 others left. But we have to exclude his own number. So there's really only 8. The probability he pulls any of the remaining numbers is 1/8, and there will be 8 such branches.

Aractus: Did you end up with 5/36 as the probability for 4 players? I calculated that and it agreed with my coding experiment. I wasn't too sure what your final answer was.

I found there was actually only two ways player 4 ended up with his own number: 2 3 1 4 and 3 1 2 4

All other branches either pick a 4 premuturely or else a player gets his own number.

Probabilities 1/18 and 1/12 respectively; giving a total of 5/36

[Whateverist]

My brain is rebelling against thinking any more about the problem at this time. Gawd knows what tomorrow may bring.

[robvalue]

Lol ok

I can pull up the post I'm talking about, should you be interested in the future.

I think you're stuck on the idea that each combination must have the same probability. Very often, that is the case. But the exclusion of one's own number screws with the natural order, and all possibiliities are no longer equal.

Each branch is equal from a particular point, but the number of branches from each point shifts about.

[robvalue]

I started doing the tree for 5 people. It's not too bad. I noticed a couple of things:

1) Any situation where you're left with 4 and 5 for the last two players is an instant lose. Player 4 must take number 5, and so it's over.

2) There is a lot of repetition in the tree. I think Aractus was referring to this with his notation. You end up with several ways of getting to the same set of numbers left (such as 3 and 5, say). So from that point, it's only necessary to continue one of these branches to completion and then you can collect together the probability of getting to that position.

[BrianSoddingBoru4]

Quick question: Did anybody shake hands with anybody else?

Boru

[robvalue]

I've calculated the probability of that is 983. I may have to recheck it.

I think the key to solving this is finding a way to systematically label the points of the tree, and to be able to catalogue the redundancy.

Maybe. There may be a more cleverererer way I haven't thought of yet.

[emjay]

Hi rob and Aractus, thanks for your replies the other day. They were both very interesting. Probability is one of my favourite subjects and I'm never happier than when I'm making little board or computer games based on it, but that was back when I had a lot of time on my hands. Now I don't so as much as I could see myself getting obsessed with this, and whiling away the hours trying to figure it out, I just don't have the time... so just saying it looks fun but I'm gonna have to leave you to it. Have fun