Normal Distribution
nothing is called 95% until it has been counted
Concept

Combinatorial search — where it appears

Choosing the best subset of a list by scoring every subset, which is exact and grows as a binomial coefficient. It is affordable over eight functions and not over twenty-four, and what replaces it past that point has a warrant of a weaker kind.

Named by 18 essays across 8 fields — each of them below, with the objects they name alongside it.

A proposal that moves more, refused more often. The two halves of the trade, both exact, on the 410 admissible assignments of twelve units. The integrated autocorrelation time of an imbalance the rule was never handed falls from 7.30 at one swap to 3.97 at three, and the acceptance rate falls with it, from 58.8% to 40.8%. A rejected proposal costs one evaluation and leaves the chain where it was, so acceptance is not the price of anything and the ranking by acceptance is the reverse of the ranking by cost. Past three the family folds: exchanging k of six from each arm is the complement of exchanging six − k, so k = 5 has the same 36 proposals as k = 1 and k = 6 has 1.

A proposal that moves more than two units

The walk's autocorrelation is a fact about its step size and not about its acceptance rate. Exchanging three units from each arm mixes nearly twice as fast as exchanging one, and is refused a third more often.

blocks · Randomisation What each pair is made of. Each pair of searches, over 300 draws, split into the two effects its excess is the difference of. The overlap is what the second search loses by having the first already run at its own answer; the interaction is what the joint search finds by moving the first off it. They subtract to the excess exactly, on every draw, because the pinned supremum cancels. Two disjoint dictionaries of independent columns read an excess of 0.000011 and are made of 0.000514 and 0.000503. A break paired with a dictionary of step columns has an interaction of exactly 0 and is all overlap. And a break paired with an independent column has an overlap of -0.004395 against an interaction of 0.002364, which is what puts its excess below zero.

Two effects in one number

How much two searches over one sample share is measured as the net of two things — ground both of them find, and configurations only the joint search reaches. One extra supremum per draw separates them exactly.

separate · Break point Stationary is not the same as convergent. How far each k-swap walk is from uniform after t steps, started at the least balanced admissible assignment of 410. Every one of these chains has a symmetric proposal and rejects by standing still, so every one of them is doubly stochastic and every one preserves the uniform distribution exactly. Only five of the six get there. Exchanging all six units of each arm is a single proposal — the complement — and the admissible set is closed under complement, so the walk takes it every time and oscillates between two assignments for ever: after 160 steps it has visited 1 state and sits 0.9976 from uniform. Its stationary distribution is a fact about the matrix; its limit does not exist.

Stationary is not convergent

A walk that exchanges every unit in each arm preserves the uniform distribution exactly and never gets near it. Every doubly stochastic matrix has the same stationary distribution; only some of them have a limit.

blocks · Randomisation Both halves grow; the difference does not. The control pair's two components and their difference, against how much each of its two searches can find, over 1200 draws at each dictionary size. Two disjoint sets of independent columns are additive at every size — the excess stays inside a standard error or two of zero throughout — and it is not because there is nothing there. The overlap grows from 0.000112 at two columns to 0.000870 at ten, a factor of 7.76, and the interaction grows with it, staying within a factor of two of the overlap at every size. Two searches competing for one residual sum share ground and find configurations neither has alone, in almost equal measure, and their difference is what the earlier field's scale calls zero.

What a zero is made of

Two disjoint dictionaries of independent columns read an excess of 0.000116 and are made of an overlap of 0.000583 and an interaction of 0.000467. The control the whole scale is anchored on reads zero because two effects cancel.

separate · Break point One curve is a binomial coefficient and the other is a line. The number of subsets a maximin over this dictionary would have to score, against the number the exchange algorithm actually scores. At three functions the walk is 2,024 subsets and is the honest answer; at eight it is 735,471 and the exchange algorithm has looked at 421. The warrant for the second curve is the four sizes where both exist and agree, which is a weak warrant — it says the algorithm has not yet been wrong, not that it cannot be — and it is the only one available past the point the first curve leaves the page.

Where the enumeration stops

A maximin over an eight-function dictionary is a walk over seventy subsets. Over twenty-four it is 735,471 at eight functions, and the exchange algorithm that replaces the walk scores 421. What licenses the second curve is four sizes where both exist and agree, which is a weaker warrant than it looks.

