Return to 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. An improvement is given by Hoeffding's bound and shown below. However, we can also demonstrate how bad it can get using the Berry-Esseen theorem, 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}(16) \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}. $$ Note that I did not try to optimize the bound given in $(*)$, the result here is only of conceptual interest.

Comparing the lengths of the confidence intervals

Consider the $(1-\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{\alpha}{2}\right) \sqrt{\alpha}\right)^{-1}, $$ where $\text{ISF}$ is the inverse survival function of the standard normal distribution. I plot below the multiplicative constant.

$\hskip 1in$

In particular, 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 2e^{-2n \varepsilon^2}. $$ Thus an $(1-\alpha)$-level confidence interval for $\mu$ is $$ (\bar X - \varepsilon, \bar X + \varepsilon), \quad \varepsilon = \sqrt{\frac{-\ln \tfrac{\alpha}{2}}{2n}}, $$ of length $\ell_H (\alpha, n) = 2\varepsilon$. I plot below the lengths of the different confidence intervals (Chebyshev inequality: $\ell_C$; normal approximation ($\sigma = 1/2$): $\ell_Z$; Hoeffding's inequality: $\ell_H$) for $\alpha = 0.05$.

$\hskip 0.5in$

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| \geq \varepsilon) \le \frac{1}{4n\varepsilon^2}. $$ The problem is that the inequality is, in a certain sense, quite loose when $n$ gets large. An improvement is given by Hoeffding's bound and shown below. However, we can also demonstrate how bad it can get using the Berry-Esseen theorem, 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| \geq \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}(16) \approx e^{-58}$ (according to Scipy), so that essentially $$ P(|\bar X - \mu| \geq \tfrac{8}{\sqrt{n}}) \le \tfrac{8}{\sqrt{n}} + 0, \qquad (*) $$ whereas the Chebyshev inequality implies $$ P(|\bar X - \mu| \geq \tfrac{8}{\sqrt{n}}) \le \tfrac{1}{256}. $$ Note that I did not try to optimize the bound given in $(*)$, the result here is only of conceptual interest.

Comparing the lengths of the confidence intervals

Consider the $(1-\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{\alpha}{2}\right) \sqrt{\alpha}\right)^{-1}, $$ where $\text{ISF}$ is the inverse survival function of the standard normal distribution. I plot below the multiplicative constant.

$\hskip 1in$

In particular, 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 2e^{-2n \varepsilon^2}. $$ Thus an $(1-\alpha)$-level confidence interval for $\mu$ is $$ (\bar X - \varepsilon, \bar X + \varepsilon), \quad \varepsilon = \sqrt{\frac{-\ln \tfrac{\alpha}{2}}{2n}}, $$ of length $\ell_H (\alpha, n) = 2\varepsilon$. I plot below the lengths of the different confidence intervals (Chebyshev inequality: $\ell_C$; normal approximation ($\sigma = 1/2$): $\ell_Z$; Hoeffding's inequality: $\ell_H$) for $\alpha = 0.05$.

$\hskip 0.5in$

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. An improvement is given by Hoeffding's bound and shown below. However, we can also demonstrate how bad it can get using the Berry-Esseen theorem, 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}(16) \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}. $$ Note that I did not try to optimize the bound given in $(*)$, the result here is only of conceptual interest.

Comparing the lengths of the confidence intervals

Consider the $(1-\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{\alpha}{2}\right) \sqrt{\alpha}\right)^{-1}, $$ where $\text{ISF}$ is the inverse survival function of the standard normal distribution. I plot below the multiplicative constant.

$\hskip 1in$

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 2e^{-2n \varepsilon^2}. $$ Thus an $(1-\alpha)$-level confidence interval for $\mu$ is $$ (\bar X - \varepsilon, \bar X + \varepsilon), \quad \varepsilon = \sqrt{\frac{-\ln \tfrac{\alpha}{2}}{2n}}, $$ of length $\ell_H (\alpha, n) = 2\varepsilon$. I plot below the lengths of the different confidence intervals (Chebyshev inequality: $\ell_C$; normal approximation ($\sigma = 1/2$): $\ell_Z$; Hoeffding's inequality: $\ell_H$) for $\alpha = 0.05$.

$\hskip 0.5in$

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. An improvement is given by Hoeffding's bound and shown below. However, we can also demonstrate how bad it can get using the Berry-Esseen theorem, 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}(16) \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}. $$ Note that I did not try to optimize the bound given in $(*)$, the result here is only of conceptual interest.

Comparing the lengths of the confidence intervals

Consider the $(1-\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{\alpha}{2}\right) \sqrt{\alpha}\right)^{-1}, $$ where $\text{ISF}$ is the inverse survival function of the standard normal distribution. I plot below the multiplicative constant.

$\hskip 1in$

In particular, 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 2e^{-2n \varepsilon^2}. $$ Thus an $(1-\alpha)$-level confidence interval for $\mu$ is $$ (\bar X - \varepsilon, \bar X + \varepsilon), \quad \varepsilon = \sqrt{\frac{-\ln \tfrac{\alpha}{2}}{2n}}, $$ of length $\ell_H (\alpha, n) = 2\varepsilon$. I plot below the lengths of the different confidence intervals (Chebyshev inequality: $\ell_C$; normal approximation ($\sigma = 1/2$): $\ell_Z$; Hoeffding's inequality: $\ell_H$) for $\alpha = 0.05$.

$\hskip 0.5in$

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. An improvement is given by Hoeffding's bound and shown below. However, we can also demonstrate how bad it can get using the Berry-Esseen theorem, 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}(16) \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}. $$ Note that I did not try to optimize the bound given in $(*)$, the result here is only of conceptual interest.

Comparing the lengths 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$

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 2e^{-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 (Chebyshev inequality: $\ell_C$; normal approximation ($\sigma = 1/2$): $\ell_Z$; Hoeffding's inequality: $\ell_H$) for $\alpha = 0.95$.

$\hskip 0.5in$

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. An improvement is given by Hoeffding's bound and shown below. However, we can also demonstrate how bad it can get using the Berry-Esseen theorem, 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}(16) \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}. $$ Note that I did not try to optimize the bound given in $(*)$, the result here is only of conceptual interest.

Comparing the lengths of the confidence intervals

Consider the $(1-\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{\alpha}{2}\right) \sqrt{\alpha}\right)^{-1}, $$ where $\text{ISF}$ is the inverse survival function of the standard normal distribution. I plot below the multiplicative constant.

$\hskip 1in$

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 2e^{-2n \varepsilon^2}. $$ Thus an $(1-\alpha)$-level confidence interval for $\mu$ is $$ (\bar X - \varepsilon, \bar X + \varepsilon), \quad \varepsilon = \sqrt{\frac{-\ln \tfrac{\alpha}{2}}{2n}}, $$ of length $\ell_H (\alpha, n) = 2\varepsilon$. I plot below the lengths of the different confidence intervals (Chebyshev inequality: $\ell_C$; normal approximation ($\sigma = 1/2$): $\ell_Z$; Hoeffding's inequality: $\ell_H$) for $\alpha = 0.05$.

$\hskip 0.5in$