Let $X \sim \operatorname{Bin}(n,p)$. Suppose we estimate $p$ by $\hat{p}=\frac{X}{n}$. By Hoeffding’s inequality
it holds for all $\delta \in (0,1)$ with probability at least $1-\delta$ that, $$\lvert\hat{p}-p\rvert\le \sqrt{\frac{\log\frac{2}{\delta}}{2n}}.
$$
I am interested in a matching non-asymptotic high probability lower bound.
The expected value $\mathbb{E}[\lvert\hat{p}-p\rvert]$ is lower bounded by $\sqrt{\frac{p(1-p)}{2n}}$ (see reference [1]). I am interested in a high-probability lower bound of the form
$$
\lvert\hat{p}-p\rvert\ge c\sqrt{\frac{\log\frac{1}{\delta}}{n}}
$$ preferably with an explicit constant $c$. Does anyone know of a reference?


**Reference**


[1] Daniel Berend and Aryeh Kontorovich, "[A sharp estimate of the binomial mean absolute deviation
with applications](https://doi.org/10.1016/j.spl.2013.01.023)"
Statistics & Probability Letters, Volume 83, Issue 4, April 2013, Pages 1254–1259, [MR3041401](https://mathscinet.ams.org/mathscinet-getitem?mr=MR3041401), [Zbl 1268.60021](https://zbmath.org/?q=an%3A1268.60021).



Lower bound on the error of proportion estimation
$\newcommand{\de}{\delta}$You want a huge deal more than what there is in reality.


Indeed, you want
\begin{equation\*}
 p\_n:=P\Big(|\hat p-p|\ge c\sqrt{\frac{\ln(1/\de)}n}\,\Big)\ge1-\de \tag{1}\label{1}
\end{equation\*}
for some $c\in(0,\infty)$, all large enough $n$, and all small enough $\de>0$.


By the central limit theorem,
\begin{equation\*}
 Z\_n:=\frac{\hat p-p}{\sqrt{pq/n}}\to Z
\end{equation\*}
(as $n\to\infty$), where $q:=1-p$ and $Z\sim N(0,1)$. So, \eqref{1} would imply
\begin{equation\*}
 1-\de\le p\_n=P\Big(|Z\_n|\ge c\sqrt{\frac{\ln(1/\de)}{pq}}\,\Big)
 \underset{n\to\infty}\longrightarrow
 P\Big(|Z|\ge c\sqrt{\frac{\ln(1/\de)}{pq}}\,\Big)
 \underset{\de\downarrow0}\longrightarrow0,
\end{equation\*}
which in turn would imply $1\le0$.




---


On the positive side, by Shevtsova's version of the [Berry–Esseen inequality](https://en.wikipedia.org/wiki/Berry%E2%80%93Esseen_theorem#Identically_distributed_summands), for any real $t$
\begin{equation}
\begin{aligned}
 P(|\hat p-p|\le t)&=P\Big(|Z\_n|\le t\sqrt{\frac n{pq}}\Big) \\ 
 &\le P\Big(|Z|\le t\sqrt{\frac n{pq}}\Big) 
 +\frac{1/2}{\sqrt n}\,\frac{p^3 q+q^3 p}{(pq)^{3/2}} \\ 
 &\le at\sqrt{\frac n{pq}}+\frac{1}{2\sqrt{npq}}, 
\end{aligned}
\end{equation}
where $a:=\sqrt{2/\pi}$.
So, for $n\ge1/(\de^2 pq)$ we have $\frac{1}{2\sqrt{npq}}\le\frac\de2$ and hence
\begin{equation}
\begin{aligned}
 P\Big(|\hat p-p|\le\frac\de{2a}\,\sqrt{\frac{pq}n}\Big)&\le\de, 
\end{aligned}
\end{equation}
that is,
\begin{equation}
\begin{aligned}
 P\Big(|\hat p-p|>\frac\de{2a}\,\sqrt{\frac{pq}n}\Big)&\ge1-\de. 
\end{aligned}
\end{equation}


