Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

In Bernoulli trials with parameter $p$, let $N_n$ be the number of trials required to produce either $n$ successes or $n$ failures, whichever comes first. I would like to computer the probability distribution of $N_n$.

My solution is:

Suppose $S_n$ is the number of trials required to produce $n$ successes. Then $$ P(S_n=k) = {{k-1}\choose{n-1}} (1-p)^{k-n}p^n.$$

Suppose $F_n$ is the number of trials required to produce $n$ failures. Then $$ P(F_n=k) = {{k-1}\choose{n-1}} p^{k-n}(1-p)^n.$$

$N_n = \min\{S_n, F_n\}.$ But I doubt it is correct and even if it is correct, I am not sure how to proceed. Can I get some insights? Thanks!

share|cite|improve this question
up vote 4 down vote accepted

Hint: $N_n$ can take on values from $n$ to $2n-1$. For any fixed $k$ in the range from $n$ to $2n-1$, the event $\{N_n = k\}$ occurs if the $k$-th trial is a success and the previous $k-1$ trials had $n-1$ successes and $k-n \leq n-1$ failures, OR, the $k$-th trial is a failure and the previous $k-1$ trials had $n-1$ failures and $k-n \leq n-1$ successes. Can you find the probability for each of the two cases? You will likely have a $\binom{k-1}{n-1}$ in there somewhere....

share|cite|improve this answer
(+1) This is the right approach and gives the right intuition. – cardinal Sep 12 '11 at 18:51

Negative binomial distribution ($NeBi(n,p)$) is the distribution of number of failures in sequence of trials until $n$ successes occur. The expression you seek is

$$ \mathbb{P}(N_n = k) = \frac{\mathbb{P}( \left. S = k-n \right| S < n) \mathbb{P}(S < n) + \mathbb{P}( \left. F = k-n \right| F < n)\mathbb{P}(F < n)}{ \mathbb{P}(S < n) + \mathbb{P}(F < n) } $$ where $S$ follows $NeBi(n, p)$ and $F$ follows $NeBi(n, 1-p)$. This gives

$$ \begin{eqnarray} \mathbb{P}(N_n = k) &=& \left( p^n (1-p)^{k-n} \binom{k-1}{n-1} +(1-p)^n p^{k-n} \binom{k-1}{n-1} \right) \frac{B(n,n) \chi_{n \le k < 2 n} }{B_p(n,n) + B_{1-p}(n,n) } \end{eqnarray} $$ where $B_p(a,b)$ is incomplete Beta function.

Added: I finally realized that, since $B_{p}(n,n) = \int_0^p (t (1-t))^{n-1} \mathrm{d} t$, $B_p(n,n) + B_{1-p}(n,n) = \int_0^1 (t (1-t))^{n-1} \mathrm{d} t = B(n,n)$, so that the normalization factor actually equals to $1$.

share|cite|improve this answer
I don't know why those incomplete beta functions are there. And, note that $n \leq k < 2n$ with probability 1, so the characteristic functions aren't needed either. :) – cardinal Sep 12 '11 at 18:53
My mistake has been to include the case of $S=F=n$ which is clearly impossible, I updated the formula. The incomplete beta functions are there to ensure that $\sum_{k=n}^{2n-1} \mathbb{P}(N_n =k) = 1$ – Sasha Sep 12 '11 at 19:05
The incomplete beta functions are not needed. – cardinal Sep 12 '11 at 19:07

Not sure I understood this correctly, but:

A trial ends either in success or failure. Assuming it was a success after $k$ trials, we know we had $n$ successes and $k-n$ failures, so the probability of this happening would rather be

$$ P(S_n=k) = {{k}\choose{n}} (1-p)^{k-n}p^n.$$

Furthermore, note that the successes and failures scenarios are mutually exclusive. There is no way you can reorder the trials and change the issue for a given $S_n$ or $F_n$.

So, shouldn't you rather have

$$ P(N_n=k) = P(S_n=k) + P(F_n=k) $$

given that $S_n=k$ and $F_n=k$ refer to opposite, mutually exclusive scenarii ?

Finally, observe that for $k=2n-1$, there is automatic (still mutually exclusive) success or failure, so you can completely characterize the distribution for $k \in [n,2n-1]$

share|cite|improve this answer
@bofh I first attempted to go this route, but it is easy to verify that $\sum_{k=n}^{2n-1} P(N_n =k) \not 1$. For instance for $n=3$ and $p=1/2$, I get $\sum _{k=n}^{2 n-1} \binom{k}{n} \left((1-p)^n p^{n-k}+p^n (1-p)^{k-n}\right)=\frac{109}{16}$. – Sasha Sep 12 '11 at 19:24
@Sasha: Try with ${k-1 \choose n-1}$ instead of ${k \choose n}$. It is trivially true that $\sum_{k=n}^{2n - 1} \mathbb P(N_n = k) = 1$. (Why?) :) – cardinal Sep 12 '11 at 19:42
@cardinal I realized that in my approach the normalization factor is also a hidden unity, and added a note to that effect. Thanks for catching that! – Sasha Sep 12 '11 at 20:09
Yep, I lacked coffe and completely missed the point indeed. Sorry for the noise :) – b0fh Sep 21 '11 at 13:42

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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