The design that has to be integers

Everything in this field so far has been about a design measure: a list of settings with weights that sum to one. It has an exact optimum, a unique one, and a theorem that certifies it.

It is also not a thing anybody can run. An experiment has a whole number of runs, and 0.1458 of an experiment at a corner is an instruction with no meaning. The gap between the object the theory is about and the object an experimenter performs is the subject of this essay, and it turns out to contain three separate surprises.

The obvious thing to do, and how far it gets #

Multiply each optimal weight by N, round to integers, and hand out any spare runs to the largest remainders. That is the apportionment rule that minimises total rounding error, and it is what anybody would try first.

At N = 13 the optimal weights — 0.1458 at each corner, 0.0802 at each edge midpoint, 0.0962 at the centre — multiply up to 1.895, 1.043 and 1.250. Round down and that is one run everywhere, nine in total, with four spare. The four largest remainders are the corners, so each corner gets a second run: eight runs on the corners, four on the edges, one at the centre.

That design reaches 99.77% of the optimal measure’s D value. It is also, it turns out, exactly the design a proper search returns.

So the shortcut works. That is the first thing to establish and it is why the second thing is worth saying.

Except when it does not #

At N = 7 the rounded design reaches 91.09% and the searched design reaches 94.54% — a gap of three and a half points of efficiency, which at that size is more than a whole run’s worth. At N = 20 the gap is smaller and still there: 98.99% against 99.40%.

At half the sizes in between, the two agree exactly. Across every size from seven to twenty runs they give the same design at seven of fourteen, and where they differ the search always wins — never once by accident in the other direction, over fourteen independent comparisons. The largest gap is the 3.5 points at seven runs; everywhere else it is under half a point.

Rounding is a good heuristic that is not the answer, and nothing about a single N says which case it is the answer in. An experimenter who rounded at thirteen and got the optimum has no way of knowing that the same procedure at seven would have cost them three and a half points.

The reason the shortcut fails is that rounding solves the wrong problem. It minimises the distance between the run counts and the ideal weights, and nobody wants the run counts to be close to the weights — they want the determinant to be large. Those are different objectives, and a design that is slightly further from the weights can have a larger determinant, because the determinant is not a linear function of the counts. The rounded design is optimal for a criterion nobody chose.

Adding a run can make the design worse #

The second surprise, and it is the one that reads as an error before it reads as a result.

Thirteen runs reach 99.77%. Fourteen reach 99.44%. Fifteen reach 98.70%. Sixteen reach 98.30%. Three consecutive additions, each of which makes the design less efficient than the one before.

Then it recovers: eighteen reaches 98.62% and twenty reaches 99.40%, and the curve goes on oscillating.

The units matter here or the result is nonsense. Efficiency is measured per run — that is what dividing X′X by N does, and it is the only way designs of different sizes can be compared at all. Fourteen runs give more total information than thirteen. What they give is less information per run, which means the fourteenth run bought less than the average of the thirteen before it.

The reason is arithmetic rather than statistical. The optimal weights are nine specific real numbers, and an N-run design approximates them with fractions whose denominator is N. Thirteen happens to divide into those weights nearly exactly: 2/13 = 0.1538 against a wanted 0.1458, 1/13 = 0.0769 against 0.0802. Fourteen does not do as well — 2/14 = 0.1429 is a good corner but the spare run has nowhere good to go. How close a design can get is a fact about how well N divides into a set of real numbers, and divisibility does not improve monotonically.

This site has this shape once already, and naming it is the point of putting the two together. More data is not monotone measures a Wald interval whose coverage falls from 93.8% at n = 19 to 81.9% at n = 20 — a larger sample covering worse. The mechanism there is the same as here: a discrete count landing against a continuous target, with the landing improving and worsening as the count steps through. Neither is a defect in a procedure. Both are what happens when something integer-valued has to approximate something real-valued, and in both cases the sensible-sounding advice — collect more, run more — is not reliably right.

The loss is the squared distance from the ideal weights #

The divisibility argument can be turned into arithmetic, and doing so makes the non-monotonic curve one expression rather than a list of surprises.

