Negative-Binomial Tails as Binomial Probabilities

Why a Waiting-Time Tail Is a Binomial Tail

A negative-binomial variable can describe how long a sequence of independent trials takes to produce a fixed number of successes. Its probabilities can be calculated directly from its probability mass function, but a cumulative probability may require adding many terms. There is another route: instead of asking when the required success occurred, count how many successes have occurred by a chosen trial. That count has a binomial distribution.

This connection is useful both for calculation and for interpretation. The event that the $r$th success has occurred by trial $n$ is exactly the event that the first $n$ trials contain at least $r$ successes. The direction matters: a waiting-time probability of the form “by trial $n$” becomes an upper tail for the binomial count.

Definitions and the Tail Identity

Definition: Let $r$ be a positive integer and let $0<p<1$. Consider an infinite sequence of independent Bernoulli trials, each with success probability $p$. Let $T_r$ be the trial number on which the $r$th success occurs. For each nonnegative integer $n$, let $B_n$ be the number of successes in the first $n$ trials, with $B_0=0$. Thus $B_n\sim\operatorname{Binomial}(n,p)$. The variable $T_r$ has the negative-binomial waiting-time distribution for the $r$th success, and $T_r\ge r$.

Theorem: For every nonnegative integer $n$, $$ P(T_r\le n)=P(B_n\ge r) =\sum_{k=r}^{n}\binom{n}{k}p^k(1-p)^{n-k}. $$ The sum is defined to be $0$ when $n<r$, since then $B_n$ cannot reach $r$.

The equation equates two descriptions of the same event, not merely two sums that happen to have the same value. By the end of trial $n$, the $r$th success has occurred if and only if at least $r$ of the first $n$ trials were successes.

Worked Example: The Third Success by Trial Five

Suppose each trial succeeds with probability $p=0.4$, independently, and let $T_3$ be the trial of the third success. Find $P(T_3\le5)$ using the binomial tail, then check it using waiting-time probabilities.

Let $B_5$ count successes in the first five trials. The identity gives $$ P(T_3\le5)=P(B_5\ge3) =\sum_{k=3}^{5}\binom{5}{k}(0.4)^k(0.6)^{5-k}. $$

The three terms are $$ \begin{aligned} P(B_5=3)&=\binom{5}{3}(0.4)^3(0.6)^2=10(0.064)(0.36)=0.2304,\\ P(B_5=4)&=\binom{5}{4}(0.4)^4(0.6)=5(0.0256)(0.6)=0.0768,\\ P(B_5=5)&=\binom{5}{5}(0.4)^5=0.01024. \end{aligned} $$ Therefore $P(T_3\le5)=0.2304+0.0768+0.01024=0.31744$.

For a check, the waiting-time mass at $t\ge r$ is $$ P(T_r=t)=\binom{t-1}{r-1}p^r(1-p)^{t-r}. $$ For $r=3$, the values at $t=3,4,5$ are $0.064$, $3(0.064)(0.6)=0.1152$, and $6(0.064)(0.36)=0.13824$. Their sum is $0.31744$, agreeing with the binomial-tail calculation.

Proof and Consequences for Intervals

To prove the theorem, use the same sequence of trials to define both $T_r$ and $B_n$. If $T_r\le n$, the $r$th success has appeared among trials $1,\ldots,n$, so at least $r$ of these trials were successes: $B_n\ge r$. Conversely, if $B_n\ge r$, then the first $n$ trials contain an $r$th success, and its trial number is no greater than $n$. Thus the two events are identical.

\{T_r\le n\}=\{B_n\ge r\}.

Taking probabilities gives $P(T_r\le n)=P(B_n\ge r)$. Since $B_n$ is binomial, its probability of taking value $k$ is $\binom{n}{k}p^k(1-p)^{n-k}$ for $k=0,\ldots,n$. Summing those masses for $k\ge r$ proves the stated formula. If $n<r$, the event $B_n\ge r$ is impossible, so the probability is zero. $\square$

For an interval of possible success trials, subtract cumulative probabilities. Define $F(n)=P(T_r\le n)$ for every integer $n$, setting $F(n)=0$ when $n<0$. For $n\ge0$, use the binomial-tail identity above. For any integers $a\le b$,

P(a\le T_r\le b)=F(b)-F(a-1).

This form is valid at the boundaries as well as in the interior. In particular, the interval probability is zero if $b<r$, and the formula does not require defining a binomial count at a negative trial number. When $1\le a\le b$, both binomial counts in the difference are defined, and the identity can be written

P(a\le T_r\le b) =P(B_b\ge r)-P(B_{a-1}\ge r).

An upper waiting-time tail follows by taking a complement. For nonnegative $n$,

P(T_r>n)=1-P(T_r\le n)=P(B_n\le r-1).

