Lesson 6 of 22

Wait for a success target: negative-binomial laws and censoring

Derive the stopped-trial law, its moments and the exact effect of a recording cap.

Loading your saved responses…

Try the optional starting-point checks and targeted refreshers. You can continue directly into this lesson.

Try

A test rig repeats an independent trial with success probability 1/2 until it records two successes. Does “four trials” mean that exactly four trials were planned, or that the second success occurred on trial four? The first experiment gives a binomial success count. The second asks for a stopping time, the random number of trials needed to reach a target.

Write the length-four records whose second success occurs on the last trial. Using S for success and F for failure, they are SFFS, FSFS and FFSS. Each has probability 1/16, so the event has probability 3/16. The record SSFF has two successes in four trials but reached the target at trial two. Including it would answer a different question.

Predict

The rig can observe at most four trials. Predict the chance that the target is still unmet at the cap. An unfinished run reports “more than four,” not “four.” Should an analysis discard those records, or replace their stopping times with four? Neither operation preserves the original stopping-time distribution.

Experiment

What does the cap hide?

Predict before changing a setting. These are exact probabilities for specified synthetic models, not sampled observations or a fitted model. Settings are temporary; record your prediction and explanation in the written task. Recalculation does not supply new independent evidence or award mastery.

Success target rSuccess probability pObservation cap c (trials)

Independent Bernoulli trials, common p=1/2. T is the total trial index of success number 2; F=T−2 counts failures. A censored record reports T>4, not T=4.

Completed probability: 11/16. Censored probability: 5/16. They sum to 1.

Each track spans probability 0 to 1. Bar length is probability, not an observed frequency.

T=2, F=0: 1/4

T=3, F=1: 1/4

T=4, F=2: 3/16

T>4 (censored): 5/16

The displayed tail is independently computed as P(Binomial(4, 1/2)<2). The original infinite distribution is not renormalized onto completed rows. If the cap is below r, every observation is censored.

Uncensored E(T) = r/p: 4 trials
Uncensored Var(T) = r(1−p)/p²: 4 trials²
E(min(T,c)): theoretical capped work: 13/4 trials
E(T | T≤c): theoretical mean among completed records: 32/11 trials

These are three different theoretical means, not an empirical average. Dropping censored records estimates a conditional quantity. Assigning their stopping time to the cap confuses actual stopping with capped work.

Bounded CPU calculation: at most 12 stopping bins, 13 fixed-count terms or 45 categorical count vectors. Integer numerators/denominators are exact in these bounds (largest probability denominator 4¹²); displayed decimal covariance summaries are separate. No random simulation, worker or network is used.

Before changing the defaults, predict all completed masses and the tail. Then set the target above the cap. Explain why a conditional mean among completed records becomes undefined while capped work remains defined. Finally use success probability one to check the deterministic boundary.

Understand

Let the trials be independent Bernoulli random variables with the same success probability p, where 0<p≤1. Let r≥1 be an integer. Define Tᵣ as the trial index of the rth success, so Tᵣ takes values r,r+1,…; define Fᵣ=Tᵣ−r as the number of failures before that success, taking values 0,1,…. Both are called negative-binomial variables under different conventions. Always name the convention and support before using a formula.

Derive the mass from the observation rule

For Tᵣ=t, trial t must be a success and exactly r−1 of the preceding t−1 trials must be successes. Choose their positions and multiply the probability of each resulting word:

P(T_r=t)=\binom{t-1}{r-1}p^r(1-p)^{t-r},\qquad t=r,r+1,\ldots.

The coefficient counts eligible records; it does not choose r positions freely among all t, because the final success position is fixed. Substituting t=f+r gives the failure-count version:

P(F_r=f)=\binom{f+r-1}{r-1}p^r(1-p)^f,\qquad f=0,1,\ldots.

At p=1, Tᵣ=r and Fᵣ=0 surely, with the zero-exponent factor interpreted as one. At p=0 the target is never reached, so there is no proper finite-valued law on these supports; do not substitute zero into a finite-mean formula.

