Negative binomial stopping argument

For the negative binomial distribution with positive integer target $r$ and success probability $0<p<1$, the $r$th success occurs after exactly $x$ failures only if the final trial is a success, while the preceding $x+r-1$ trials contain $x$ failures and $r-1$ successes. Choosing the failure locations gives the binomial coefficient $\left(\genfrac{}{}{0ex}{}{x+r-1}{x}\right)$. Each such stopped sequence has probability $(1-p{)}^x{p}^r$ by independence, and the sequences describe mutually exclusive events, so their probabilities add. This proves the probability mass function. Counting arrangements among all $x+r$ positions would wrongly include sequences that already reached the target earlier. The same argument is used for three heads in MIT 18.05, spring 2022, problem set 9 solutions, problem 2(b).

A short route to normalization and moments is to split the failures count into successive waiting blocks:where $F_i$ counts failures after success $i-1$ and before success $i$, with $F_1$ starting at the first trial. Fresh independent Bernoulli trials make the blocks independent, each with the failures-count geometric distribution. Each block has total mass $p{\sum }_{j=0}^{\infty }(1-p{)}^j=1$ by the geometric series, so their sum also defines a normalized probability distribution. The linearity of expectation and variance additivity for independent random variables give $\mathbb{E}X=r(1-p)/p$ and $\mathrm{Var}(X)=r(1-p)/p^2$. This makes the moments transparent without a long calculation of sums. For $p=1$, every block is zero.

The same stopping rule connects a waiting count to a fixed-length count. Let $N=X+r$ be the trial number of the $r$th success, and let $B_n$ count successes in the first $n$ trials, so $B_n$ has a binomial distribution. For any nonnegative integer $n$,The target is still unmet after $n$ trials exactly when fewer than $r$ successes have occurred. With $r=2$, $p=1/2$ and $n=4$, this gives $\mathbb{P}(N>4)=(1+4)/16=5/16$; equivalently, $\mathbb{P}(X\le 2)=1-5/16=11/16$, matching $1/4+1/4+3/16$. At $p=1$, the event identity still holds, with $N=r$ and $B_n=n$ deterministically.

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 givesIndeed, 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 $\left(\genfrac{}{}{0ex}{}{-1}{0}\right)=1$; an upper summation limit of $-1$ denotes an empty sum.

Suppose independent Bernoulli trials give a player a win with probability $p$, and the match ends when either player reaches $r$ wins. The player's match-win probability isFor a win with $n$ losses, the final trial must be a win. The preceding $r+n-1$ trials contain exactly $r-1$ wins and $n$ losses; the binomial coefficient counts their arrangements. Because $n<r$, the opponent cannot already have won, and because the player has only $r-1$ previous wins, the match has not ended earlier. Summing the disjoint terminal events gives the formula, a truncated negative binomial distribution sum. The constant game-win probability must describe independent games, or equivalently remain the same conditional on every previous history.