Let's assume we have a biased coin with probabilities $\frac{4}{5}$ and $\frac{1}{5}$ and we don't know to which event (head or tail) the probabilities belong to.
But we want to decide it by majority after n tosses.
(1) What's the probability of error of such a decision?
My approach:
Let $X = \sum_{i=1}^n X_i$ be the sum of the outcomes of this binomial distributed random variable after $n$ tosses. As a given note says, we can use the following Chernoff-bound.
$$ \begin{equation*} \mathbb{P}(X \leq (1-\beta) \cdot E(X)) \leq \exp(- \frac{E[X] \beta²}{2}), \beta\in (0,1) \end{equation*} $$
If we represent the event head by $1$ and tail by $0$ and the sum $X$ is greater then $n/2$, head should be the one event with probability $4/5$ right?
Using the Chernoff-bound gives us
$$ \begin{align*} \mathbb{P}(X \leq \frac{n}{2}) &= \mathbb{P}(X \leq (1-\frac{3}{8})\frac{4n}{5})\\ &\leq \exp(- \frac{9n}{160}) \end{align*} $$
So, how to move on and what is the probability of error now?
Thanks and happy Easter!