Skip to *Using Hoeffding's bound* subtitle below for the answer.

**Problem with the Chebyshev confidence interval**

As mentioned by Carlo, we have $\sigma^2 \le \frac{1}{4}$. This follows from $\text{Var}(X) \le \mu(1-\mu)$. Therefore a confidence interval for $\mu$ is given by
$$
P(|\bar{X}-\mu| > \varepsilon) \le \frac{1}{4n\varepsilon^2}.
$$
The problem is that the inequality is, in a certain sense, quite loose when $n$ gets large. We can show how bad it can get using the [Berry-Esseen theorem][1], pointed out by Yves. Let $X_i$ have a variance $\tfrac{1}{4}$, the worst possible case. The theorem implies that
$
P(|\bar X - \mu| > \tfrac{\varepsilon}{2\sqrt{n}}) \le 2\, \text{SF}(\varepsilon) + \tfrac{8}{\sqrt{n}},
$
where $\text{SF}$ is the survival function of the standard normal distribution. In particular, with $\varepsilon = 16$, we get $\text{SF}(8) \approx e^{-58}$ (according to Scipy), so that essentially
$$
P(|\bar X - \mu| > \tfrac{8}{\sqrt{n}}) \le \tfrac{8}{\sqrt{n}} + 0, \qquad (*)
$$
whereas the Chebyshev inequality implies
$$
P(|\bar X - \mu| > \tfrac{8}{\sqrt{n}}) \le \tfrac{1}{256}.
$$
This means that *for $n$ sufficiently large* (or equivalently $\varepsilon$ sufficiently small in $(1)$), *the confidence intervals obtained from the Chebyshev inequality are needlessly large.* Note that I did not try to optimize the bound given in $(*)$, the result here is only of conceptual interest.


----------


**Comparing the lenghts of the confidence intervals**

Fix a level $1 > \alpha > 0$ and consider the $\alpha$-level confidence interval lengths $\ell_Z(\alpha, n)$ and $\ell_C(\alpha, n)$ obtained using the normal approximation ($\sigma = \tfrac{1}{2}$) and the Chebyshev inequality, repectively. It turns out that $\ell_C(\alpha, n)$ is a constant times bigger than $\ell_Z(\alpha, n)$, independently of $n$. Precisely, for all $n$, 
$$
\ell_C(\alpha, n) = \kappa(\alpha) \ell_Z(\alpha, n), \quad \kappa(\alpha) = \left(\text{ISF}\left(\tfrac{1-\alpha}{2}\right) \sqrt{1-\alpha}\right)^{-1},
$$
where $\text{ISF}$ is the inverse survival function of the standard normal distribution. I plot below the multiplicative constant.

$\hskip 1in$[![enter image description here][2]][2]

This is nothing too dramatic (I expected a larger factor; you can make your own mind about it): the $95\%$ level confidence interval obtained using the Chebyshev inequality is about $2.3$ times bigger than the same level confidence interval obtained using the normal approximation.


----------

**Using Hoeffding's bound**

Hoeffding's bound gives
$$
P(|\bar X - \mu| \geq \varepsilon) \leq e^{-2n \varepsilon^2}.
$$
Thus an $\alpha$-level confidence interval for $\mu$ is 
$$
(\bar X - \varepsilon, \bar X + \varepsilon), \quad \varepsilon = \sqrt{\frac{-\ln \tfrac{1-\alpha}{2}}{2n}},
$$
of length $\ell_H (\alpha, n) = 2\varepsilon$. I plot below the lengths of the different confidence intervals for $\alpha = 0.95$.

$\hskip 0.5in$[![enter image description here][3]][3]

We have a winner.


  [1]: https://en.wikipedia.org/wiki/Berry%E2%80%93Esseen_theorem
  [2]: https://i.sstatic.net/nK4pv.png
  [3]: https://i.sstatic.net/L2qFn.png