# odd person out game

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$.

-
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

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$.

-

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).

-