Let $B(n,p)$ be a Binomial Distribution. We can estimate $p$ using $\hat{p} = \frac{\sum_{i=1}^m X_i}{m n}$, where $X_i \sim B(n,p)$ are i.d.d. and from Chebyshev's inequality we have

\begin{align*} \Pr\left[|p-\hat{p}| > \epsilon \sqrt{\frac{p(1-p)}{n}}\right] \leq \frac{1}{m \epsilon^2} \end{align*} since $\mathbb{E}[\hat{p}]=p,\ Var[\hat{p}] = \frac{p(1-p)}{mn}$. Therefore we can use $O(1/(\epsilon^2 \delta))$ samples and the above probability will be less that $\delta$.


I would like to find a way to obtain an estimator $\hat{q}$ such that it holds \begin{align*} \Pr\left[p < \hat{q} < p+ \epsilon \sqrt{\frac{p(1-p)}{n}}\right] \geq 1-\delta \end{align*} with $O(1/(\epsilon^2 \delta))$ samples. In other words I want the estimator $\hat{q}$ to be close to and greater than p with high probability.

  • 1
    $\begingroup$ Such an "estimator" would serve nicely as a $1-\delta$ UCL of the mean, so why not analyze any of the standard Binomial UCL procedures? $\endgroup$
    – whuber
    Commented Jun 9, 2017 at 15:08
  • $\begingroup$ There seems to be an error in your definition of $\hat{p}$: when you divide the sum by m times n, this is not an estimator for p, but for p/n. $\endgroup$
    – cdalitz
    Commented May 7, 2019 at 12:13

1 Answer 1


Chebychev's inequality gives a bound for

$$P(p-\gamma< \hat{p}<p+\gamma) = P(p<\hat{p}+\gamma<p+2\gamma)$$

You set $2\gamma:=\varepsilon\sqrt{p(1-p)/n}$, so setting

$$\hat{q}=\hat{p} + \gamma \approx \hat{p} + \frac{1}{2}\varepsilon\sqrt{\frac{\hat{p}(1-\hat{p})}{n}}$$

should add just the amount of bias such that $\hat{q}$ is centered in the interval of interest to the right of $p$.

Sidenote: You can obtain a much tighter bound of $O(\exp(-n\varepsilon^2)$ instead of $O(1/(n\varepsilon^2))$ by using Hoeffdings' inequality instead of Chebysheff's inequality:

$$P(|\hat{p}-p|>\varepsilon) \leq 2\cdot e^{-2n\varepsilon^2}$$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.