Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I found this question on http://www.cs.uwm.edu/classes/cs317/ I tried to solve it because I have a quals exam on the theory courses next month. Please check my answer if it is correct or not. I assumed that $X$ ( random variable) is equal to the number of rounds coin-flipping.

Suppose $n$ people, $n \ge 3$ play the odd person out game to decide who will buy refreshments. The game works as follows. Everyone flip a fair coin simultaneously. If all the coins but one come up the same, the person whose coin comes up different buys the refreshments.

Otherwise, the people flip the coins again and continue until just one coin comes up dierent from all the others. We would like to know the expected number of rounds of coin- flipping needed to decide the odd person out with $n$ people. Notice that we can view a round of coin-flipping as a "success" if an odd person out is chosen on that round; otherwise, it is a "failure". The game then is interested in reaching a successful round.

a. What is the probability of success? of failure?

My answer is : probability of success is $p$, probability of failure is $(1-p)$.

b. What is the probability that $k$ rounds are needed for a success to show up?

My answer is: $(1-p)^{k-1}p$

c. What is the expected number of rounds needed for the game to end? $E(x) = 1/p$.

share|improve this question
    
You have not told us what p is? –  echoone Aug 3 '12 at 9:37
    
Also, in answer to b) you have written 'i' instead of '1'. Seems to be a typo. Otherwise the answers are correct given p, but try to actually find p. It is not that hard. –  Wonder Aug 3 '12 at 9:59
add comment

2 Answers

The probability of exactly one head if $n$ fair coins are tossed is $\binom{n}{1}\left(\frac{1}{2}\right)^n$. The probability of exactly one tail is the same. So the probability of "success" in any round is given by $p$, where $$p=2\binom{n}{1}\left(\frac{1}{2}\right)^n=\frac{2n}{2^n}=\frac{n}{2^{n-1}}.$$ The rest of your calculations are correct. In particular, the expected number of rounds is $\frac{1}{p}$, which in this case is $\frac{2^{n-1}}{n}$.

As you recognized, if the random variable $X$ measures the number of rounds, then $X$ has geometric distribution. The probability that $X=k$ is $(1-p)^{k-1}p$.

share|improve this answer
add comment

To calculate $p$, I recommend the counting method to answer this question because it is intuitive and gives a good overview of this simple problem.

  1. Count the total number of outcomes: $$\underbrace{2\cdot2\cdot2\cdot\ldots\cdot2}_{n\text{ times}} = 2^n.$$

  2. Count the number of possibilities where only one is different. There are two cases. Either the Head is the only coin, or the Tail is the only coin. In each cases, you have one possibility by people playing. Either it's the first guy, or the second one, or the third one, or the $n$th one. Therefore you have $2n$ outcomes where one of the coin is different to the rest of the coin.

  3. Therefore, by counting method, you can get the probability: $$ p=\frac{2n}{2^{n}} = \frac{n}{2^{n-1}}.$$

To be more visual, let's represent a $4$-bit binary value ($4$ people playing the game):

$0000$

$0001$ <= Only one 1

$0010$ <= Only one 1

$0011$

$0100$ <= Only one 1

$0101$

$0110$

$0111$ <= Only one 0

$1000$ <= Only one 1

$1001$

$1010$

$1011$ <= Only one 0

$1100$

$1101$ <= Only one 0

$1110$ <= Only one 0

$1111$

As you can see, it is a really easy way to get the probability of success, and it is correct regarding the binomial probability law that André Nicolas stated (it's reduced a bit as it is a fair coin).

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.