Negative Binomial: Wait for the r-th Success
How many independent Bernoulli trials are needed to reach the r-th success?
How this lesson unfolds.
Begin with How does the stopping condition of an experiment determine whether a count follows a Binomial, Geometric, or Negative Binomial model? The sequence then connects The Last Trial Must Be the r-th Success and builds toward Independent Waiting-Time Variances Add.
How does the stopping condition of an experiment determine whether a count follows a Binomial, Geometric, or Negative Binomial model?
Distinguishing stochastic models hinges on identifying the terminal trigger: when the protocol conducts a pre-set quota of trials and tallies successes, binomial applies; when the protocol repeats attempts until a quota of successes is reached, the waiting duration governs.
- $$X \sim \operatorname{NB}(r, p), \quad X \in \{r, r+1, \dots\}, \quad \sum_{i=1}^X I_i = r \text{ with } I_X = 1$$
- $$Binomial fixes total trials $n$ and counts successes; Geometric waits for the 1st success ($r=1$); Negative Binomial fixes the required success quota $r$ and records the total trials $X$ taken to reach it.$$
- Learning goalDistinguish Negative Binomial models from Binomial and Geometric trials by stopping conditions.
- Helpful foundationsBernoulli trials · Binomial distribution · Geometric distribution · Foundations of the Theory of Probability (Kolmogorov, 1933) · An Essay towards solving a Problem in the Doctrine of Chances (Thomas Bayes, 1763)
- Common trapBinomial fixes total trials n; Negative Binomial fixes quota r with random trials.
- Next connectionDerive the probability mass function for quota completion on trial x.
More context & mechanics
In repeated independent Bernoulli trials with success probability p, the experimenter's stopping rule determines the mathematical family:
- If you decide beforehand to run n=50 trials, the success count K is random ~ Binomial(n, p).
- If you test until you encounter the very first success, the trial count X is random ~ Geometric(p).
- If you test until you accumulate exactly r successes, the total trials X is random ~ Negative Binomial(r, p).
The quota r is deterministic; the duration X is stochastic.
In automated fuzzing and cybersecurity penetration testing, an attack harness executes randomly mutated network payloads until it successfully discovers r=5 distinct exploitable memory corruptions. The number of packets required to trigger those 5 exploits is Negative Binomial.
Pierre Rémond de Montmort first formulated this distribution in his 1713 work Essay d'analyse sur les jeux de hazard while analyzing the classic 'Problem of Points'—determining fair division of stakes when a game is interrupted before a player achieves the required quota of winning points.
'Quota Stops the Clock': If trials are fixed, it's Binomial. If the success quota is fixed, it's Negative Binomial.
Why does the Negative Binomial PMF use combinations C(x-1, r-1) rather than C(x, r)?
Waiting for r = 3 successes with p = 0.4 on trial k = 6 means trial 6 is rigidly locked to success; the preceding 5 trials can distribute the other 2 successes across 5 choose 2 = 10 arrangements, yielding P(X=6) = 10 × (0.4)³ × (0.6)³ = 0.13824 (13.82%).
- $$P(X=x) = \binom{x-1}{r-1} p^{r-1} (1-p)^{x-r} \cdot p = \binom{x-1}{r-1} p^r (1-p)^{x-r}$$
- Learning goalDerive the Negative Binomial PMF by conditioning on the fixed final success.
- Helpful foundationsCombinations formula · Negative binomial stopping rule · Independent probabilities · Foundations of the Theory of Probability (Andrey Kolmogorov, 1933) · An Essay towards solving a Problem in the Doctrine of Chances (Thomas Bayes, 1763)
- Common trapUsing C(x, r) permits premature stopping, violating the requirement that trial x is success r.
- Next connectionDecompose total trials into a sum of independent geometric waiting times.
More context & mechanics
For an experiment to terminate on exactly trial x with r successes, two events must occur in tandem:
- Among the preceding x-1 trials, exactly r-1 successes and (x-1)-(r-1) = x-r failures must appear in any order: C(x-1, r-1) p^(r-1) (1-p)^(x-r).
- The x-th trial must yield a success: multiplying by an independent factor of p.
Combining terms produces P(X=x) = C(x-1, r-1) p^r (1-p)^(x-r).
In telecommunication protocols like TCP with Selective Repeat ARQ, a client requests r=4 consecutive uncorrupted packet headers to establish a TLS handshake. If the transmission channel bit-error rate is 1-p, this formula yields the exact probability distribution of transmission attempts.
Blaise Pascal noted this exact combinatorial structure in 1654 during correspondence with Pierre de Fermat: the final decisive round in a match must belong to the ultimate victor, fixing the last index in the combinatorial tree.
'Seat x is Reserved': The final success is locked in seat x. The other r-1 successes choose seats freely among the first x-1 trials: C(x-1, r-1).
How does breaking down the Negative Binomial count into independent Geometric stages make computing its expected value instantaneous?
Reaching r targets decomposes into r consecutive milestones: waiting for success 1, then resetting the clock and waiting for success 2, and so on; by linearity of expectation, the total expected trials add directly to E[X] = r/p = 3 / 0.4 = 7.5.
- $$X = \sum_{i=1}^r G_i, \quad G_i \sim \operatorname{Geometric}(p) \implies E[X] = \sum_{i=1}^r E[G_i] = \frac{r}{p}$$
- $$Reaching $r$ successes is equivalent to waiting for the 1st success, then waiting for the 2nd, up to the $r$-th; by linearity of expectation, $E[X] = \sum E[G_i] = r/p$.$$
- Learning goalCalculate Negative Binomial expectation by decomposing trials into independent Geometric waiting times.
- Helpful foundationsGeometric expectation · Linearity of expectation · Random variable decomposition · Foundations of the Theory of Probability (Andrey Kolmogorov, 1933) · An Essay towards solving a Problem in the Doctrine of Chances (Thomas Bayes, 1763)
- Common trapSumming infinite series is unnecessary when expectation decomposes linearly into geometric stages.
- Next connectionLeverage independence across geometric stages to compute total variance.
More context & mechanics
Let G₁ be the trials until the 1st success. Because Bernoulli trials are memoryless, after success 1 occurs, the process restarts fresh: let G₂ be the additional trials until the 2nd success, continuing through G_r. Each Gᵢ is an independent Geometric random variable with mean E[Gᵢ] = 1/p. Total trials is X = G₁ + G₂ + ṡ + G_r. Linearity of expectation yields E[X] = r/p.
In SaaS sales pipeline modeling, an account executive converts qualified leads with probability p=0.08. To hit a quarterly quota of r=12 enterprise contracts, management calculates the expected required customer demo calls as 12 / 0.08 = 150 calls.
Linearity of expectation was formalized by Andrey Kolmogorov in his 1933 Foundations of Probability, liberating probabilists from evaluating hypergeometric series by transforming expectation into a linear operator over sample spaces.
'Stacking the Waits': Each success costs an average wait of 1/p. Buying r successes costs r × (1/p) = r/p.
Why does the variance of the total wait scale linearly with r as r(1-p)/p²?
Because each successive milestone phase begins afresh without memory of previous droughts, their waiting-time fluctuations are statistically independent, allowing their variances to sum cleanly to Var(X) = r(1-p)/p² = 3(0.6)/0.16 = 11.25.
- $$\operatorname{Var}(X) = \sum_{i=1}^r \operatorname{Var}(G_i) = \frac{r(1-p)}{p^2}, \quad \operatorname{Cov}(G_i, G_j) = 0 \; (i \ne j)$$
- $$Because each trial is memoryless and independent, the waiting times between successive successes have zero covariance, allowing their individual geometric variances $(1-p)/p^2$ to sum directly.$$
- Learning goalDerive Negative Binomial variance using independence and stage variance additivity.
- Helpful foundationsVariance of geometric distribution · Variance of sum of independent variables · Covariance
- Common trapSumming r independent variables scales variance as r σ², not r² σ².
- Next connectionTransition from discrete waiting times to continuous Gamma distribution models.
More context & mechanics
Each intermediate geometric waiting stage Gᵢ has variance Var(Gᵢ) = (1-p)/p². Because Bernoulli trials have no memory, the trials spent waiting for success 2 share zero correlation with trials spent waiting for success 1: Cov(Gᵢ, Gⱼ) = 0. For independent variables, variance is strictly additive: Var(X) = ∑_(i=1)^r Var(Gᵢ) = r(1-p)/p². Standard deviation is √(r(1-p))/p.
In high-frequency algorithmic trading execution (e.g. TWAP/VWAP algorithmic execution), an algorithm targets r block fills. The risk engine uses r(1-p)/p² to establish 99% confidence value-at-risk (VaR) time-horizons for completing market orders.
Pafnuty Chebyshev published the universal variance additivity theorem for mutually independent variables in 1867, establishing the mathematical bridge from individual spread to macroscopic stability.
'Summing Spreads': Independent stages add their uncertainties. One wait spreads by (1-p)/p²; r independent waits spread by r(1-p)/p².