Where the gain is, and where the decision is

At twelve units a walk over the admissible assignments is nearly twice as cheap at three swaps as at one, and it does not matter, because at twelve units a hunt costs 2.25 evaluations per draw and no walk is competitive with that.

The question the gain was raised for is the comparison at trial scale, where the admissible set cannot be enumerated: the walk against the hunt, which crosses at a tolerance of about a fifth of a standard deviation. A larger proposal makes the walk cheaper. Does it move the crossing?

It barely moves it at all, and the reason is worth more than the number.

Both costs in one unit #

The only comparison that means anything is in a unit both methods have, and the unit is assignments evaluated per usable draw.

A rejection sampler shuffles an assignment, computes its imbalance, and keeps it if it is admissible: 1/p evaluations per independent draw, where p is the share of assignments the rule admits. A chain evaluates one proposed assignment per step and produces one effectively-independent draw every τ steps: τ evaluations per usable draw. Both are counted here rather than taken from a closed form, and the chain also pays 1/p once, for the starting point, which is the part of the accounting easiest to leave out.

The gain is real and it is in the wrong place #

At the loosest tolerance the larger proposal is worth a great deal. One swap costs 105.69 evaluations per usable draw and eight swaps cost 18.71 — a factor of 5.65. At a tolerance of 0.7 it is 230.22 against 51.41, a factor of 4.48. At 0.35 it is 326.02 against 162.31, a factor of 2.01.

At 0.18 it is 315.47 against 315.77. The factor is one.

The mechanism is the acceptance rate, which does exactly what a bigger step should make it do. At a tolerance of 1.2 an eight-swap proposal is accepted 69.6% of the time; at 0.7, 38.4%; at 0.35, 10.6%; at 0.18, 1.8%. A proposal accepted once in fifty-six moves the chain about as far per evaluation as a small proposal accepted once in four, whatever its size — and the product of step size and acceptance is what mixing is.

So the regime where a larger proposal helps and the regime where the comparison is decided do not overlap. At a tolerance of 1.2 the walk at eight swaps costs 18.71 and a hunt costs 2.2, so the walk loses by a factor of eight after a factor of six of improvement. At 0.18 the walk wins, and the improvement is zero.

The middle of the sweep, where both statements are true at once #

The two tolerances between the ends are where the argument is easiest to see, because both effects are present and neither has finished.

At a tolerance of 0.7 about one assignment in eight is admissible, a hunt costs 7.6 evaluations per draw, and the walk costs 230.22 at one swap and 51.41 at eight. The larger proposal has taken a factor of thirty off the gap and the gap is still a factor of seven. At 0.35 one assignment in forty-six is admissible, the hunt costs 45.8, and the walk costs 326.02 and 162.31 — the gap is down to three and a half, and the proposal size is now worth only a factor of two.

Read across those two columns, the hunt’s cost has risen by a factor of six and the best walk’s has risen by a factor of three. That is the whole race: the hunt is losing ground faster than the walk is, so they meet eventually, and the proposal size is a one-off improvement to a curve that is nearly flat rather than a change to its slope.

The crossing, four times #

Interpolating each proposal size’s cost against the hunt’s gives where the two methods cost the same:

• one swap: 0.190
• two swaps: 0.183
• four swaps: 0.181
• eight swaps: 0.195

The whole family crosses inside a band of about two hundredths of a standard deviation, and the ordering is not even monotone — four swaps crosses at the tightest tolerance and eight at the loosest, because by then the eight-swap chain’s acceptance has collapsed below the four-swap chain’s usefulness.

For a design decision this is a clean answer: the tolerance at which a walk becomes worth using is about a fifth of a standard deviation whatever the proposal is, which is where roughly one assignment in four hundred is admissible. The proposal size is not a lever on that boundary.

Why the crossing has to be immovable #

The result is negative and the reason for it is arithmetic rather than a property of these particular numbers, which is what makes it worth stating in general.

The two costs are τ and 1/p, so the crossing is at $1/p = \tau$. At twelve units the two chains have τ of 7.30 and 3.97, so the crossing sits where the admitted share is 13.7% and 25.2% respectively — a chain nearly twice as cheap crosses at a share nearly twice as large.