Measure how far an N-run design’s weights sit from the optimal measure’s, in total variation. The thirteen-run design puts 2/13 = 0.1538 at each corner against a wanted 0.1458, 1/13 = 0.0769 at each edge against 0.0802, and 1/13 at the centre against 0.0962 — a total deviation of 0.0645. The best fourteen-run arrangement has to put its spare run somewhere, and the cheapest place is the centre, which gives a total deviation of 0.0935.

Fourteen runs are 45% further from the ideal weights than thirteen. And the efficiencies lost are 0.23% and 0.56% — a ratio of 2.4 against the 2.1 that squaring the distance ratio predicts.

So the loss is about 0.55 times the squared total-variation distance, which is what a smooth maximum gives and is why the fourteenth run makes things worse: it does not merely fail to help, it forces the design further from a set of nine real numbers than thirteen runs were.

Two things follow that the curve alone does not say.

The criterion is extraordinarily flat. Thirteen runs sit 6.5% away from the ideal weights in total variation and lose a quarter of one per cent of the determinant — an insensitivity of nearly thirty to one. That is why 99.77% is reachable at all, and it is the same flatness the equivalence theorem’s tangency is a statement about: a function touching its bound has zero slope there.

And the curve is predictable without a search. The best achievable efficiency at N runs is one minus 0.55 times the squared distance from the weights to the nearest N-denominator lattice point, so an experimenter choosing between sizes can compute the shape of the oscillation from the optimal measure alone — which the measure itself supplies — rather than running twenty exchange searches at each size.

That is the useful residue of the whole essay. The rounding heuristic is optimal for a criterion nobody chose; the searched design is optimal for the right one; and the gap between them is second order in a distance the rounding heuristic is minimising to first order. The heuristic gets the first order right and the whole of what is left is second order, which is why it agrees at half the sizes and is never badly wrong except where a size cannot reach every setting at all.

The search has more than one answer #

The third surprise is about the algorithm rather than the answer.

Finding the best N-run design is not a convex problem. There is no equivalence theorem for it, no certificate, and no reason for a hill-climbing search to reach the same place from every start. The method used here is point exchange: start from N candidates chosen at random, then repeatedly try replacing each design point with each candidate and take whichever swap most improves the determinant, until no swap improves it.

That is a local search. It stops at a local optimum. And whether it stops at the optimum depends on where it began.

It is worth being clear about how brutal the method is, because its crudeness is the reason it is trustworthy at all. At each pass it considers every one of the N design points paired with every one of the 121 candidates — about sixteen hundred determinant evaluations per pass — and takes the best swap available. There is no gradient, no clever update, and no structure being exploited. The determinant is recomputed from scratch after every accepted swap rather than updated by the rank-one formula that would make it faster, because N is thirteen and p is six and a derivation whose correctness would need its own paragraph is not worth a millisecond in a figure drawn once per build.

What the method cannot do is see past a single swap. A design two swaps away from something better, with neither swap improving on its own, is a design the search will sit in. That is exactly the situation the near-ties at ten runs create, and it is why the number of starts rather than the number of passes is what fixes it.

At N = 10, 65% of twenty random starts reach the best design found; the other 35% stop somewhere else. At N = 11 it is 90%. At every other size from seven to twenty it is 100%.

So the unreliability is not a property of the algorithm alone — it is a property of the size being asked for. The sizes where the optimal weights divide cleanly have one answer that every start falls into, and the sizes where they do not have several near-ties that a search can get stuck between. That is not something a single run at a single N could reveal, and it is the reason this figure sweeps sizes rather than reporting a rate.

And what a bad start costs is almost nothing #

Here is where the honest measurement complicates the warning.

The received advice about exchange algorithms is to use many random starts because local optima are a real hazard. The first half of that is right. The second half, at least here, is not much of a hazard: the worst start at N = 10 produces a design 99.991% as efficient as the best, and at N = 11 99.847%.

Those are losses in the fourth decimal place. An experimenter who ran the search once, got the inferior local optimum, and never knew, has lost approximately nothing.

