Say we have a coin with a probability of $p$ to get "head" on each toss, and assume that we have a parameter $k\in\mathbb N^+$.
I'm looking for an upper bound on the number of tosses $N$ that would ensure that we see at least $k$ heads with probability $1-\delta$.
I have made an attempt of computing such a bound, but am not sure that it is correct or if it can be simplified.
The Chernoff bound tells us that if we mark the number of heads by $H$ then:
$$\Pr[H\le Np(1-\gamma)]\le e^{-\gamma^2Np/2}$$
This means that to get a probability of at most $\delta$ we would need to set $$ \gamma = \sqrt{\frac{2\ln\delta^{-1}}{Np}}. $$ This means that the requirement that $H\ge k$ implies that we need $$ k = Np(1-\gamma) = Np\left(1-\sqrt{\frac{2\ln\delta^{-1}}{Np}}\right)=Np-\sqrt{{2{Np}\ln\delta^{-1}}}. $$
Denote $x=\sqrt {Np}$, then $$ x^2-x\cdot\sqrt{{2\ln\delta^{-1}}} - k = 0. $$
Then we have $$x=\frac{\sqrt{{2\ln\delta^{-1}}}+\sqrt{2\ln\delta^{-1}+4k}}{2} =\frac{\sqrt{{\ln\delta^{-1}}}+\sqrt{\ln\delta^{-1}+4k}}{\sqrt2}.$$
Therefore: $$ N = x^2/p = \frac{\left(\sqrt{{\ln\delta^{-1}}}+\sqrt{\ln\delta^{-1}+4k}\right)^2}{2p} = \frac{{{\ln\delta^{-1}}}+2(\ln\delta^{-1}+\sqrt{4k\ln\delta^{-1}})+{(\ln\delta^{-1}+4k)}}{2p} = \frac{{{2\ln\delta^{-1}}}+2k+\sqrt{4k\ln\delta^{-1}}}{p}. $$
- Is my analysis correct? Is there a way to simplify the bound?
To me, it seems wrong, as I would expect that $N=k/p+O(1)$ would be enough when $\delta$ is constant. What am I missing?
A foolish arithmetic mistake in one of the steps. The correct bound is $$N=\frac{{{2\ln\delta^{-1}}}+k+\sqrt{2k\ln\delta^{-1}}}{p}$$
Going back to the analysis, we have:
$$x=\frac{\sqrt{{2\ln\delta^{-1}}}+\sqrt{2\ln\delta^{-1}+4k}}{2} =\frac{\sqrt{{\ln\delta^{-1}}}+\sqrt{\ln\delta^{-1}+\color{red}{2}k}}{\sqrt2}.$$
Therefore: $$ N = x^2/p = \frac{\left(\sqrt{{\ln\delta^{-1}}}+\sqrt{\ln\delta^{-1}+2k}\right)^2}{2p} = \frac{{{\ln\delta^{-1}}}+2(\ln\delta^{-1}+\sqrt{2k\ln\delta^{-1}})+{(\ln\delta^{-1}+2k)}}{2p} = \frac{{{2\ln\delta^{-1}}}+k+\sqrt{2k\ln\delta^{-1}}}{p}. $$
I'm still wondering if there is a way to simplify this analysis.