But the crossing is quoted as a tolerance, and the admitted share falls like the tolerance raised to the number of balancing constraints: $p \propto a^k$. So doubling the share the crossing sits at moves the tolerance by a factor of $2^{1/k}$, which is 1.26 at three constraints and 1.19 at four.

A chain twice as cheap buys about twenty per cent of tolerance.

Run backwards, the same expression says what it would take to move the crossing anywhere interesting: halving the crossing tolerance needs τ improved by $2^k$ — a factor of eight to sixteen.

Nothing in the family of proposals can do that. Going from one swap to three is the whole of the available range and it is worth a factor of 1.84, so the crossing tolerance moves by nineteen to twenty-six per cent and no arrangement of the same idea moves it further.

The crossing is exponential in the tolerance and the lever is linear in the cost, and that mismatch is the finding rather than any of the numbers it is computed from.

What a chain is paying for at a tight tolerance #

It is worth looking at what the walk is actually doing at a tolerance of 0.18, because the numbers describe a chain in trouble in a specific way.

One assignment in three hundred and fifty-seven is admissible. The one-swap chain accepts 26.3% of its proposals, which sounds healthy — but accepted here means the swap landed on another admissible assignment, and an admissible assignment two units away from an admissible assignment is a near neighbour in exactly the sense that makes a draw useless: the statistic barely changes. So the chain moves often and goes nowhere, and its autocorrelation time is 315.

The eight-swap chain has the opposite problem. When it moves it goes somewhere, and it moves once in fifty-six proposals. Its autocorrelation time is 316.

The two failures are different and cost the same, which is what an optimum in the middle would normally look like — except that the middle is worse: two swaps cost 345.03 and four cost 352.71. The curve across the proposal sizes at this tolerance is essentially flat with a slight hump, and none of the four is materially better than any other. That is a stronger statement than the optimum has moved: at the tolerance where the decision is made, there is no useful optimum in the proposal size at all.

Which is a negative result, and worth the same as a positive one #

The question was the product has an optimum, and nothing here says which way the cost comparison moves. The answer is that it moves by about a hundredth, on a quantity that runs from 2 to 357 across the same sweep.

That is worth recording for the reason every ruled-out explanation in this collection is. It closes a line of enquiry rather than opening one: a practitioner deciding between a hunt and a walk does not need to think about the proposal size when making that decision, and one who has already decided on a walk at a loose tolerance should think about very little else.

It also says something about where the walk’s cost comes from. If the proposal size moved the crossing, the chain’s expense at tight tolerances would be a step-size problem, curable by proposing better. It does not, so it is not: at a tight tolerance the admissible set is a thin, sparse region of the assignment space, and a chain inside it is refused almost everywhere it tries to go. The cost is the geometry of the set, not the design of the proposal.

Why the hunt’s cost is the only thing that moves #

One more reading of the sweep, because the asymmetry in the figure is the argument in one picture.

The hunt’s cost is 1/p, and p is the probability that a shuffled assignment satisfies every constraint. That falls off a cliff as the tolerance tightens — 0.451, 0.132, 0.0219, 0.0028 across the four columns — because it is approximately the volume of a shrinking box in a space of standardised imbalances, and volume in three dimensions falls like the cube of a side.

The walk’s cost does not have that structure. A chain does not need to find an admissible assignment, it starts at one, and what it pays is the correlation between successive draws. That correlation is bounded above by one however thin the set gets, so τ is bounded by the number of steps between genuinely different assignments, and the set being thin makes those steps rarer rather than impossible.

So one method’s cost is a volume and the other’s is a mixing time, and the crossing is where a volume passes a mixing time on the way down. A change that makes the mixing time better by a factor of six moves that crossing by the sixth root of six in tolerance — which, on a cost that spans two orders of magnitude across the sweep, is the two hundredths measured. The band is not a coincidence and it is not an artefact of the draw count; it is what a lever on the flat curve does to a crossing with a steep one.

What the numbers at two hundred units are and are not #

Every figure here is a run rather than a matrix, and the accuracy should be read accordingly.

