Negative Binomial Waiting Time for a Fixed Number of Successes

Waiting for a Fixed Number of Successes

A geometric waiting time ends at the first success. In many applications, however, a process continues until it has accumulated a specified number of successes: a laboratory may need several valid readings, a reviewer may need a fixed number of qualifying files, or a system may be monitored until a target number of events occurs. The negative binomial waiting-time model describes the trial on which the target success is reached.

The model is built from repeated Bernoulli trials. A trial has one of two outcomes, success or failure, and its success probability remains constant. A valid interpretation therefore depends not only on how many successes are required, but also on whether the trials can reasonably be treated as independent and identically distributed.

Definition: Let $I_j$ equal 1 when trial $j$ is a success and 0 when it is a failure. Suppose $I_1,I_2,\ldots$ are independent Bernoulli random variables with $P(I_j=1)=p$, where $0<p<1$. For a fixed positive integer $r$, define the trials-until-$r$-successes variable by $$ T_r=\min\left\{n\geq 1:\sum_{j=1}^{n} I_j=r\right\} $$ when the target is reached, and define $T_r=\infty$ if it is never reached. Under these assumptions, $T_r$ is finite with probability 1. The parameters are $r$, the required number of successes, and $p$, the success probability on each trial.

The value $T_r$ counts trials, not failures. It includes the trial that produces the $r$th success. The target requires at least $r$ trials, because one trial can produce at most one success. There is no finite upper limit on the number of trials: any number of failures may occur before the target is reached.

Assumptions and Support

Before applying this model, state what counts as a success and what one trial represents. Then check the assumptions: each trial has the same success probability $p$, outcomes on different trials are independent, and the target $r$ is fixed in advance. For example, a process in which success becomes more likely after each attempt is not described by this constant-$p$ model.

For $0<p<1$, the support—the set of possible values with positive probability—is

T_r\in\{r,r+1,r+2,\ldots\}.

The minimum value $r$ occurs if the first $r$ trials are all successes. Any larger integer can occur if the process has enough failures before reaching its $r$th success. Although $T_r=\infty$ is included in the definition so that the variable is defined even on an outcome where the target is never reached, it has probability zero under the stated assumptions.

To justify that last statement, let $N_n=\sum_{j=1}^{n}I_j$, the number of successes in the first $n$ trials. Then $N_n\sim\operatorname{Binomial}(n,p)$, and the event that the target has not been reached by trial $n$ is $N_n<r$. Thus

P(T_r=\infty)\leq P(T_r>n)=P(N_n<r) =\sum_{k=0}^{r-1}\binom{n}{k}p^k(1-p)^{n-k}.

For each fixed $k$, the term $\binom{n}{k}p^k(1-p)^{n-k}$ tends to zero as $n$ increases: the binomial coefficient grows at most like a polynomial in $n$, while $(1-p)^n$ decreases geometrically. There are only $r$ terms in the sum, so the sum tends to zero. Consequently, the probability of never reaching $r$ successes is zero. If $p=1$, the target is reached deterministically at trial $r$; if $p=0$, it is never reached. The usual negative binomial waiting-time model assumes $0<p<1$.

Relating Completion Time to a Success Count

A useful way to interpret events involving $T_r$ is to count successes by a fixed trial. Write $N_n$ for the number of successes in the first $n$ trials. The target has been reached by trial $n$ exactly when $N_n\geq r$. An exact completion time has a more specific description: to have $T_r=n$, the first $n-1$ trials must contain exactly $r-1$ successes, and trial $n$ must be a success.

Key relationship: For $n\geq r$, the event $T_r=n$ is the event that there are exactly $r-1$ successes among trials 1 through $n-1$, followed by a success on trial $n$. The event $T_r\leq n$ is the event that there are at least $r$ successes among the first $n$ trials.

These event descriptions follow directly from the definition: if trial $n$ is the first time the cumulative success count equals $r$, then the count just before it must be $r-1$, and trial $n$ must add one success. Conversely, those two conditions guarantee that the $r$th success occurs on trial $n$. For a deadline event, reaching at least $r$ successes by that deadline is equivalent to having reached the target on or before it.

Since $N_n$ has a binomial distribution under the independent, fixed-$p$ assumptions, binomial probabilities can be used to calculate deadline probabilities. The exact-time description can likewise be evaluated using a binomial count on the first $n-1$ trials together with the probability of success on the final trial.

Worked Example: Exact Trial of the Third Success

A hypothetical sensor records a valid reading with probability $0.5$ on each check. Checks are independent, and the probability stays fixed. What is the probability that the third valid reading occurs on check 6?

Method. Use the exact-completion-time event: checks 1 through 5 must contain exactly two valid readings, and check 6 must be valid.

Among the first five checks, the number of valid readings has a $\operatorname{Binomial}(5,0.5)$ distribution. The probability of exactly two is $$ \binom{5}{2}(0.5)^2(0.5)^3 =10(0.25)(0.125) =0.3125. $$

