[Math] Chebyshev and Hoeffding Inequality

probabilitystatistics

I am kind of stuck on a problem that goes as follows.

There are two coins in front of you, one is fair, the other has probability 3/4 of ‘Heads’. You take one of the two coins (without knowing if it is the fair one or the other one), and toss it n times. Let $X_n=\frac{number.\: of\: heads}{n}$

(a) How would you make a prediction (from the value of Xn) on whether the coin is the fair one or the biased one?

b) Using Chebyshev’s inequality, show that for n ≥ 320, the prediction is correct with probability at least 95%.

(c) Using Hoeffding’s inequality, show that for n ≥ 119, the prediction is correct with probability at least 95%.

So I managed to calculate the Variance of the binomial random variable but, the thing I dont understand is how we can show with 95% with out a value of $\epsilon$, would I be solving for 0.95 and trying to find epsilon in this case ? I just wanted to confirm.

Thanks in advance

Best Answer

There are many ways of making a prediction.

Let us denote by $p$ the mean of the Bernoulli trials. We have two complementary hypothesis:

  • $H_0$ is the hypothesis $p = 1/2$
  • $H_1$ is the hypothesis $p = 3/4$

We could define the following test:

  • We accept $H_0$ if and only if the empirical mean $\overline{X}:= \frac{1}{n}\sum_{i=1}^n X_i$ is less or equal then $5/8$ (i.e.: the empirical mean is nearer to $1/2$ then to $3/4$).

What is the probability of the prediction being wrong? $$\mathbb{P}(\text{ wrong estimate }| p = 1/2) = \mathbb{P}(\overline{X} > 5/8 | p = 1/2)$$

We find:

  • Chebychev: $$\mathbb{P}(\overline{X} > 5/8 | p = 1/2) \le \mathbb{P}(|\overline{X} - 1/2|^2 > 1/64 | p = 1/2) \le \frac{1/4}{n (1/64)} = 0.05 \text{ if n = $320$ } $$

  • Chernoff: $$\mathbb{P}(\overline{X} - 1/2 > 1/8 | p = 1/2) \le e^{-2n(1/64)} \approx 0.024 \text{ if $n = 119$ }$$

Similarly one can deal with:

$$ \mathbb{P}(\text{ wrong estimate }| p = 3/4) = \mathbb{P}(\overline{X} \le 5/8 | p = 3/4) $$

So the $\epsilon$ you were missing in the variance is actually imposed by the test you choose.

P.s.: you might see that with this test you get that Chernoff errs with probability less then $5\%$ already after $96$ trials.

Furthermore you should notice that since Chernoff does not depend on the distribution (but only on the boundedness of the distribution) you do not have to check the Chernoff estimate again in the second case ($p= 3/4$).

Related Question