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
    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
    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}$$


This site is temporarily in read-only mode and not accepting new answers.

Not the answer you're looking for? Browse other questions tagged .