Binomial $p$ estimator

Question

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

Question

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.

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