Normalize the law and justify independent waiting gaps

Let Gⱼ be the number of trials from success j−1 to success j, including the latter success; before success one, start at trial one. For any positive integers g₁,…,gᵣ, specifying all these gaps determines one finite success/failure word ending at the rth success. Independence of the original trials gives

P(G_1=g_1,\ldots,G_r=g_r)=p^r(1-p)^{g_1+\cdots+g_r-r}=\prod_{j=1}^r p(1-p)^{g_j-1}.

Each geometric mass sums to one because its geometric series does. Summing the finite product of nonnegative series therefore gives total one. This proves that all r successes occur almost surely and that the gaps are independent geometric variables. We did not assume that arbitrary random blocks are independent; we proved factorization from each finite word.

Now Tᵣ=G₁+⋯+Gᵣ. Group the gap tuples by their sum t. There are C(t−1,r−1) ways to split t into r positive parts, by choosing r−1 divider positions in the t−1 internal gaps. This reproduces the mass formula and proves its infinite sum is one.

Derive moments with the convention intact

The geometric trial-count lesson gives E(G)=1/p by tail summation. Write q=1−p. Differentiating the convergent geometric series for |q|<1 twice gives

E[G(G-1)]=\sum_{g\ge1}g(g-1)pq^{g-1}=\frac{2q}{p^2}.

Consequently E(G²)=2q/p²+1/p, and subtracting 1/p² yields Var(G)=q/p². Independent gaps add variances as well as means:

E(T_r)=\frac r p,\quad \operatorname{Var}(T_r)=\frac{r(1-p)}{p^2},\quad E(F_r)=\frac{r(1-p)}p,\quad \operatorname{Var}(F_r)=\operatorname{Var}(T_r).

For r=3,p=1/4, the expected total is 12 trials, the expected failures are 9, and the variance is 36 squared count units. Subtracting a constant changes the mean, not the variance. These are model expectations; they do not say every run ends near its mean.

A stopping/count identity makes the cap transparent

The event Tᵣ>c means exactly that the first c trials contain fewer than r successes. Thus

P(T_r>c)=P(\operatorname{Binomial}(c,p)<r)=\sum_{j=0}^{\min(r-1,c)}\binom cj p^j(1-p)^{c-j}.

This is an equality of events in the same trial sequence. The finite sum calculates the tail exactly; it does not turn the infinite law into a finite law. At the default r=2,p=1/2,c=4, completed masses are 1/4,1/4,3/16 at times 2,3,4. The remaining 5/16 is censored. The weighted completed time is 2, giving three different quantities:

E(T)=4: the uncensored stopping mean.
E(min(T,4))=2+4·5/16=13/4: expected work performed before completion or the cap.
E(T | T≤4)=2/(11/16)=32/11: expected stopping time among completed runs.

These are theoretical quantities, not empirical averages. Dropping unfinished records changes the population being described. The binary completion flag must be retained even when work stops at c; a true completion at c and an unfinished run with c trials of work are different outcomes.

Apply

Change the mechanism: draw one Bernoulli(p) coin B and repeat its value on every trial. Each trial still has success probability p, but the trials are dependent. With probability p the target is reached at r; otherwise it is never reached. For 0<p<1 the expected stopping time is infinite. Identify exactly which factorization in the gap proof fails, then explain what the cap records on each branch.

Continue

Continue with multinomial counts and protocol dependence to compare ordered trials with dependent count summaries. Existing without-replacement evidence in P-1 and the discrete family introduction cover a different sampling mechanism; neither should be relabeled as this stopping protocol.

Primary comparison: MIT 18.600, Fall 2019, Lecture 14, retrieved 28 October 2026. The original tasks and cap comparison here develop the named law, not a claim of complete course equivalence or empirical independence.

Apply · explain · revise

Practice and reasoning

Drafts save locally as you type. Reveal worked solutions when useful; the site remembers that exposure. Automatic matches check the requested answer, while written arguments require review against the rubric.