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 14 essays across 7 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 rung 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

Named alongside it

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

Covariate balanceMonte CarloReference distributionRerandomisationAcceptance rateRandomisation testBasis functionsImbalanceMarkov chain Monte CarloAssignment mechanismBurn-inClosed form

All concepts