= Success-failure stopping identity
{title2=$P(T_n<U_m)=\sum_{k=0}^{m-1}\binom{n-1+k}{k}p^nq^k$}
In independent <Bernoulli trials> with success <probability> $p$ and failure <probability> $q=1-p$, let $T_n$ be the trial of success $n$ and $U_m$ the trial of failure $m$, for positive integers $n,m$. If success $n$ occurs after $k<m$ failures, its final trial is a success and the preceding trials have $n-1$ successes and $k$ failures. The <negative binomial stopping argument> therefore gives the title sum.
Put $F=n+m$. By trial $F-1$, at least one target must have been reached, so the same <event> is that a <binomial distribution> with $F-1$ trials has at least $n$ successes. Conditioning instead on the final trial of a block of $F$ trials gives
$$
\sum_{k=0}^{m-1}\binom{n-1+k}{k}p^nq^k
=\binom{F-1}{n}p^nq^{F-n}
+\sum_{k=n+1}^{F}\binom Fk p^kq^{F-k}.
$$
Indeed, more than $n$ successes in the full block guarantee the success target won; with exactly $n$ successes it won only when the final trial was a failure. These disjoint cases explain the extra boundary term. A zero success target wins immediately; a zero failure target has already been reached. To include $n=0$ in the displayed finite sum requires the explicit generalized convention $\binom{-1}{0}=1$; an upper summation limit of $-1$ denotes an <empty sum>.
Back to article page
