# Run of $N$ successes before run of $k$ failures

What is the probability that a run of $N$ consecutive successes will occur before a run of $k$ consecutive failures when each trial has a probability $p$ of success and $q=1-p$ of failure?

-
sorry, I misread the question... I thought you want to know the probability to have $N$ successes followed by $k$ failures (in what seems to be $N+k$ trials). – Fabian Apr 25 '11 at 18:46

The second item under a Google search for the phrase "Run of $N$ successes before run of $k$ failures" (the first is this question!) gives a Google books link to page 71 of A First Course in Probability by Tapas K. Chandra, Dipak Chatterjee.
After a detailed explanation, the solution given there is $${p^{N-1}(1-q^k)\over p^{N-1}+q^{k-1}-p^{N-1}q^{k-1}}.$$
I'm assuming that you count "a run of N consecutive successes" as soon as N consecutive successes have occurred, without waiting to see if the next trial will be a success (i.e. whether this will be a run of exactly N, or more than N, consecutive successes). Let $u_n$ be the probability that a run of N consecutive successes occurs before a run of k consecutive failures, given that you start with $n$ consecutive successes (if $n \ge 0$) or $-n$ consecutive failures (if $n < 0$). Thus you want $u_0$. The boundary conditions are $u_N = 1$ and $u_{-k} = 0$, and first-step analysis tells you if $n \ge 0$, $u_n = p u_{n+1} + q u_{-1}$, while if $n \le 0$, $u_n = p u_1 + q u_{n-1}$. From the first recurrence we get $u_n - u_{-1} = p (u_{n+1} - u_{-1})$ for $n \ge 0$, so $u_0 - u_{-1} = p^N (u_N - u_{-1}) = p^N (1 - u_{-1})$ and $u_1 - u_{-1} = p^{N-1} (1 - u_{-1})$. From the second, $u_n - u_1 = q (u_{n-1} - u_1)$ for $n \le 0$, so $u_0 - u_1 = q^k (u_k - u_1) = - q^k u_1$ and $u_{-1} - u_1 = - q^{k-1} u_1$. Putting these together, I get $u_{0} = \frac{p^N q (1 - q^k)}{p q^k + p^N q - p^N q^k}$.