product · Optimum A rate that does not know how large the trial is. The share of equal splits admitted by a tolerance of 1 coin-spreads on 3 functions, at six trial sizes. The first two are exact — 12,870 and 184,756 splits, walked, averaged over eight draws of the units — and the rest are sampled. From a hundred units on, the rate sits on (2Φ(1) − 1)^3 = 0.3182, which contains no n at all. The two small trials are 29.2% and 27.7% short of it, so the sixteen-unit measurement understates the rate rather than bracketing it. Meanwhile the admissible count — the rate times C(n, n/2) — goes from 2^11.5 to 2^393.7: the exhaustion a small trial runs into is a fact about small trials.

A count that has to be estimated

At sixteen units the admissible assignments can be counted by walking all 12,870 of them. At four hundred there are about 2^393.70, and the share admitted is 0.31885 against a closed form of 0.31818 that has no trial size in it at all. The exhaustion a small trial runs into is a fact about small trials.

product · Randomisation Thinness stays put and reachability does not. The same balancing rule and the same tolerance at five trial sizes. The admitted share barely moves — one admissible assignment in 27, 30, 30, 20, 18 — because the acceptance rate of a rerandomisation is a fact about the basis rather than about the number of units. What does move is the number of single swaps available: 36, 49, 64, 81, 100, growing like a quarter of the square of the trial size. Filled marks are sizes whose admissible set falls into more than one piece. The set is in 4 pieces at 12 units, 2 at 14, and one piece from 16 upwards. The fourteen-unit result is a statement about fourteen units.

A defect that is about size

The admitted share of a rerandomisation barely moves with the number of units. The number of admissible neighbours grows like the square of it, and that is what decides whether the walk can go everywhere.

reach · Randomisation The split depends on the order. How much two searches share, measured both ways round, over 300 draws. Pinning the first search at its own answer and searching the second gives one overlap; pinning the second and searching the first gives another. A break paired with an independent column reads -0.004395 one way and 0.002163 the other, at 8.70 paired standard errors and on opposite sides of zero. The excess the two components subtract to is the same in both orders by construction, so what changes is only how it is attributed. There is no order-free way to say which of two searches found ground both can reach, and the two orders bracket it.

A split that depends on the order

Run the second search first and pin that instead, and the same draw gives a different overlap and a different interaction — with the same difference. And one pair has no second order at all.

separate · Break point Whichever dial made the set thin, the crossing is at the same thinness. Each curve is one dictionary, swept over eight tolerances at two hundred units; a point above the line is a set thin enough that walking beats hunting. The curves lie nearly on top of one another, which is the answer to whether the crossing is a fact about the tolerance or about the thinness it produces: the crossings sit between one admissible assignment in 176 and one in 268 for dictionaries of 3 to 6 functions. The mechanism is that a hunt costs exactly 1/p and a walk costs almost the same everywhere — between 82 and 394 evaluations per usable draw across the whole table — so the crossing is wherever 1/p reaches a number that does not move.

The set a dictionary leaves

A rule constrained on six functions at a loose tolerance leaves a set as thin as one constrained on three at a tight one. Both sampling methods cross over at the same thinness, and the tolerance where that happens moves by a factor of three.

dict · Assignment How long a walk has to be given. Every equal split of twelve units is enumerated, the 410 admissible ones are found, the transition matrix is built, and the distance from uniform is computed exactly at each step — no simulation anywhere. The walk is started at the least balanced admissible assignment, which is the state a rejection sampler is least likely to have handed it and the one a burn-in has to cover. It is 0.0849 away after twenty steps and 0.00008 after ninety. A real cost, and a small one, and naming it is what stops it being assumed to be zero.

Walking the admissible set

A rerandomisation test hunts for admissible assignments and throws away the rest. A walk visits them instead — and it is exactly uniform only because it stands still when a proposal fails, which is the step that looks like waste.

joint · Randomisation The crossing barely moves. Both methods' costs in one unit — assignments evaluated per usable draw — as the tolerance tightens. A hunt costs 1/p and rises without limit: from 2.22 at a tolerance of 1.2 to 357.14 at 0.18. A walk costs its autocorrelation time and barely moves. The two cross at a tolerance of 0.190 at one swap and 0.195 at eight — the whole family of proposal sizes crosses inside a band of about two hundredths, because where the crossing is, the large proposal has already lost its advantage. A multi-swap proposal is worth a factor of 5.65 in the regime where the walk should not be used at all.