The event on the right says that fewer than $r$ successes have appeared by trial $n$. This is a lower binomial tail, in contrast to the upper binomial tail for $P(T_r\le n)$.

Worked Example: A Success-Time Interval

Let $T_3$ be the trial of the third success in independent trials with $p=0.5$. Find $P(4\le T_3\le6)$.

Here $1\le4\le6$, so the interval identity uses the defined counts $B_6$ and $B_3$: $$ P(4\le T_3\le6)=P(B_6\ge3)-P(B_3\ge3). $$

For $B_6$, the complement of $B_6\ge3$ consists of zero, one, or two successes. Since $B_6\sim\operatorname{Binomial}(6,0.5)$, $$ P(B_6\ge3)=1-\frac{\binom60+\binom61+\binom62}{2^6} =1-\frac{1+6+15}{64}=\frac{42}{64}. $$ For $B_3$, at least three successes means all three trials succeed, so $P(B_3\ge3)=1/8=8/64$. Consequently, $$ P(4\le T_3\le6)=\frac{42}{64}-\frac{8}{64} =\frac{34}{64}=0.53125. $$

As a direct check, $P(T_3=4)=\binom32/2^4=12/64$, $P(T_3=5)=\binom42/2^5=12/64$, and $P(T_3=6)=\binom52/2^6=10/64$. These add to $34/64$.

Worked Example: Fewer Than Four Successes by Trial Seven

Suppose each trial succeeds with probability $p=0.3$, and $T_4$ is the trial of the fourth success. Find $P(T_4>7)$.

The fourth success has not occurred by trial seven exactly when there are at most three successes in the first seven trials. Thus $$ P(T_4>7)=P(B_7\le3) =\sum_{k=0}^{3}\binom{7}{k}(0.3)^k(0.7)^{7-k}. $$

Evaluating each term gives $$ \begin{aligned} P(B_7=0)&=(0.7)^7=0.0823543,\\ P(B_7=1)&=7(0.3)(0.7)^6=0.2470629,\\ P(B_7=2)&=21(0.3)^2(0.7)^5=0.3176523,\\ P(B_7=3)&=35(0.3)^3(0.7)^4=0.2268945. \end{aligned} $$ The sum is $0.0823543+0.2470629+0.3176523+0.2268945=0.873964$. This is a large probability, consistent with an expected waiting time of $4/0.3$, which exceeds seven trials.

Boundary Cases and a Common Pitfall

The binomial-tail identity is a practical way to choose which finite sum to evaluate. For $P(T_r\le n)$, sum binomial probabilities from $r$ through $n$, or take one minus the sum from zero through $r-1$. For $P(T_r>n)$, sum from zero through $r-1$. If the requested interval begins at trial $1$ or later, use the difference of two binomial tails. If an interval reaches zero or negative integers, use $F(n)$ with its zero definition for $n<0$, rather than trying to construct a binomial count from a negative number of trials.

Common mistake: reversing the tail. Writing $P(T_r\le n)=P(B_n\le r)$ counts too few successes, the opposite of the event needed. The correction is $P(T_r\le n)=P(B_n\ge r)$.
Common mistake: using an undefined count. Substituting $a=0$ into $P(B_b\ge r)-P(B_{a-1}\ge r)$ would call for $B_{-1}$, which is not defined. Use $F(b)-F(a-1)$ with $F(n)=0$ for negative integers, or restrict the binomial-difference version to $1\le a\le b$.
Common mistake: mixing parameterizations. Here $T_r$ counts trials through and including the $r$th success, so its support begins at $r$. A variable counting failures before that success is $T_r-r$, not $T_r$.

The identity matters because a waiting-time question can often be answered with familiar binomial probabilities, including established ways of computing binomial tails. It also makes the event logic transparent: “success achieved by time $n$” means “enough successes in the first $n$ trials.” Keeping that equivalence and the boundary convention explicit prevents both tail-direction errors and invalid trial indices.

Key takeaway: For independent trials with success probability $p$, $P(T_r\le n)=P(B_n\ge r)$, while $P(T_r>n)=P(B_n\le r-1)$. Use a CDF difference for intervals, and only write binomial counts at nonnegative trial numbers.

Check Your Understanding

Use the event equivalence and boundary conventions to answer these questions.

For the fourth success, express $P(T_4\le9)$ as a probability involving a binomial count. Which tail is it?
For $r=2$, express $P(T_2>5)$ as a binomial probability and state its possible count values.
Explain why the binomial-difference formula for $P(a\le T_r\le b)$ was restricted to $1\le a\le b$.
If $r=3$ and $n=2$, what is $P(T_3\le n)$, and why?
Write $P(0\le T_2\le4)$ using the extended CDF $F$, without defining a binomial count at a negative index.

Negative-Binomial Tails as Binomial Probabilities

What You'll Learn