# Binomial $p$ estimator

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.

• 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? – whuber Jun 9 '17 at 15:08
• 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. – cdalitz May 7 '19 at 12:13

Chebychev's inequality gives a bound for

$$P(p-\gamma< \hat{p}

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