Question

Suppose n people, n ≥ 3, play "odd person out" to decide who will buy the next round of refreshments. The n people each 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 different from all the others. a) What is the probability that the odd person out is decided in just one coin flip? b) What is the probability that the odd person out is decided with the kth flip? c) What is the expected number of flips needed to decide odd person out with n people?

Answer 1

Answer:

Assume that all the coins involved here are fair coins.

a) Probability of finding the "odd" person in one round: $\displaystyle n \cdot \left(\frac{1}{2}\right)^{n - 1}$.

b) Probability of finding the "odd" person in the $k$th round: $\displaystyle n \cdot \left(\frac{1}{2}\right)^{n - 1} \cdot \left( 1 - n \cdot \left(\frac{1}{2}\right)^{n - 1}\right)^{k - 1}$.

c) Expected number of rounds: $\displaystyle \frac{2^{n - 1}}{n}$.

Step-by-step explanation:

a)

To decide the "odd" person, either of the following must happen:

• There are $(n - 1)$ heads and $1$ tail, or
• There are $1$ head and $(n - 1)$ tails.

Assume that the coins here all are all fair. In other words, each has a $50\,\%$ chance of landing on the head and a

The binomial distribution can model the outcome of $n$ coin-tosses. The chance of getting $x$ heads out of

• The chance of getting $(n - 1)$ heads (and consequently, $1$ tail) would be $\displaystyle {n \choose n - 1}\cdot \left(\frac{1}{2}\right)^{n - 1} \cdot \left(\frac{1}{2}\right)^{n - (n - 1)} = n\cdot \left(\frac{1}{2}\right)^n$.
• The chance of getting $1$ heads (and consequently, $(n - 1)$ tails) would be $\displaystyle {n \choose 1}\cdot \left(\frac{1}{2}\right)^{1} \cdot \left(\frac{1}{2}\right)^{n - 1} = n\cdot \left(\frac{1}{2}\right)^n$.

These two events are mutually-exclusive. $\displaystyle n\cdot \left(\frac{1}{2}\right)^n + n\cdot \left(\frac{1}{2}\right)^n = 2\,n \cdot \left(\frac{1}{2}\right)^n = n \cdot \left(\frac{1}{2}\right)^{n - 1}$ would be the chance that either of them will occur. That's the same as the chance of determining the "odd" person in one round.

b)

Since the coins here are all fair, the chance of determining the "odd" person would be $\displaystyle n \cdot \left(\frac{1}{2}\right)^{n - 1}$ in all rounds.

When the chance $p$ of getting a success in each round is the same, the geometric distribution would give the probability of getting the first success (that is, to find the "odd" person) in the $k$th round: $(1 - p)^{k - 1} \cdot p$. That's the same as the probability of getting one success after $(k - 1)$ unsuccessful attempts.

In this case, $\displaystyle p = n \cdot \left(\frac{1}{2}\right)^{n - 1}$. Therefore, the probability of succeeding on round $k$ round would be

$\displaystyle \underbrace{\left(1 - n \cdot \left(\frac{1}{2}\right)^{n - 1}\right)^{k - 1}}_{(1 - p)^{k - 1}} \cdot \underbrace{n \cdot \left(\frac{1}{2}\right)^{n - 1}}_{p}$.

c)

Let $p$ is the chance of success on each round in a geometric distribution. The expected value of that distribution would be $\displaystyle \frac{1}{p}$.

In this case, since $\displaystyle p = n \cdot \left(\frac{1}{2}\right)^{n - 1}$, the expected value would be $\displaystyle \frac{1}{p} = \frac{1}{\displaystyle n \cdot \left(\frac{1}{2}\right)^{n - 1}}= \frac{2^{n - 1}}{n}$.