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 '17 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 '19 at 12:13

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, privacy policy and cookie policy

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