Russian roulette probability question

[AlphaNumeric]

Suppose N people are playing Russian roulette. p1 plays p2, the winner of which plays p3, the winner of which plays p4, ...... , the winner of which plays pN. After N-1 games there's 1 person left. Obviously this is unfair on p1, he would have to win all N-1 games to survive, while pN only needs to win 1.

Suppose we now play delayed Russian roulette, where the player doesn't die immediately but their loss is recorded. All $$\frac{1}{2}N(N-1)$$ pairings are listed and everyone plays everyone. At each step one of each pairing definitely loses but it is equally likely to be one as the other. If someone loses a game at any point they are shot at the end by a heartless referee. What is the expected number of survivors at the end?

I know it is less than 1, because it is harder to survive than normal RR and normal RR has exactly 1 survivor. Any one person has to survive N-1 games, which has probability $$\frac{1}{2^{N-1}}$$ but you can't just sum over N to get $$\frac{N}{2^{N-1}}$$, they aren't independent, right? A generalisation is to say the 'gun' fires a blank with probability $$\alpha$$ each time but that just means $$\frac{1}{2} \to \frac{\alpha}{2}$$ I think.

This smacks of being like a first year probability question but I always sucked at working out how many people did this to get that expectation of this many whatevers. And before anyone asks, I'm not setting up my own meaner, harder version of fight club. And even if I were the first rule is not to talk about it

 

[mathman]

The maximum number of survivors is 1, since if he won all games, everyone else has lost to him.

 

[AlphaNumeric]

I know the maximum, I want the expected number of survivors. In some games there will be no survivors, in some games there will be 1. The question is thus equivalent to "What fraction of the time would there be a survivor at all?".

 

[przyk]

Any one person has to survive N-1 games, which has probability $$\frac{1}{2^{N-1}}$$ but you can't just sum over N to get $$\frac{N}{2^{N-1}}$$, they aren't independent, right?

They don't need to be independent in order for the probabilities to add. They need to be mutually exclusive.

 

[Tach]

I know the maximum, I want the expected number of survivors. In some games there will be no survivors, in some games there will be 1. The question is thus equivalent to "What fraction of the time would there be a survivor at all?".

If you restate the problem this way, then the simple answer is :

$$1-p(none)$$ where $$p(none)$$ is the probability for all the shooters to be killed. Your problem , as you constructed it, lacks the information necessary to calculate $$p(none)$$, so it is an ill-posed problem .

 

[AlphaNumeric]

They don't need to be independent in order for the probabilities to add. They need to be mutually exclusive.

Opps, yes I was thinking about multiplicative combinations. Suffice to say I don't get the feeling its just a matter of summing them because whether or not player 1 loses a particular game is related to whether or not his opponent does.

I'm certain its a straight forward problem for someone half decent at probability, I'm just not one of them.

$$1-p(none)$$ where $$p(none)$$ is the probability for all the shooters to be killed. Your problem , as you constructed it, lacks the information necessary to calculate $$p(none)$$, so it is an ill-posed problem .

Why is it ill posed? It can clearly be done by brute force, you write down all distinct unordered (i,j) pairs for i,j in 1,...,N,of which there will be $$\frac{1}{2}N(N+1)$$. You then consider all win-lose combinations for those, which will total $$2^{\frac{1}{2}N(N+1)}$$ possible outcome combinations and then you count how many of those have 0 survivors compared to the maximum possible of 1 survivor.

It's the sort of counting/combinatorics question I've always been useless at but which seems the bread and butter of undergrad probability courses (what little I remember from my own).

 

[Tach]

Why is it ill posed? It can clearly be done by brute force, you write down all (i,j) pairs for i,j in 1,...,N,of which there will be $$\frac{1}{2}N(N+1)$$. You then consider all win-lose combinations for those, which will total $$2^{\tfrac{1}{2}N(N+1)}$$ possible outcome combinations and then you count how many of those have 0 survivors compared to the maximum possible of 1 survivor.

You are missing the information required to calculate the 0 survivor vs. 1 survivor outcome, i.e. you are missing the probabilities associated with the outcome.