Where the gain is, and where the decision is

A bigger proposal is worth a factor of six at a loose tolerance and nothing at a tight one. The tolerances where it helps are the ones where a hunt costs two evaluations a draw, and the crossing barely moves.

blocks · Assignment What a second break adds. Over 200 draws, the likelihood ratio a search over one break point reports, and how much more a search over an ordered pair adds on top of it. Under AR(1) at 0.8, which has no break at all, the first search manufactures 5.697 and the second adds 4.278. Under a law with exactly one break — where a second one is as absent as the first was in the row above — the first search reports 9.442 and the second still adds 5.800. Searching for something that is not there costs the same whether or not something else was there to find.

A second break on a flat profile

Searching a hundred and twenty rows for one change point manufactures five units of likelihood. Searching for a second manufactures four more, on a series that has at most one — and on a profile whose whole range is under seven.

charged · Break point Where a walk is cheaper than a hunt. Both costs in the same unit. A rejection sampler evaluates 1/p assignments per independent draw and does not care how large the trial is; a walk evaluates one per step and yields an effective draw every τ steps, and τ is a property of the constraint and the statistic together. They cross at a tolerance of 0.194 standard deviations, where about one assignment in 396 is admissible — far tighter than any trial is designed at. And the walk does not remove the acceptance cost; it pays it once, hunting for somewhere to start.

Draws that repeat each other

A hunt costs 1/p evaluations per independent draw. A walk costs one per step and yields an effective draw every τ steps. Both are counted in the same unit, and the walk is dearer at every tolerance a trial is designed at.

joint · Reference A thin enough set is not one set. Every admissible set of 14 units this table can enumerate, by how much of the assignment space it admits and how many pieces it falls into under single swaps. A walk is uniform on the piece it starts in and never leaves it. The pieces are not fragments: at 522 admissible assignments the set splits into 3 halves of exactly 520 each, and every assignment's complement is in the other half — no sequence of admissible single swaps takes an assignment to its own mirror image. Two-swap proposals reconnect four of the six disconnected sets here — the two they do not are the thinnest, where a two-unit move rarely lands anywhere admissible either — which makes a bigger proposal a correctness repair rather than the speed dial it was measured as.

The walk that cannot cross

A thin enough admissible set is not one set. It splits into an assignment and its mirror image, no sequence of admissible single swaps joins them, and the walk that samples it is uniform on half the reference distribution for ever.

dict · Randomisation An overlap that depends on where it is read. Each pair's overlap on the doubled log-likelihood scale — the sum of the two searches' own quantiles less the joint search's quantile, as a share of the smaller — at five quantile levels, over 1200 draws under the first-order autoregression. two dictionaries of independent columns: -0.176 at 0.5, -0.000 at 0.75, 0.238 at 0.9, 0.320 at 0.95, 0.538 at 0.99; a break, and an independent column: -1.211 at 0.5, -0.406 at 0.75, -0.029 at 0.9, 0.205 at 0.95, 0.161 at 0.99; two dictionaries of step columns: -0.397 at 0.5, 0.145 at 0.75, 0.438 at 0.9, 0.541 at 0.95, 0.682 at 0.99; a break, and a step column it contains: 1.000 at 0.5, 1.000 at 0.75, 1.000 at 0.9, 1.000 at 0.95, 1.000 at 0.99; a break, and a whitening window: 0.512 at 0.5, 0.640 at 0.75, 0.716 at 0.9, 0.732 at 0.95, 0.754 at 0.99. Every pair but the containment overlaps more at the 95% point than at the median, the control included.

The overlap at the critical value

Two searches over independent noise columns are additive on average: the joint search finds what the two find separately, to within a fortieth of the smaller. At the point a test actually uses — the joint statistic's 95% quantile — the same pair overlaps by 0.320, and a rule that adds the two searches' own critical values rejects 1.4% of true nulls instead of 5%. Nothing about the searches causes it. Quantiles of a sum do not add, and on every pair in the field the overlap at the critical value is larger than the overlap the field measured.

