The fifth a third stage never reaches

Two rules for a fixed-width interval sit at opposite ends of one trade, and the field’s last two essays measured both ends. Stein’s two-stage rule reads the spread once, from the first few observations, and takes as many more as that reading asks for. Its interval is exact for every σ, and at a first stage of five it pays 2.03 times the observations that knowing σ would need. The purely sequential rule re-reads the spread after every observation and stops the first time it is satisfied. It spends 0.88 times the oracle and covers 90.5% where it claims 95%, and the essay that took that shortfall apart found it was not the randomness of the sample size but its dependence on the same observations the interval is built from.

That diagnosis suggests a rule in the middle, and the literature has one. Peter Hall’s three-stage procedure takes a first stage, reads the spread, and takes a second stage up to a fixed fraction ρ of what that spread asks for — not all of it. It then re-reads the spread on everything collected and takes a third stage to the rest. The point of the middle stage is that the third stage’s target is read from many observations rather than five, which is where the two-stage rule’s overspend comes from; and the point of stopping only twice is that the target is never read at the moment it happens to be satisfied, which is where the sequential rule’s shortfall comes from. On paper it inherits the good half of each.

It does not, at a first stage of five, and the reason is worth more than the rule.

A rule whose coverage can be computed #

The first thing the three-stage rule buys is not a number of observations. It is that its coverage can be computed exactly, which the sequential rule’s cannot.

Every quantity the rule’s final sample size N is computed from is a sample spread. For normal observations the spread of a sample is independent of its mean, and that survives the staging: the first stage’s spread decides how many observations the second stage adds, and the mean of all of them is still independent of every spread read along the way. So given N, the final mean is exactly normal with variance $\sigma^2/N$, and the probability that an interval of half-width d covers is $2\Phi(d\sqrt{N}/\sigma) - 1$. The coverage is the average of that over the distribution of N.

That distribution is one integral. Write $X_1$ for the first stage’s sum of squared deviations, a $\chi^2$ on $n_0 - 1$ degrees of freedom. Given $X_1$, the second stage’s size T is fixed, and the sum of squares on all T observations is $X_1$ plus a fresh $\chi^2$ on $T - n_0$ degrees of freedom. The third stage brings the sample to N = max(T, ⌈z²s_T²/d² + c⌉), so $P(N \le n \mid X_1)$ is a $\chi^2$ distribution function evaluated at a line in $X_1$. Integrating $X_1$ out over twelve hundred of its own quantiles gives the whole distribution of N, the coverage and the mean spend with no simulation in them. The same construction with one stage gives Stein’s rule, where it reproduces the theorem: at a half-width of 0.4 and a first stage of five, the two-stage rule covers 95.42%, above its level, on a mean of 48.70 observations.

A computation with no noise in it can still be wrong, so it is checked against the rule run directly — the habit a single interval’s miss argues for, of counting what a claim delivers rather than trusting its derivation. A hundred thousand drawn experiments at the same setting cover 88.41%; the integral says 88.42%. That is the first number the essay turns on.

The rule as written, with ρ = 0.5 and nothing added, spends 0.86 times the oracle — 20.76 observations where knowing σ would need 24.01 — and covers 88.42%. That is two points worse than the sequential rule it was meant to repair, on two fewer observations than the sequential rule took. The middle stage has removed the dependence and the coverage got worse. Whatever is wrong here is not the defect the previous essay found.

The experiments whose second stage bought nothing #

The integral can be split by what happened in it, and the split that explains the number is whether the second stage took any observations at all.

The second stage targets half of what the first spread asks for. If the first five observations happen to sit close together, half of what they ask for can be five or fewer, and the second stage adds nothing. At a half-width of 0.4 that happens whenever the first sample variance is below 0.4165 — a $\chi^2$ on four degrees of freedom below 1.67 — and that is 20.3% of experiments. In those experiments nothing is re-estimated. The third stage reads the same spread from the same five observations a second time and takes as many more as that low reading asks for.

Those experiments end on 7.1 observations on average and cover 70.5%. The four fifths whose second stage ran end on 24.2 and cover 93.0%. The stuck fifth alone accounts for 76% of the rule’s shortfall from 95%. The rule fails where its own design premise — the third stage reads a spread from many observations — was never met.

This is the two-stage rule’s defect, back in a different place. Stein pays for a low first spread by multiplying by $t^2/z^2$, which at four degrees of freedom is 2.01, in every experiment, so the experiments with a low reading are protected along with everyone else. The three-stage rule uses z throughout, on the reasoning that by the third stage the spread rests on enough observations for z to be honest. In a fifth of experiments it rests on five, and z on five observations is exactly the mistake Stein’s t exists to prevent — the same mistake, in a different setting, that studentising a bootstrap interval pays to avoid when its scale rests on two or three numbers.

Concavity, not bias #

The rule’s mean sample size is 3.25 observations under the oracle, and it is tempting to read the shortfall as that bias. Most of it is not.

