Sums of Geometric Waiting Times

Why Sums of Waiting Times Have a Negative-Binomial Law

A geometric random variable records how long we wait for one success. If instead we wait for $r$ successes, the total waiting time is a sum of $r$ geometric random variables. The resulting distribution is called the negative-binomial distribution. Its formula is simple, but its support depends on what “waiting time” counts: failures, or all trials including the successful one.

Throughout, let $p$ be the success probability on each trial, with $0<p\leq 1$, and write $q=1-p$. The waiting times considered below are independent and have the same success probability. The case $p=1$ is degenerate; the main derivations take $0<p<1$.

Two Geometric Support Conventions

Both conventions describe the wait for one success in independent Bernoulli trials. They differ only in whether the successful trial is counted.

Definition: Under the failures-before-success convention, a geometric random variable $X$ counts the number of failures before the first success: $$ P(X=k)=q^k p,\qquad k=0,1,2,\ldots. $$ Under the trials-until-success convention, a geometric random variable $T$ counts the total number of trials through the first success: $$ P(T=t)=q^{t-1}p,\qquad t=1,2,3,\ldots. $$ The two variables are related by $T=X+1$.

For $r$ successes, let $X_1,\ldots,X_r$ be independent geometric variables using the failures-before-success convention. Their sum $K=X_1+\cdots+X_r$ counts the total number of failures before the $r$th success. If instead $T_i=X_i+1$ counts trials through success $i$, then $N=T_1+\cdots+T_r=K+r$ counts all trials through the $r$th success.

Worked Example: Translating Between the Two Conventions

Suppose $r=3$ successes are required. If there are $k=2$ failures before the third success, the total number of trials is $n=k+r=5$. The same outcome can be represented as $K=2$ under the failures convention or $N=5$ under the trials convention.

For $p=0.4$, $q=0.6$. The probability of exactly two failures before the third success, as derived below, is $$ \binom{2+3-1}{3-1}(0.4)^3(0.6)^2 = \binom{4}{2}(0.064)(0.36) =6(0.02304) =0.13824. $$

In the trials convention, the same probability is $$ \binom{5-1}{3-1}(0.4)^3(0.6)^{5-3} =\binom{4}{2}(0.064)(0.36) =0.13824. $$ The numerical probabilities agree because the events are the same; only the recorded waiting time differs by $r=3$.

Deriving the Negative-Binomial Distribution

Theorem: Let $X_1,\ldots,X_r$ be independent, each with $P(X_i=k)=q^k p$ for $k=0,1,\ldots$, where $r$ is a positive integer and $0<p<1$. Then $K=\sum_{i=1}^r X_i$ has probability mass function $$ P(K=k)=\binom{k+r-1}{r-1}p^r q^k,\qquad k=0,1,2,\ldots. $$ Equivalently, if $T_i=X_i+1$ counts trials through success and $N=\sum_{i=1}^r T_i$, then $$ P(N=n)=\binom{n-1}{r-1}p^r q^{n-r},\qquad n=r,r+1,\ldots. $$

To derive the first formula, consider any particular nonnegative integer tuple $(x_1,\ldots,x_r)$ whose entries sum to $k$. Independence gives its probability: $$ P(X_1=x_1,\ldots,X_r=x_r) =\prod_{i=1}^r (p q^{x_i}) =p^r q^{x_1+\cdots+x_r} =p^r q^k. $$ Thus every tuple contributing to $P(K=k)$ has the same probability. It remains to count the tuples.

The number of ordered $r$-tuples of nonnegative integers summing to $k$ is $\binom{k+r-1}{r-1}$. One way to see the count is to arrange $k$ identical marks and insert $r-1$ separators. The number of marks before the first separator is $x_1$, the number between the first and second is $x_2$, and so on; a separator at an endpoint or beside another separator allows a component to be zero. There are $k+r-1$ positions for the combined marks and separators, and choosing the $r-1$ separator positions specifies the tuple. Multiplying the number of tuples by their common probability proves the formula.

Since $N=K+r$, the event $N=n$ is exactly the event $K=n-r$. Substituting $k=n-r$ into the first formula gives $$ P(N=n)=\binom{(n-r)+r-1}{r-1}p^r q^{n-r} =\binom{n-1}{r-1}p^r q^{n-r},\qquad n\geq r. $$ This also explains the lower endpoint: at least $r$ trials are needed to obtain $r$ successes. $\square$

The coefficient counts possible allocations of the failures among the $r$ waiting periods. In the trials interpretation, it counts the possible placements of the first $r-1$ successes among the first $n-1$ trials: the $n$th trial must be a success. Either interpretation gives the same coefficient after shifting $n=k+r$.

Worked Example: A Specific Negative-Binomial Probability

A trial succeeds with probability $p=0.3$. Find the probability that the fourth success occurs after exactly three failures in total. Here $r=4$, $k=3$, and $q=0.7$. The number of ways to allocate three failures across four waiting periods is $$ \binom{3+4-1}{4-1}=\binom{6}{3}=20. $$ Each allocation has probability $(0.3)^4(0.7)^3$. Therefore, $$ P(K=3)=20(0.3)^4(0.7)^3 =20(0.0081)(0.343) =0.055566. $$ In total-trials language, this is the probability that the fourth success occurs on trial $n=3+4=7$, and the formula gives $\binom{6}{3}(0.3)^4(0.7)^3$, the same value.

