# A Bernoulli trial problem

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!

-

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....

-
(+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$.

-
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]$

-
@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