The coverage an interval of half-width 0.4 has on n observations is $2\Phi(0.4\sqrt{n}) - 1$, which climbs steeply through the small sample sizes and flattens past the oracle. At the rule’s mean of 20.76 observations it is 93.16%. The rule delivers 88.42%. Of the points missing, only 1.84 come from the mean being low; the other 4.75 come from N being spread around that mean under a concave curve. An experiment that ends at 7 observations covers about 71%; one that ends at 40 covers about 99%; and the two do not average back to what an experiment of 23 or 24 would have delivered.

That is what separates this rule’s failure from the sequential rule’s. The sequential rule’s sample size is tight — a standard deviation of 8.60 at this setting — and its defect is the dependence. The three-stage rule has no dependence and a standard deviation of 10.81, and the extra spread, concentrated at the bottom of the range, is the whole defect. Both rules fall short by similar amounts for unrelated reasons, which is why the three-stage rule cannot be thought of as the sequential rule with one source of error removed.

The constant is not a constant #

Hall’s rule has a repair built in: a constant c added to the third stage’s target, so N = max(T, ⌈z²s_T²/d² + c⌉). The asymptotic theory — the same kind of result as the shortfall vanishing as the required width goes to zero — says c can be chosen so the coverage error vanishes faster than it otherwise would, and that the right c is a fixed number that does not grow with the experiment. Because the coverage here is exact, c can be chosen by bisection rather than by expansion: the number that makes the rule cover exactly 95%.

At a half-width of 0.4 it is 8.50 observations. The tuned rule then covers 95.00% on a mean of 28.82, which is 1.20 times the oracle — under two thirds of the two-stage rule’s spend for the same guarantee. That is a real improvement and the headline the rule deserves.

But it is not a constant. Across requirements from a half-width of 0.7 down to 0.15 — oracle sample sizes from 7.8 to 170.7 — the c that restores the level runs 1.90, 5.39, 8.50, 12.99, 15.57 and 19.07. The tuned rule’s spend as a share of the oracle runs 1.20, 1.20, 1.20, 1.19, 1.17 and 1.09: a proportion, and nearly the same one throughout the practical range. The asymptotic constant is derived in a theory where the first stage grows with the experiment, and the defect it corrects is then a second-order term. Here the first stage is five observations whatever the requirement, the stuck fifth is a fifth at every width, and a correction aimed at it has to scale with the experiment because the experiment’s other observations are what it is paying with.

The split figure shows what the constant does with its observations. It raises the stuck experiments from 70.5% to 87.6% and the experiments whose second stage ran from 93.0% to 96.9%. The level is reached on average by making four fifths of experiments over-cover enough to pay for the fifth that still under-covers. Every experiment pays eight and a half observations to protect the twenty per cent that needed more.

A repair aimed at the fifth #

That suggests a different repair. The stuck experiments are stuck because the second stage can be empty, and the second stage can be made not to be. Require that the first two stages together reach at least some floor, whatever the first spread says, and the third stage always reads a spread from more than the five observations that produced the low reading.

The two repairs can be priced in the same currency. Each point on either curve is a mean spend and the coverage it buys. A floor of ten observations spends 23.35 on average and covers 92.43%; the constant, at that same mean spend, covers 91.13%. A floor of fifteen spends 24.61 and covers 93.95% against the constant’s 92.25%. A floor of eighteen covers 94.63% where the constant at its spend covers 92.78%. At a floor of twenty-one the rule covers 95.30% with no constant at all, on 1.087 times the oracle, against the constant’s 1.200 for the same guarantee.

The floor wins for the reason the split gave. The constant spends the same number of observations in every experiment. The floor spends them only in experiments whose first reading was low, which are the experiments that under-cover, and it spends them before the spread is re-read, so they improve the reading as well as lengthening the sample.

There is a cost to the comparison that should be stated. A floor of twenty-one observations is a floor chosen knowing that the oracle is twenty-four, and the oracle is what σ would say. A rule whose floor has to be set near the answer is a rule with a guess of σ in it, and that is the two-stage rule’s lesson again: everything works once the first look is large enough. What the floor shows is where the rule’s observations are worth spending, not that the problem has gone. It is the same lesson a block size that changes drew from a schedule: an adaptation is cheap where it reads something the interval does not need, and dear where it reads the thing itself. A floor of ten, which needs only a rough sense that the experiment will be tens of observations rather than hundreds, already recovers most of what the constant buys at that price.

What the first stage decides #

The whole story is a story about a first stage of five, and it changes as the first stage grows.

At a first stage of ten the stuck share rises to 41.4% — ten observations is closer to half of 24 — but the stuck experiments cover 86.8% rather than 70.5%, because ten observations is a far better reading. The untuned rule covers 92.11%, on par with the sequential rule’s 92.67%, and the constant falls to 5.00, for a tuned spend of 1.13 times the oracle against the two-stage rule’s 1.36.

