How to use upper bound for Bernoulli distribution? Suppose we test a prediction method, a neural set for example, on set of $n$ new test cases. Let $X_i = 1$ if the predictor is wrong and $X_i = 0$ otherwise. Then $\bar X_n = \dfrac1n \sum\limits_{i=1}^nX_i$ is the observed error rate. Each $X_i$ may be regarded as a Bernoulli with unknown mean $p$. How likely is $X_i$ to not be within $ε$ of $p$? For $ε = 0.2$ and $n = 100$ the bound is $0.0625$.
Can you help me with how to use this bound?
 A: This upper bound is just an application of Chebyshev's inequality. Without using explicit the distribution you can find an upper bound:
$${P}\left[\left|X-\mu\right|\geq \epsilon\right] \leq \frac{\sigma^2}{\epsilon^2}$$
In your case $X=\frac{1}{n}\sum\limits_{i=1}^nX_i$, where $X_i$ is bernoulli distributed as $X_i\sim Ber(p)$. Then we have $\mathbb E(X)=\ p$ and $Var(X)=\sigma^2=\frac{p\cdot (1-p)}{100}$. 

We calculate the maximum of $\frac{p\cdot (1-p)}{100}$ to ensure that the inequality holds (worst case). We can ignore the factor $\frac{1}{100}$ here.
I. Derivative of $f(p)=p\cdot (1-p)=p-p^2$ and setting it equal to zero.
$f^{'}(p)=1-2p=0\Rightarrow p=0.5$ 
II Proving if it is a (relative) minimum or a (relative) maximum
$f^{''}(p)=-2$. Thus $f^{''}(0.5)=-2<0\Rightarrow \text{maximum at p=0.5}$

Finally we can input all values to obtain the upper bound. It is given that $\epsilon=0.2$ and we have $\sigma^2=\frac{0.5\cdot 0.5}{100}=0.0025$
$${P}\left[\left|X-0.5\right|\geq 0.2\right] \leq \frac{0.0025}{0.2^2}=0.0625$$

We have the random variable  $X=\frac1n \sum\limits_{i=1}^n X_i$. We want the variance. $Var\left(\frac1n \sum\limits_{i=1}^n X_i\right)=\frac1{n^2}Var\left( \sum\limits_{i=1}^n X_i\right)=\frac1{n^2}\left[Var\left(  X_1\right)+Var\left(  X_2\right)+Var\left(  X_3\right)+\ldots Var(X_n)\right]$
$=\frac1{n^2}\left[n\cdot Var\left(  X_1\right)\right]=\frac1{n}\left[ Var\left(  X_1\right)\right]$
Since $X_i$ is bernoulli distributed the variance of $X_1$ is $p\cdot (1-p)$. Therefore 
$$Var\left(\frac1{100} \sum\limits_{i=1}^{100} X_i\right)=\frac1{100}\cdot p\cdot (1-p)$$
