Adding Independent Negative-Binomial Counts

Why These Counts Add

A negative-binomial variable can record the number of failures observed before a specified number of successes. When separate processes require different numbers of successes, their failure counts may be added. If all the trials have the same success probability, the separate stopped sequences can be joined into one sequence: it has the combined number of required successes, and its total number of failures is the sum of the separate counts.

The shared success probability matters. It gives every trial in the joined sequence the same Bernoulli distribution. Independence matters too: it ensures that the probability of a joined sequence is the product of the probabilities of its component sequences.

Definition: Let $0<p<1$ and let $r$ be a positive integer. A negative-binomial variable $X$ with parameters $r$ and $p$, written here as a failures-before-$r$th-success count, is the number of failures before the $r$th success in independent Bernoulli trials with success probability $p$. Its support is $\{0,1,2,\ldots\}$, and its probability mass function is $$ P(X=x)=\binom{x+r-1}{r-1}p^r(1-p)^x,\qquad x=0,1,2,\ldots. $$

The binomial coefficient counts the ways to place the $x$ failures among the $r$ groups of failures that may occur before successive successes. The final trial must be a success, so the $r-1$ dividers between those groups are placed among the first $x+r-1$ positions. Write $q=1-p$ when it is convenient to shorten formulas.

The Sum Law from Trial Sequences

Let $X_1,\ldots,X_m$ be independent negative-binomial counts. Suppose $X_i$ counts failures before $r_i$ successes, and all the Bernoulli trials have the same success probability $p$. Set $R=r_1+\cdots+r_m$ and $S=X_1+\cdots+X_m$.

Theorem: If $X_1,\ldots,X_m$ are independent failures-before-$r_i$th-success counts with common success probability $p$, where each $r_i$ is a positive integer and $0<p<1$, then $S=X_1+\cdots+X_m$ is a failures-before-$R$th-success count, where $R=\sum_{i=1}^m r_i$. In particular, $$ P(S=k)=\binom{k+R-1}{R-1}p^R(1-p)^k,\qquad k=0,1,2,\ldots. $$

To see the mechanism, generate each count from its own independent Bernoulli sequence and stop sequence $i$ at its $r_i$th success. Join the resulting finite sequences in order. Every component ends in a success. The joined sequence therefore ends at its $R$th success, and the number of failures in it is exactly $S$.

This joining also gives a one-to-one correspondence between component outcomes and finite binary sequences with $R$ successes that end in a success. To recover the components from a joined sequence, split it just after its $r_1$th success, then after its next $r_2$ successes, and continue in this way. Thus no possible joined sequence is omitted or counted more than once.

Specify the component blocks.
Block $i$ ends at its $r_i$th success and contains $X_i$ failures. Its probability is $p^{r_i}q^{X_i}$.

Join the blocks.
The joined sequence has $R=\sum_i r_i$ successes and $S=\sum_i X_i$ failures, and ends at its $R$th success.

Count sequences with $k$ failures.
There are $\binom{k+R-1}{R-1}$ ways to arrange $k$ failures and $R$ successes with the last trial a success.

For any particular joined sequence with $k$ failures, independence gives its probability as the product of its component probabilities:

\prod_{i=1}^m p^{r_i}q^{X_i} =p^{\sum_i r_i}q^{\sum_i X_i} =p^R q^k.

There are $\binom{k+R-1}{R-1}$ such sequences. Adding their equal probabilities gives

P(S=k)=\binom{k+R-1}{R-1}p^R q^k.

Substituting $q=1-p$ proves the stated mass function. The argument works because the component sequences are independent and share the same $p$. $\square$

How the Convolution Counts the Same Sequences

The trial-sequence argument has an equivalent expression as a convolution. For specified nonnegative integers $x_1,\ldots,x_m$ summing to $k$, independence gives

P(X_1=x_1,\ldots,X_m=x_m) =\prod_{i=1}^m \binom{x_i+r_i-1}{r_i-1}p^{r_i}q^{x_i} =p^R q^k\prod_{i=1}^m\binom{x_i+r_i-1}{r_i-1}.

Summing over all such allocations of the $k$ failures yields a combinatorial identity:

Identity: For positive integers $r_1,\ldots,r_m$, $R=\sum_i r_i$, and any nonnegative integer $k$, $$ \sum_{\substack{x_1+\cdots+x_m=k\\x_i\geq 0}} \prod_{i=1}^m\binom{x_i+r_i-1}{r_i-1} =\binom{k+R-1}{R-1}. $$

To verify the identity, imagine $R$ ordered success gaps: the first gap is before the first success, the second is between the first and second successes, and so on. Divide these gaps into $m$ consecutive groups of lengths $r_1,\ldots,r_m$. If group $i$ receives $x_i$ failures in total, the number of ways to distribute them among its $r_i$ gaps is $\binom{x_i+r_i-1}{r_i-1}$, by the stars-and-bars count. For a fixed allocation $(x_1,\ldots,x_m)$, multiplying these counts gives the number of distributions across all groups. Summing over the allocations counts every distribution of $k$ failures among all $R$ gaps exactly once. There are $\binom{k+R-1}{R-1}$ such distributions. This proves the identity and, on substituting it into the convolution, proves the sum law again. $\square$

Worked Probabilities

Worked Example: Adding Two Success Requirements

Let $X_1$ count failures before one success and $X_2$ count failures before two successes. Suppose the counts are independent and each trial has success probability $p=1/2$. Find $P(X_1+X_2=0)$, $P(X_1+X_2=1)$, and $P(X_1+X_2=2)$.