At a first stage of twenty the rule is stuck in 96.6% of experiments, because twenty is almost the whole oracle and half of what it asks is usually already there. The rule then is a two-stage rule with z in place of t, and it covers 95.02% with no constant, on 1.065 times the oracle — against the two-stage rule’s 1.188 and the sequential rule’s 1.031 at 94.67%. With a long first stage all three rules are good and the differences are small, which was also where the previous essay ended up. Every defect in this field is a defect of a short first stage.

The fraction ρ the second stage aims at turns out to matter very little. Across ρ from 0.2 to 0.95 the untuned rule covers between 88.03% and 91.70%, and the tuned spend runs between 1.196 and 1.292 times the oracle, with its minimum near ρ = 0.35. Aiming the second stage higher shrinks the stuck share but also lets the second stage overshoot, and the two roughly cancel. The middle stage is worth having; how much of the way it goes is a detail.

What a practitioner should take from three rules #

The three-stage rule is the rule to run when observations are expensive and a guarantee is wanted, and it is the stopping half of the trade a design chosen from the data found free on the other half: there, choosing where the runs go cost nothing, and here choosing how many is worth computing exactly. Tuned, it reaches the two-stage rule’s coverage at 59% of its spend at a first stage of five. But the tuning is not a constant read from a table. It is a proportion of the experiment that has to be computed for the first stage actually used, and the computation is cheap enough — an exact integral rather than a simulation — that there is no reason to borrow an asymptotic value.

Better still is to look at where the rule fails before tuning it. A fifth of its experiments never run the middle stage, and every other repair spends observations on experiments that did not need them. A floor on the second stage aims the observations at the experiments that do.

And the comparison with the sequential rule should be read as two different failures, not as better and worse versions of one. The sequential rule’s interval is short because it stops when the spread looks small; the three-stage rule’s interval is short because some of its experiments are short, and the coverage curve punishes short experiments more than it rewards long ones. One repair, a fresh variance, fixes the first and does nothing for the second. One repair, a floor, fixes the second and is irrelevant to the first.

Still open: a floor that reads the first stage #

The floor here is a number of observations fixed before the experiment, and the only floors that work well are ones set near the oracle — which is to say, set by somebody who already knows roughly what σ is. The natural next rule makes the floor a function of the first stage: run the second stage to at least ρ of the target computed with t on $n_0 - 1$ degrees of freedom rather than z, so that a low first reading is inflated by Stein’s own factor exactly when it is the only reading the rule has. That keeps the rule free of any guess and aims the inflation at the stuck experiments alone. Whether it beats the fixed floor at equal spend, and whether its coverage stays at the level across the whole range of requirements without any constant at all, is a computation the same integral can make.

What is claimed here, and what is not #

This essay takes a three-stage stopping rule for a fixed-width interval on a normal mean, computed exactly. The claims are that the rule’s coverage is an exact average of $2\Phi(d\sqrt{N}) - 1$ over N, matching a hundred thousand drawn experiments to a hundredth of a point; that as written, at a first stage of five and a half-width of 0.4, it covers 88.42% on 0.86 times the oracle; that 20.3% of experiments run no second stage and account for 76% of the shortfall; that most of the shortfall is the spread of N under a concave curve rather than its mean; that the constant restoring the level grows from 1.90 to 19.07 observations across requirements while the tuned spend stays near 1.2 times the oracle; and that a floor on the second stage covers more than the constant at every shared spend.

What stays out, named as a decision: non-normal observations, where the spread is no longer independent of the mean and the exact computation is unavailable — the sequential rule’s dependence then comes back in a weakened form and would have to be simulated; Hall’s asymptotic constant itself, which is not computed here because the exact one replaces it; and intervals that are not fixed-width, where the corrected sequential intervals are the answer and the question is a different one.

The boundary against the stopping-rule field’s own boundary is the same as for the two earlier essays on stopping in this field: that field owns what looking does to a test’s error rate, and this one owns what a rule for how many observations does to an interval’s coverage. The boundary against the blinded rules is that those read a quantity the interval does not use, so their stopping is free, and what the blindfold costs is the price of that freedom rather than of any dependence; every rule here reads the spread the interval needs, and the cost of doing so is what is measured.

The checks, and the refusal that makes them mean something #

The integral is checked against a hundred thousand experiments drawn from the rule itself, and the two-stage version of it is checked against Stein’s theorem at every first stage and requirement drawn. Each figure checks its own claim at every setting of its slider: the tuned rule reaches 95% on fewer observations than the two-stage rule, the stuck experiments cover less than the rest before and after the constant, the constant grows as the requirement tightens, and the floor covers more than the constant at every shared spend. The refusal is a three-stage rule with no middle stage — ρ set so low that the second stage never runs — which is a two-stage rule with z in place of t, and which the checks require to fall below its level at a first stage of five. It does, at 89.09% on 1.02 times the oracle — a check that passed it could not tell z from t on four degrees of freedom.