It's the sort of counting/combinatorics question I've always been useless at but which seems the bread and butter of undergrad probability courses (what little I remember from my own).

It is not the counting that you are mistaken about, it is the probabilities that are missing in your problem statement.

 

[AlphaNumeric]

You are missing the information required to calculate the 0 survivor vs. 1 survivor outcome, i.e. you are missing the probabilities associated with the outcome.

It is not the counting that you are mistaken about, it is the probabilities that are missing in your problem statement.

I said "At each step one of each pairing definitely loses but it is equally likely to be one as the other". In each duel it is 50/50 who wins, what additional information is required? With there being no asymmetry between any of the players and outcomes it comes down to counting, as each outcome in terms of "player 1 beat players 3, 5, 8 and 10, player 2 bear players 1,5,7 and 14, etc" are all equally likely.

 

[Tach]

I said "At each step one of each pairing definitely loses but it is equally likely to be one as the other". In each duel it is 50/50 who wins.

Then you have all the tools to calculate $$p(none)$$

 

[James R]

If each player plays N-1 games, and there is a 0.5 chance of losing each game, then the chance of a particular player not losing any games is $$(1/2)^{N-1}$$.

If that player does not losing any games, then all other players have lost at least one game.

So, the probability of one lone survivor is as given.

The problem of losing at least one game is that it opens the possibility that some other player has won all his games. This leads to a more complicated calculation, of course, and I don't think I want to spend the time thinking it through.

Clearly, Tach is being as useless and clueless as usual in this thread, making claims he cannot support and the usual kinds of incorrect statements we usually get from him. His standard response to all problems, I have found, is to tell the person posing the problem "I could solve this if I wanted to, but instead I'll just claim either (a) you are wrong, or (b) a solution is possible and I'll leave you to work it out yourself." This is Tach-code for "I don't know how to solve this, so I'll pretend I can solve it. That way, I boost my own ego."

 

[przyk]

Suffice to say I don't get the feeling its just a matter of summing them because whether or not player 1 loses a particular game is related to whether or not his opponent does.

In this case my impression is that it really is that simple. Normally you'd want to add P(player 1 wins and all the others lose) + P(player 2 wins and all the others lose) + ..., because all the events of the type "player n wins and all the others lose" are mutually exclusive. But in this case because there can only be a maximum of one winner, P(player n wins and all the others lose) = P(player n wins).

 

[Tach]

.

Clearly, Tach is being as useless and clueless as usual in this thread, making claims he cannot support and the usual kinds of incorrect statements we usually get from him.

Clearly you are as abusive as usual. If you engaged brain you would have found out that the solution I gave is valid and represents the general solution to the problem. $$p=1-p(none)$$ where $$p(none)$$ is the much easier to calculate probability that each player has lost at least one shootout. If you stopped trolling for a while you might become a much better person.

This leads to a more complicated calculation, of course, and I don't think I want to spend the time thinking it through.

Pot, meet kettle.

 

[James R]

Give us the expected number of winners, Tach. Or admit you cannot.

 

[Pete]

If each player plays N-1 games, and there is a 0.5 chance of losing each game, then the chance of a particular player not losing any games is $$(1/2)^{N-1}$$.

If that player does not losing any games, then all other players have lost at least one game.

So, the probability of one lone survivor is as given.

The problem of losing at least one game is that it opens the possibility that some other player has won all his games. This leads to a more complicated calculation, of course, and I don't think I want to spend the time thinking it through.

So for each player, the probability that they will survive is $$(1/2)^{N-1}$$.

It's naively tempting to just add them all up for a total probability of a lone survivor of $$\frac{N}{2^{N-1}}$$

My second thought was that this isn't correct, because it implies that more than one player might win...

but my third thought was that the events of each player winning are mutually exclusive events, so we can in fact naively add them up.

Expected number of winners = P(single survivor) = $$\frac{N}{2^{N-1}}$$

Edit - I see przyk beat me to it.

 

[Tach]

Give us the expected number of winners, Tach. Or admit you cannot.

Do you think that you can use the hint and calculate $$p(none)$$ all by yourself?

 

[James R]

