**Problem with the Chebychev 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. This follows from 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 Chebychev 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 Chebychev inequality are of over-estimated length or of under-estimated level.** 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 Chebychev 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) = \frac{\ell_Z(\alpha, n)}{\text{ISF}((1-\alpha)/2) \sqrt{1-\alpha}} =: \kappa(\alpha) \ell_Z(\alpha, n),
$$
where $\text{ISF}$ is the inverse survival function of the standard normal distribution. I plot below the multiplicative constant.

[![enter image description here][2]][2]

This is nothing too dramatic: the $95\%$ level confidence interval obtained using the Chebychev inequality is only about $2.3$ times bigger than the same level confidence interval obtained using the normal approximation.


----------

I have not answered the whole question. Left to answer is: now what? What is good statistical practice here and are there references to support any claim?


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