The autocorrelation times are estimated from eight thousand steps by the initial-positive-sequence rule, and at τ ≈ 320 that is twenty-five effectively independent draws — so those entries carry something like a fifth of their own value in error. The 315.47 against 315.77 at the tightest tolerance should be read as the same to within what this measurement can resolve, not as a difference of three tenths.

The acceptance rates are measured on the same runs and are precise; the hunt’s cost is counted over twenty thousand shuffled assignments per tolerance and is precise below about one in a thousand. So the crossings inherit the autocorrelation times’ error, which is why they are quoted to three decimal places and described as a band.

The comparison at twelve units, where everything is exact, is the essay before this one, and the two agree about the mechanism: acceptance falls with the proposal, the autocorrelation time falls with it, and the cost is τ rather than one over the acceptance rate. What the exact calculation cannot show is the collapse at a tight tolerance, because at twelve units there is no tolerance tight enough — the smallest admissible set an enumeration reaches still holds nearly half the assignments.

How a lever gets chosen, and why this one was not one #

There is a pattern behind this result that is worth naming, because the measurement that produced it is the sort nobody does and the reasoning that skips it is the sort everybody does.

A gain gets measured where it is easy to measure. At a loose tolerance the admissible set is fat, the acceptance rate is high, chains of every proposal size run cheaply, and the factor of 5.65 at a tolerance of 1.2 falls out of a short experiment. A decision gets made where the problem is hard — at a tight tolerance, where the admissible set is thin, where a hunt is expensive enough that a walk is worth considering at all. Those are not the same place, and nothing in the shape of the gain warns that it will not survive the journey between them.

It does not survive. By a tolerance of 0.35 eight swaps are worth 2.01, and by 0.18 they are worth 1.00 — no gain, at all, at the setting where the walk exists to help. The mechanism is not subtle once looked at: a larger exchange moves further, and moving further from a thin admissible set means landing outside it. The acceptance rate at that tolerance has fallen to 1.8%, and a proposal refused ninety-eight times in a hundred is a proposal that does not move regardless of how far it would have gone.

So the crossing sits where it sits for a reason that has nothing to do with the proposal. One, two, four and eight swaps cross a hunt at 0.190, 0.183, 0.181 and 0.195 — a band two hundredths wide, on a family whose costs span 2 to 357. The thing that decides whether to walk or to hunt is the tolerance and the size of the admissible set it leaves, and the proposal size is a parameter of the walk that the decision is nearly blind to.

That is an unwelcome answer to publish next to an essay that measured the gain carefully and found it real. Both are true. The gain is real, it is a genuine fact about mixing, and it is worth having where it applies. It is simply not a lever on the question the field was built to answer, and the only way to find that out was to measure the same family at the tolerance where the question is live rather than at the one where the measurement is convenient.

What is claimed here, and what is not #

This essay takes whether a larger proposal moves the choice between a walk and a hunt. The claims are that eight swaps are worth a factor of 5.65 at a tolerance of 1.2 and a factor of 1.00 at 0.18; that the acceptance rate at eight swaps falls from 69.6% to 1.8% across that range, which is why; and that the crossing between the two methods sits between 0.181 and 0.195 for every proposal size measured, so the proposal is not a lever on the decision.

What stays out and is named as a decision: the number of balancing functions. Every run here uses three, and the admissible set’s thinness is as much a function of that as of the tolerance — a rule constrained on six functions at a loose tolerance has a set as thin as one constrained on three at a tight one. Whether the crossing moves with the basis size rather than with the tolerance is the obvious next sweep and is not made here.

The boundary against the exact essay is that it establishes the mechanism where everything can be computed, and this one asks whether the mechanism reaches the decision.

The checks, and the refusals that make them mean something #

Two claims are gated. The gain from a larger proposal is required to be more than a factor of three at the loosest tolerance and to have gone — within twenty per cent — by the tightest, which is the shape the whole argument is about. And every proposal size is required to have a crossing at all, since a family in which some member never crossed would mean the two costs were not comparable in the unit they are being compared in.

The refusal is the one this field carries throughout, and it is sharpest here: a proposal size chosen from its acceptance rate is rejected. At a tolerance of 1.2 the one-swap chain accepts 87.7% of its proposals and costs 5.65 times as much per usable draw as the eight-swap chain that accepts 69.6%.