If we note $k$ the number of successes among $n$ i.i.d. Bernoulli trials, the probability distribution for $k$ is binomial.
The number of successes $k^*$ with highest probability is roughly equal to $k^* = np$, and I'm trying to establish a "credibility" interval that the observed number of successes will be near $k^*$.
More precisely, I'm trying to estimate the relationship between the interval radius $r$ and the probability threshold $t$ in the following expression : $$\mathbb{P}\big( k \in [np-r\,;\,np+r]\big) \,\,>\,\, t$$
Using the formula for a binomial distribution, this is : $$ \sum_{ np - r \,\leq\, k}^{k \,\leq\, np + r} {n \choose k} \,p^k \,(1-p)^{n-k} \,\,>\,\, t $$
What bounds can I use ?
Some numerical tests. I have used a simple algorithm that computes the sum for $r = 0, 2, 4, 6, etc.$ to get a numerical approximation. We can see that the interval length grows roughly at the speed of $\sqrt{n}$.
On the picture below, the $x$-axis is the number of trials $n$, the blue dots are the computed length $2*r$ and the black line is a regression line $\alpha\,\sqrt{n}$. Each graph shows the regression for different values of $p$ using a constant threshold $t = 0.9$.
For small $p$ the following apply https://en.wikipedia.org/wiki/Poisson_limit_theorem