Which is precisely why nobody notices there is a second answer. A failure that costs a hundredth of a percent produces no symptom, generates no complaint, and never gets investigated. The multiplicity of answers is real, it is measurable, and its consequence is negligible — and reporting only the first of those three would be alarmism, while reporting only the third would be missing that the search is not deterministic in a way its output does not admit.

The general point is one this site keeps arriving at from different directions: an error’s size and an error’s visibility are unrelated. The stopping-rule field has errors that are enormous and invisible; this one has an error that is visible only to somebody looking for it and turns out not to matter. Both had to be measured to find out which kind they were.

No exact design can be certified #

There is a structural consequence of all this that is worth stating plainly, because it explains why this essay has no theorem in it where the previous two did.

The equivalence theorem certifies a design measure: it is D-optimal exactly when the largest prediction variance in the region equals p. The condition requires equality, and equality requires the freedom to put any real weight anywhere.

An N-run design has no such freedom, so it cannot satisfy the condition. The thirteen-run design’s largest prediction variance is 6.882 against p = 6, and it is the best thirteen-run design there is. The excess is not a defect to be fixed; it is the price of thirteen.

So the certificate that made the continuous problem tidy is unavailable exactly where an experimenter needs it. There is no way to know, from a design alone, that no better N-run design exists. What is available is the distance to the measure — 99.77% at thirteen runs — which bounds how much could possibly be gained by looking harder. That is weaker than a certificate and it is not nothing: an experimenter told their design is 99.77% efficient knows that no amount of further search can buy more than a quarter of a percent.

The same problem on a different region #

The three effects above are not artefacts of the square. Run the whole sweep on a circular region and the same three things happen, with different numbers: the searched design beats the rounded one at some sizes and equals it at others, the efficiency curve is not monotone, and the exchange search has more than one answer at some sizes.

What changes is the size of the rounding penalty. On the disc at thirteen runs the searched design reaches 0.9881 and the rounded one 0.9802 — a gap of nearly a point where on the square at the same size there was none. The reason is that the disc’s optimal measure has support on a circle rather than on nine grid points, so the weights are spread over more settings and there are more ways for thirteen integers to land badly.

What size to run #

The practical residue, since the numbers point somewhere.

Sizes that divide the weights well are worth preferring. Thirteen runs at 99.77% beats fourteen at 99.44%, sixteen at 98.30% and eighteen at 98.62%. If the budget allows anything between thirteen and eighteen, thirteen is the best of them per run, and it is also the cheapest. That is an unusual position to be in and it is worth checking for rather than assuming away.

Run the search from several starts anyway. It costs seconds, the cost of not doing it is small but not zero, and the sizes where it matters are not predictable in advance without doing the sweep. The same argument applies to the seeded-generator discipline this site runs on: a procedure whose answer depends on a random start has a seed, the seed is part of the result, and a design reported without one cannot be reproduced.

And do not round the weights and stop. It is right most of the time and wrong by three and a half points at seven runs, which is the size range where an experiment can least afford it.

The check, and the refusal that makes it mean something #

Three claims are gated in this field’s library and each is a comparison across sizes, so none can live in a figure. The efficiency falls from thirteen runs to fourteen and again to sixteen, asserted as two separate inequalities so that one unlucky size cannot carry it. The search’s hit rate is below 1 at ten runs and exactly 1 at thirteen, on the same seeds and the same candidate set — the second half being what makes the first a statement about the size rather than about the algorithm. And the rounded design is strictly worse at seven runs and exactly equal at thirteen, again both halves, because the equality is what makes the inequality surprising.

The refusal here is a quiet one and it is worth naming. A design’s efficiency is meaningless without the optimum to measure it against, and the optimum is found by a search over a grid — so every number in this essay could in principle be an artefact of that grid rather than a fact. assertTheGridIsFineEnough refines the candidate set from 121 points to 441 and requires the optimal D value to move by less than a tenth of a percent and the support to stay on the same nine settings. It does: 0.474594 at both. Had the refinement moved the reference, every efficiency in this field would have been a number about the implementation.