So the actual original question I am trying to solve is a little bit different than the title:
In a binomial setting with probability of success $p$, I keep examining observations until a fraction of success $a<f<b$ is reached. What is the probability of stopping after exactly $N$ observations. This is equivalent of asking $P(G_N|\bar{G_0},...,\bar{G_{N-1}})$ where $G_N\equiv a<f_N<b$.

As a first step to solve this, I want to compute $P(G_N)$, i.e. the probability of getting a fraction of success $a<f_N<b$ after $N$ observations. One way I can think of is to use a continuous estimation of the binomial distribution, and then integrate for $a<f_N<b$. But I have this feeling that there should be an easier way. Is there?

Also, I realize that after computing $P(G_N)$, I still have to compute the original conditional probability, which would be complicated. Is there a more clever way to think about the original question?


1 Answer 1


Computing $P(a < f_N < b)$ is the same as computing $CDF_B(bN) - CDF_B(aN)$, where $CDF_B$ is the cumulative distribution function of the binomial distribution with $N$ trials. So really all you need is an efficient way to compute the CDF of the binomial distribution.

If you're looking for a way to compute this numerically, e.g., because you want to plot $P(a < f_N < b)$ exactly for different values of $a$, $b$, and $N$, there probably exists a library for computing distribution CDF's, including the binomial CDF, in whatever programming language you're using. If you're looking for an analytic approximation, you might try something like this, where $CDF_N$ is the CDF of the normal distribution:

$\begin{align}CDF_B(bN) - CDF_B(aN) &\approx CDF_N(bN) - CDF_N(aN) \\ &\approx PDF_N \left( \frac{a+b}{2}N \right) (b-a)N \\ &= \frac{(b-a) \sqrt{N}}{\sqrt{2 \pi p q}} e^{-\frac{1}{2\sqrt{Npq}} ((\frac{a+b}{2} - p) N)^2 }\end{align}$

E.g., the probability that the observed fraction of successes is between 0.49 and 0.51 after flipping a fair coin 100 times is approximately $0.2 / \sqrt{\pi/2} \approx 0.16$.

The first approximation is the standard approximation of a binomial distribution by a normal distribution:

$Binomial(n,p) \approx Normal(np, \sqrt{npq})$

The second approximation is a midpoint approximation: for any differentiable function $f$,

$f(b) - f(a) \approx f'(\frac{a+b}{2}) (b-a)$

In the last line, we substitute the definition of $PDF_N$ and simplify.

All together, this approximation should be accurate so long as $N$, $pN$, and $qN$ are large (so that $CDF_B \approx CDF_N$), and $(b-a)N$ is small (so the midpoint approximation is accurate).

EDIT: $p$ is the probability of success, and $q = 1-p$ is the probability of failure.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.