apart · Criterion The overlap climbs and the interaction does not. The over-charge at each quantile level split into overlap — the two searches' own quantiles less the sequential run's — and interaction — the joint search's quantile less the sequential run's — for three pairs over 1200 draws. two independent dictionaries: overlap -0.40, 0.01, 1.55, 2.44, 5.72; interaction 0.07, 0.01, 0.11, 0.06, 0.00. two step dictionaries: overlap -0.73, 8.19, 22.53, 31.02, 47.75; interaction 4.87, 4.55, 4.90, 4.75, 1.10. a break and a window: overlap 17.88, 29.52, 43.01, 53.79, 71.61; interaction 1.57, 1.29, 1.19, 3.22, 2.75, at the 50%, 75%, 90%, 95% and 99% points.

The split at the critical value

Split the over-charge of two searches at the joint statistic's 95% point rather than at its mean, and the two components behave differently. The interaction — what only the joint search can reach — stays within two units of its average at every level up to the 95% point. The overlap climbs from nothing to most of the over-charge, on two searches over independent columns as much as on searches that share ground. At the critical value the split's overlap has stopped meaning shared ground: it is mostly the arithmetic of adding tails, and the identity that defines it hides that.

separate · Break point Four rules for a break and a column. How often each of four rules says something is there, for the pair of searches over a break and a column, under four truths, 400 draws each under a first-order autoregression at 0.8 with every threshold simulated on 1200 null draws. nothing there: joint, calibrated 6.3%, summed thresholds 6.3%, Bonferroni 6.3%, either, uncorrected 12.0%. a shift from row 60: joint, calibrated 65.3%, summed thresholds 64.0%, Bonferroni 55.0%, either, uncorrected 69.3%. a column enters: joint, calibrated 11.8%, summed thresholds 10.8%, Bonferroni 73.0%, either, uncorrected 82.5%. both: joint, calibrated 70.5%, summed thresholds 69.0%, Bonferroni 75.8%, either, uncorrected 84.8%. The first block is each rule's size.

The power a calibration buys

Charging two searches separately makes a joint test conservative, and calibrating the joint statistic on its own null repairs that. Against a real break, on the pair of a break search and a window search, the repair is worth 47 points of power — 62.0% against 14.5%. On the pair of a break search and a column search it is worth nothing, and worse: a real column is found by the calibrated joint test on 11.8% of samples and by a plain Bonferroni split on 73.0%, because a joint statistic takes its threshold from the noisier of its two searches.

apart · Criterion One order's interaction climbs under long memory. The break-and-window pair's interaction — the joint search's quantile less the sequential run's — at five quantile levels, in the field's order (break first, solid) and the other (window first, dashed), under three laws, 1200 draws each. first-order autoregression: break first 1.57, 1.29, 1.19, 3.22, 2.75; window first 0.98, 1.26, 1.53, 2.55, 2.14. five-period moving average: break first 2.00, 1.88, 2.29, 2.63, 0.60; window first 0.16, 0.21, 0.26, 0.29, 0.00. long memory: break first 0.53, 0.80, 1.05, 0.46, 1.35; window first 2.01, 1.62, 4.75, 6.07, 7.85, at the 50%, 75%, 90%, 95% and 99% points. Under two of the laws, and in the field's order under all three, the interaction stays within a few units of its median. Under long memory with the window searched first it climbs from 2.01 to 7.85, against an average of 1.99; the same order's averages under the other two laws are 0.94 and 0.17.

A tail the law gives the pair

Split the over-charge of two searches at their critical value and the interaction — the configurations only the joint search reaches — stays near its average while the overlap climbs. That held under one law. Under a five-period moving average and under long memory it holds for every pair in the order the field reads, to within three units. In the other order, one pair acquires a tail of its own: with the window searched first and the break second, the interaction under long memory climbs from 2.0 at the median to 7.9 at the 99th percentile, four times its average.

separate · Break point

Named alongside it

The objects these essays reach for when they reach for this one.

Monte CarloCovariate balanceReference distributionRerandomisationAcceptance rateLikelihood ratioRandomisation testChange pointCritical valueData snoopingSpecification searchSupremum statistic

All concepts