The probability check 6 is valid is $0.5$. By independence, multiply the two probabilities: $$ P(T_3=6)=0.3125(0.5)=0.15625. $$

Thus the probability is $0.1563$ to four decimal places. The answer is less than the probability of exactly three valid readings in six checks, because that latter event also includes sequences in which the third valid reading occurred before check 6. The calculation uses the trials-until-successes convention and includes the final successful check.

Worked Example: Reaching a Two-Success Target by a Deadline

A hypothetical document-screening process classifies each file as qualifying with probability $0.4$. Assume files are screened independently with the same probability. Find the probability that the second qualifying file is found by the end of the fifth file.

Method. “By the end of the fifth file” means $T_2\leq5$. This occurs if and only if at least two of the first five files qualify. Let $N_5$ be the number of qualifying files among the first five. Then $N_5\sim\operatorname{Binomial}(5,0.4)$, so it is convenient to subtract the cases of zero and one qualifying file from 1.

The probability of no qualifying files is $$ P(N_5=0)=\binom{5}{0}(0.4)^0(0.6)^5=0.07776. $$

The probability of exactly one qualifying file is $$ P(N_5=1)=\binom{5}{1}(0.4)(0.6)^4 =5(0.4)(0.1296) =0.2592. $$

Therefore, $$ P(T_2\leq5)=P(N_5\geq2) =1-0.07776-0.2592 =0.66304. $$

The probability is $0.6630$ to four decimal places. The event is “at least two successes by the deadline,” not “exactly two successes in five trials”: the process may have reached its target earlier and may have additional successes by trial 5.

Worked Example: A Specific Completion Time and the Support

A hypothetical quality check passes with probability $0.25$ on each independent inspection. The inspection process stops once four passes have occurred. Find the probability that the fourth pass occurs on inspection 7, and state the possible finite completion times.

Method. For $T_4=7$, the first six inspections must include exactly three passes, and inspection 7 must be a pass. The number of passes in the first six inspections has a $\operatorname{Binomial}(6,0.25)$ distribution.

The probability of exactly three passes in the first six inspections is $$ \binom{6}{3}(0.25)^3(0.75)^3 =20\left(\frac{1}{64}\right)\left(\frac{27}{64}\right) =\frac{540}{4096}. $$

Inspection 7 passes with probability $0.25=\frac14$, independently. Hence $$ P(T_4=7)=\frac{540}{4096}\left(\frac14\right) =\frac{540}{16384} =\frac{135}{4096} =0.032958984375. $$

The probability is $0.0330$ to four decimal places. Four passes require at least four inspections, and any larger integer is possible, so the finite support is $\{4,5,6,\ldots\}$. Under the stated model, the probability that the target is never reached is zero.

Common Exam Trap: Counting Successes at the Wrong Time

A frequent error is to treat an exact completion time as if it were simply a fixed-trial success count. For example, one might calculate $P(T_3=6)$ by finding the probability of exactly three successes in six trials. That calculation includes sequences in which the third success occurred before trial 6, so it does not describe a first attainment on trial 6.

For the sensor example, the incorrect calculation is $$ P(N_6=3)=\binom{6}{3}(0.5)^3(0.5)^3 =20(0.5)^6 =0.3125. $$

This is the probability of exactly three successes in all six checks, not the probability that the third success is on check 6. The corrected event requires exactly two successes in the first five checks and a success on check 6: $$ P(T_3=6)=\binom{5}{2}(0.5)^2(0.5)^3(0.5) =0.15625. $$

A second trap is to use the model when its assumptions do not hold. If the success probability changes from trial to trial, or one outcome affects the probability of a later outcome, then the binomial count and the calculations above need not apply. The model is appropriate only when the Bernoulli trials are independent and share the same success probability.

Key takeaway: The negative binomial waiting time $T_r$ is the trial number of the $r$th success under independent Bernoulli trials with fixed success probability $p$. Its finite support begins at $r$ and continues without an upper bound. For an exact completion time, count $r-1$ successes before the final successful trial; for completion by a deadline, count at least $r$ successes by that deadline.

Check Your Understanding

For each problem, identify the relevant completion-time event before calculating.

A hypothetical test produces a positive result with probability $0.3$ independently on each trial. The process stops at the third positive result. What is the minimum possible value of $T_3$, and what is $P(T_3=3)$? (Answer: Minimum $3$; probability $0.0270$.)
A hypothetical machine produces an acceptable part with probability $0.5$ independently on each attempt. Find the probability that the second acceptable part is produced on attempt 4. (Answer: $0.1875$.)
A hypothetical archive search finds a relevant record with probability $0.2$ on each independent file. Find the probability that the second relevant record is found by the end of file 3. (Answer: $0.1040$.)
Independent trials have success probability $0.6$, and the target is four successes. State the finite support of the trials-until-target variable and the probability that it is infinite. (Answer: $\{4,5,6,\ldots\}$; probability $0$.)
A hypothetical component passes an independent inspection with probability $0.25$. Find the probability that the third pass occurs on inspection 5. (Answer: $0.0527$.)

What You'll Learn