Moments of the Sum

The sum’s expectation and variance also follow from the individual waiting times. For the failures-before-success convention, the probability generating function of one geometric variable is $$ G_X(s)=E[s^X]=\sum_{k=0}^{\infty}p q^k s^k=\frac{p}{1-qs},\qquad |qs|<1. $$ By independence, the probability generating function of $K$ is the product of the individual generating functions: $$ G_K(s)=\left(\frac{p}{1-qs}\right)^r. $$ Because $0<p<1$, this function is differentiable in an open interval containing $s=1$. The power series and its derivatives converge there, so the standard generating-function identities $E[K]=G_K'(1)$ and $E[K(K-1)]=G_K''(1)$ apply. Differentiating gives $$ G_K'(s)=r q p^r(1-qs)^{-r-1},\qquad G_K''(s)=r(r+1)q^2p^r(1-qs)^{-r-2}. $$ Consequently, $$ E[K]=\frac{rq}{p},\qquad E[K(K-1)]=\frac{r(r+1)q^2}{p^2}. $$ Since $\operatorname{Var}(K)=E[K(K-1)]+E[K]-(E[K])^2$, substitution yields $$ \operatorname{Var}(K) =\frac{r(r+1)q^2}{p^2}+\frac{rq}{p}-\frac{r^2q^2}{p^2} =\frac{rq^2}{p^2}+\frac{rq}{p} =\frac{rq}{p^2}. $$

The total-trials sum $N=K+r$ differs from $K$ by a constant, so it has the same variance and an expectation larger by $r$. Thus $$ E[N]=r+\frac{rq}{p}=\frac{r}{p},\qquad \operatorname{Var}(N)=\frac{rq}{p^2}. $$ For $p=1$, each waiting time is one trial under the trials convention and zero failures under the failures convention; the corresponding sums are $N=r$ and $K=0$ with probability one.

Worked Example: Mean and Variance for Four Successes

Let $r=4$ and $p=0.2$, so $q=0.8$. The number of failures before the fourth success has $$ E[K]=\frac{4(0.8)}{0.2}=16,\qquad \operatorname{Var}(K)=\frac{4(0.8)}{(0.2)^2} =\frac{3.2}{0.04}=80. $$ The total number of trials is $N=K+4$, so $$ E[N]=16+4=20,\qquad \operatorname{Var}(N)=80. $$ The mean of 20 trials also agrees with the fact that each of four successes requires an average of $1/p=5$ trials.

Using the Formula Carefully

The negative-binomial formula is useful when a process continues until a fixed number of successes has occurred. It gives the probability of a specified completion time and, through its cumulative probabilities, the chance of finishing by a given time. It also makes clear how success probability affects waiting: a smaller $p$ increases both the expected number of trials and the variability.

A common mistake is to use the right binomial coefficient with the wrong exponent or support. Under the failures convention, $k$ begins at zero and the probability contains $q^k$. Under the trials convention, $n$ begins at $r$, and the number of failures is $n-r$, so the probability contains $q^{n-r}$. In both cases the exponent of $p$ is $r$, because exactly $r$ successes are required.

Worked Example: Probability of Finishing Within a Given Number of Failures

Suppose $r=2$ successes are required and $p=0.4$, so $q=0.6$. Find the probability of at most two failures before the second success. Sum the probabilities for $k=0,1,2$: $$ \begin{aligned} P(K\leq 2) &=P(K=0)+P(K=1)+P(K=2)\\ &=\binom{1}{1}(0.4)^2 +\binom{2}{1}(0.4)^2(0.6) +\binom{3}{1}(0.4)^2(0.6)^2\\ &=0.16+2(0.16)(0.6)+3(0.16)(0.36)\\ &=0.16+0.192+0.1728\\ &=0.5248. \end{aligned} $$ The same event means finishing within $r+2=4$ total trials. In that convention, sum $P(N=n)$ for $n=2,3,4$; these correspond respectively to $k=0,1,2$, giving the same probability $0.5248$.

Key takeaway: For $r$ independent geometric waiting times with common success probability $p$, the sum has a negative-binomial distribution. Count failures with support $0,1,\ldots$, or count total trials with support $r,r+1,\ldots$; converting between them requires the shift $N=K+r$.

Check Your Understanding

Check that you can identify the support and interpret each parameter before substituting into a formula.

If $r=3$ successes are required and there are $k=5$ failures before the final success, how many total trials have occurred?
Write the probability mass function for the number of trials needed to obtain $r$ successes when each trial succeeds with probability $p$.
For $r=2$ and $p=0.5$, calculate the probability of exactly one failure before the second success.
State the mean and variance of the total number of trials required for $r$ successes.
Explain why the negative-binomial coefficient counts allocations of failures across waiting periods.