Problem from an old exam:
We have $m$ coins, one of which is fake. We know that on a real coin, heads occur with a probability of $\frac{1}{2}$, and on the fake coin, it occurs with a probability of $p > \frac{1}{2}$.
We search for the fake coin in the following way: we toss each coin $n$ times and count the number of heads. The procedure indicates the coin with the most heads (in case of a tie, the procedure does not indicate any coin).
Prove that for every $p > \frac{1}{2}$, $m \geq 2$, and $\epsilon > 0$, there exists an $n$ such that the above procedure identifies the fake coin with a probability of at least $1-\epsilon$. Find $n$.
$ Y_i = \begin{cases}
Y_i = 1, & \text{if the } i\text{-th toss of fake coin results in heads} \\
Y_i = 0, & \text{otherwise}
\end{cases}$
Let $Y = \sum_{i=1}^n{Y_i}$ denote the number of heads in $n$ tosses of a fake coin
We have $$\mathbb{E}[Y] = n \cdot p$$
$$\text{Var}[Y] = np(1 + (n-1)p) – (np)^2$$
Let $X_k$ denote the number of heads in $n$ tosses of a k-th fair coin.
$$
\mathbb{E}[Y^2] = \mathbb{E}\left[\sum Y_i Y_i + \sum\limits_{i \neq j} Y_i Y_j\right] = \mathbb{E}[Y] + \mathbb{E}\left[\sum_{i=1}^{n}\sum_{j=1}^{n} Y_i Y_j\right]
$$
For the test to correctly identify the fake coin, $P(\max(X_1, …, X_{n-1}) < Y)$ must hold, i.e., $P((X_1 < Y) \land (X_2 < Y) \ldots \land (X_{n-1} < Y))$.
I want to calculate $P(X < Y) = P(X – Y < 0)$.
Let $D = X – Y$. We have
$$\mathbb{E}[D] = \mathbb{E}[X] – \mathbb{E}[Y]$$
$$ Var[D] = Var[Y] + Var[X]$$
How can I find $P(D < 0)$ with this information? Is this approach suitable for this question?
Thanks.
Best Answer
You can compute this by a relatively trivial union bound. Using the notation in the post, we have that if $X = \max(X_1, \dots, X_{m-1})$, then it suffices to show that $P(X \geq Y) \to 0$ for fixed $p > 1/2, m \geq 2$. $$ P(X \geq Y) = P(X_1 \geq Y \text{ or } X_2 \geq Y \text{ or } \dots \text{ or } X_{m-1} \geq Y ) \leq \sum_{i=1}^{m-1} P(X_i \geq Y) = \sum_{i=1}^{m-1} P(X_i - Y \geq 0). $$ Put $Z_i = Y - X_i$; we have $$E[Z_i] = n(p - 1/2) = n\mu > 0$$ and $$\operatorname{Var}(Z_i) = \operatorname{Var}(X_i) + \operatorname{Var}(Y) = \frac{n}{4} + np(1-p) = n\sigma^2 > 0$$ for some positive constants $\mu, \sigma^2$. A Chebyshev bound gives immediately that $$ P(Z_i \leq 0) \leq P(|Z_i - n\mu| \geq n\mu) \leq \frac{n\sigma^2}{(n\mu)^2} = \frac{\sigma^2}{n\mu^2} $$ so $$ P(X \geq Y) \leq \sum_{i=1}^{m-1}P(X_i - Y \geq 0) = \sum_{i=1}^{m-1}P(Z_1 \leq 0)= \frac{m\sigma^2}{n \mu^2}. $$ Clearly this is goes to $0$ as $n \to \infty$, as desired.
In general I suspect that the moments of $X$ might be annoying to calculate, especially in an exam, so one would like to pass to individual $X_i$.