The total success requirement is $R=1+2=3$. The sum $S=X_1+X_2$ has the failures-before-three-successes distribution. Since $q=1-p=1/2$, the formula gives

P(S=k)=\binom{k+2}{2}\left(\frac12\right)^3\left(\frac12\right)^k.

For zero failures,

P(S=0)=\binom{2}{2}\left(\frac12\right)^3=\frac18.

For one failure,

P(S=1)=\binom{3}{2}\left(\frac12\right)^4=\frac{3}{16}.

For two failures,

P(S=2)=\binom{4}{2}\left(\frac12\right)^5=\frac{6}{32}=\frac{3}{16}.

The values are probabilities of distinct outcomes of $S$; their sum is $1/8+3/16+3/16=1/2$, which is the probability that $S\leq 2$, not the total probability over its unbounded support.

Worked Example: Checking a Convolution at Two Failures

Let $X_1$ count failures before two successes and $X_2$ failures before three successes. They are independent, with common success probability $p=0.4$, so $q=0.6$. Calculate $P(X_1+X_2=2)$ directly by convolution and compare it with the sum law.

The possible allocations of two failures are $(0,2)$, $(1,1)$, and $(2,0)$. For $X_1$, the relevant probabilities are

P(X_1=0)=0.4^2=0.16,\quad P(X_1=1)=\binom{2}{1}(0.4)^2(0.6)=0.192,\quad P(X_1=2)=\binom{3}{1}(0.4)^2(0.6)^2=0.1728.

For $X_2$, they are

P(X_2=0)=0.4^3=0.064,\quad P(X_2=1)=\binom{3}{2}(0.4)^3(0.6)=0.1152,\quad P(X_2=2)=\binom{4}{2}(0.4)^3(0.6)^2=0.13824.

By independence, the three convolution contributions are

\begin{aligned} P(X_1+X_2=2) &=P(X_1=0)P(X_2=2)+P(X_1=1)P(X_2=1)+P(X_1=2)P(X_2=0)\\ &=(0.16)(0.13824)+(0.192)(0.1152)+(0.1728)(0.064)\\ &=0.0221184+0.0221184+0.0110592\\ &=0.055296. \end{aligned}

The direct formula has $R=5$, so it gives

P(X_1+X_2=2)=\binom{6}{4}(0.4)^5(0.6)^2 =15(0.01024)(0.36)=0.055296.

Both calculations agree. The separate terms matter: their sum is correct only when each allocation of failures is paired with the corresponding component probabilities.

Worked Example: A Small Lower-Tail Probability

Let $X_1$ and $X_2$ be independent failures-before-success counts with common success probability $p=0.25$. Find the probability that their total is at most one failure.

Each count requires one success, so $S=X_1+X_2$ is a failures-before-two-successes count. With $q=0.75$, the two relevant probabilities are

P(S=0)=\binom{1}{1}(0.25)^2=0.0625, \qquad P(S=1)=\binom{2}{1}(0.25)^2(0.75)=0.09375.

Therefore the lower-tail probability is

P(S\leq 1)=P(S=0)+P(S=1)=0.0625+0.09375=0.15625.

The event is a lower tail because it includes values at or below one. An upper-tail event would instead use values at or above a specified threshold.

When the Sum Law Does Not Apply

The common-$p$ condition is not a technical detail that can be dropped. For example, let $X_1$ and $X_2$ each count failures before one success, independently, but let their success probabilities be $0.5$ and $0.8$, respectively. Then

$$ P(X_1+X_2=0)=(0.5)(0.8)=0.4, $$

while

$$ P(X_1+X_2=1) =(0.5)(0.8)(0.2)+(0.5)(0.5)(0.8) =0.08+0.20=0.28. $$

If the sum were failures-before-two-successes for some success probability $p^\ast$, its zero-failure probability would be $(p^\ast)^2=0.4$, requiring $p^\ast=\sqrt{0.4}$. Its ratio of one-failure to zero-failure probabilities would then be $2(1-p^\ast)$, about $0.735$. The actual ratio is $0.28/0.4=0.7$, so no such $p^\ast$ gives this sum distribution. Independent counts with different success probabilities do not, in general, add to a negative-binomial count.

A related parameterization pitfall is to confuse failures with total trials. The theorem concerns failures-before-$r$th-success variables. If a variable instead records the trial number on which the $r$th success occurs, it equals the failure count plus $r$. Adding such trial counts adds both the failures and the success requirements; it is not the same numerical sum as adding failures alone.

Key takeaway: For independent failures-before-$r_i$th-success counts with a common success probability $p$, the sum is a failures-before-$\sum_i r_i$th-success count with that same $p$. The trial-sequence argument explains why: joining the stopped sequences adds both their failures and their required successes.

Check Your Understanding

Use the failures-before-$r$th-success convention in each question.

If independent counts require $2$, $4$, and $1$ successes, respectively, and share the same success probability, what success requirement does their sum have?
For two independent counts with $r_1=1$, $r_2=2$, and common success probability $p$, write $P(X_1+X_2=3)$.
In the joined-sequence argument, how can the component sequences be recovered from their concatenation?
Why does a common success probability allow the probability of a joined sequence with $R$ successes and $k$ failures to be written as $p^R(1-p)^k$?
Does independence alone guarantee that the sum of two negative-binomial counts with different success probabilities is negative-binomial? Explain briefly.