|
N children have decided to choose among them one who stays to count (while the others go and hide) by flipping a coin. What is the probability that the one who stays to count is decided on the nth round of coin flipping, when the one who gets a different side of the coin than the others is the one who stays and counts?
My "reasoning":
P("second child "loses"")=1/2
P("third child "loses"")=1/(2^2)
P("Nth child "loses"")=1/(2^N-1)
These are disjoint cases so the probability that the "loser" is decided on the first round is the sum of 1/(2^k) where k goes from 1 to N-1. Therefore the probability that the "loser" would be decided on the nth round is the sum of 1/(2^k) where k goes from 1 to nN-1. This is a geometric sum so the result would be 1-(1/(2^nN-1)).
The answer given in the book is p(1-p)^n-1, where p=N/2^(N-1).
That would be (N/2^(N-1))(1-(N/2^(N-1)))^n-1. This makes no sense to me because if for example there were 2 children deciding who hides and who seeks the probability that the seeker would be decided on the first round would be [(N=2,n=1)]:
(2/2^(2-1))(1-(2/2^(2-1)))^1-1=(2/2)*1=1
So what am I missing?
|
The chance of the event happening on the Nth toss is:
p = [ n * 1 * 0.5 ^ (n - 1) ]
n = (n choose (n-1)) (any one of the n people could have the opposite)
1 = the one person could get either head or tail, does not affect probability
0.5 ^ (n - 1) = the remaining (n-1) people must get the opposite of the one person, hence the 0.5
For this to actually happen, on the previous (n-1) tosses, the previous condition must be false:
(1 - p ) ^ (n - 1)
Combine them together, you get:
p * (1 - p) ^ (n - 1)
|
Let me see if I'm understanding the problem correctly. In each round, every single child flips a coin. If only one child doesn't match the others, that child becomes the counter. Otherwise, repeat the round. I assume this is what the problem is because the solution matches with this description.
If so, then the fault with your reasoning is that you cannot know that the second child is the loser until all the other children also flip their coins. Three person example:
First child flips H
Second child flips T (you would say child loses right here)
Third child flips T
Intuitively, it should be the case that all children have an equal probability of losing. The way you formulated the solution, the first child can never lose.
Cambium's solution looks correct. I'm going to present the solution in a different way, because sometimes it helps people to see things in multiple ways.
I usually look at probability in terms of the space of all possibilities. In this case, there are 2^N possible results for each round, where a result is the coin flips that the children get. Back to the three person example, here are the 2^3=8 possible outcomes.
HHH
HHT
HTH
THH
HTT
THT
TTH
TTT
Now, we want to figure out how many of these possible results are "losing" results (i.e. one child is different from the rest). In the three person case, we see there are 6 possibilities. Let's solve the general case.
Consider the scenario where only one child flips H. Using combinatorics, we can represent this as a choosing problem, where we only choose one child as the losing child.
(N choose 1) = N
The tails case is symmetric, so we now can see that there are 2*N possible results that are considered "losing" results. Putting it all together, we can see that the probability is:
2*N / (2^N) -------> N / (2^(N-1))
From here, you can just apply the geometric sequence to solve the rest of the problem.
It should be noted that this method works because all results are equally likely. If you have a problem where the likelihood of events is not equal, like with an unfair coin, then you would have to do weighted averages to compensate.
|
I think the notes above are too complicated. There are 2^n total possible outcomes, and out of those there are only 2 instances of the nth child losing: either HHHH....T or TTTTT....H, the probability is 2/(2^n), or 1/(2^(n-1)). OP you just missed a parenthesis, and you don't need to sum anything. The question asks you the probability that it is decided on the nth round, not by the nth round. Read more carefully.
Edit: this assumes a fair coin and n > 1 obviously. Base case is p = 0 for n = 1. In response to the post above: note that combination like HTH would have resulted on the second child losing, not the third.
|
|
|
|
|
|
EPT