Never mind, Tach. Other people beat you to it, and it's obvious you couldn't do it anyway.

 

[AlphaNumeric]

Do you think that you can use the hint and calculate $$p(none)$$ all by yourself?

You didn't give a hint, you gave the most basic probability identity, $$P( \bar{A} ) = 1 - P(A)$$. I think its pretty clear I was aware of that identity, my probability knowledge isn't zero.

In fact what I asked for was the expectation value, which that in its definition (for discrete outcomes) $$E(\textrm{pop} ) = \sum_{n} P(\textrm{pop} = n)\, n = P(\textrm{pop} = 0)\, 0 + P(\textrm{pop} = 1)\, 1 = P(\textrm{pop} = 1)$$ where $$\sum_{n} P(\textrm{pop} = n) = 1$$. Because the population can only be 0 or 1 this reduces to calculating a single probability coefficient. The fact I'd boiled down the question of "What is the expectation value?" to "What is this probability?" illustrates your 'hint' was redundant, never mind being trivial.

You then went on to do precisely as JamesR says you always do, challenging JamesR to do it by himself after he said that you'll pretend you can do it and then not do it.

As for everyone else, thanks for the help. It seems it was just as straight forward as I'd expected it to be but I needed a prod and a push to see it I'd done the N=3 case by brute (back of an envelope) force and gotten 1/4 vs 3/4, which gels with what has been said

 

[Guest254]

This is a question of expectation, which is a linear function. There's no need to talk about adding probabilities -- the sum is just a biproduct of the linearity of expectation. Let $$X_i$$ be an indicator function on the event that the ith person survives (meaning that $$X_i=1$$ if the ith person survives, and 0 otherwise). The total number of survivors is

$$ X = X_1 + \cdots + X_N$$

Now each of the $$X_i$$ are identically distributed, so when we take expectations (which is linear) we get

$$ \mathbb{E}(X) = \mathbb{E}(X_1+\cdots + X_N) = \mathbb{E}(X_1) + \cdots + \mathbb{E}(X_N) = \mathbb{E}(X_1) + \cdots + \mathbb{E}(X_1) = N\mathbb{E}(X_1) = Np_1 $$

where $$p_1$$ is the probability that the first person survives. But obviously $$p_1=2^{1-N}$$, so there's your answer.

 

[Tach]

You didn't give a hint, you gave the most basic probability identity, $$P( \bar{A} ) = 1 - P(A)$$. I think its pretty clear I was aware of that identity, my probability knowledge isn't zero.

In fact what I asked for was the expectation value, which that in its definition (for discrete outcomes) $$E(\textrm{pop} ) = \sum_{n} P(\textrm{pop} = n)\, n = P(\textrm{pop} = 0)\, 0 + P(\textrm{pop} = 1)\, 1 = P(\textrm{pop} = 1)$$ where $$\sum_{n} P(\textrm{pop} = n) = 1$$. Because the population can only be 0 or 1 this reduces to calculating a single probability coefficient. The fact I'd boiled down the question of "What is the expectation value?" to "What is this probability?" illustrates your 'hint' was redundant, never mind being trivial.

Let's make it simple, assume that N=3. Then:

1 loses to 2 AND wins against 3, $$p=\frac{1}{2^2}$$

AND

2 loses to 3 , $$p=\frac{1}{2}$$


OR, by symmetry:

1 loses to 3 AND wins against 2, $$p=\frac{1}{2^2}$$

AND

3 loses to 2 , $$p=\frac{1}{2}$$

Therefore $$p(none)=2 \frac{1}{2^2}\frac{1}{2}=\frac{1}{2^2}$$

The answer to the problem is $$1-p(none)=\frac{3}{2^2}$$

Now, try working the general case all by yourself. It is very easy when you understand the method. If you do it correctly, you should be getting$$\frac{n}{2^{n-1}}$$

You then went on to do precisely as JamesR says you always do, challenging JamesR to do it by himself after he said that you'll pretend you can do it and then not do it.

Don't make claims you can't back up.

 

[James R]

Tach:

You obviously haven't caught up with the conversation. The problem was solved in your absence.

Read back to see the full solution. You'll learn something.