A price paid only when asked
A landmark search on a weighted maze stores the distances from a few chosen cells, its landmarks, to every other cell, and uses them to bound how far a query still has to go. On a maze of 2,500 cells the four corners cost nothing to keep, and starting from the corners found that a watch does best to begin there. The candidates near where the queries end built a watch that does better while traffic stays put: every thousand queries it prices its placement and four candidates near recent destinations on a sample of the last twenty queries, and refits one landmark when the saving pays for the refit. When the destination jumps every thousand queries, no refit has time to pay, and the plain corners win.
So the watch needs a switch, and a string of essays has refined one. A switch that counts the jumps read the traffic’s pace from the spacing of its last few stretch ends, moments when the destination has moved more than ten cells from where its stretch began. A silence that overrules the count let a long quiet stretch overrule a stale reading, a gap between off and on gave switching off its own threshold, and a margin the count sets itself returned the watch to the corners only when the count’s reading plus half a standard error was under 1,600 queries. The count asks and the price answers added money to the decision: the count proposes returning to the corners, and the watch’s last price of the corners against its placement must agree. It cost a cell or two a query on every stream, and the reason was in its accounts. The tolerance did nothing, the price agreed with the count three times in four, and the pricing search was paid at every look, including on streams where the count never asked.
Its closing section proposed paying only when asked. At the moment of a proposal the watch’s sample is in hand, and one extra search of it settles whether the corners would be dearer; at every other look the switch is the margin rule. It also proposed a new kind of stream, on which the destination drifts a step at a time between jumps, so that the count, which reads drift’s stretch ends as pace, would make misreadings for the price to refuse. The prediction was that on the six jump streams the lazy confirmation costs within a fifth of a cell of the margin rule, and that on the drifting stream it beats the margin rule by more than a cell. The named risk was the price’s timing: at the moment of a proposal the sample might hold too few queries to the new destination to show the corners as cheaper, and the price would refuse correct proposals.
The switch, as built
The lazy switch is the margin rule until the count proposes. Then, if the watch’s placement is not already the corners, it searches the last twenty queries with the corners’ landmarks — one charged search of the sample — and compares that with what those twenty queries actually cost under the placement, which is already known because they were served. If the corners would have cost at most the tolerance more, in cells a query, the proposal is accepted and the watch goes back to the corners; otherwise it keeps watching. A proposal made while the placement is the corners is accepted at a price of nought.
The streams are the earlier essays’ four mazes and 30,000 queries a stream: one jump of the destination to a random cell every 1,000, 2,500, 5,000 or 10,000 queries on average, and two that change pace halfway. The drifting streams add, before every query, a chance of one in a hundred that the destination steps to a neighbouring cell — one in about thirty-three on the fastest — on top of jumps every 1,000, 2,500 or 5,000 queries. Every switch is charged at the better of two watch windows, and every cell any of them searches is charged to the stream.
Free on the jump streams
Priced only when the count asks, the confirmation is within a fifth of a cell of the margin rule on four of the six jump streams and 0.6 cells dearer at worst, against 0.8 to 2.1 for the confirmation that priced at every look. On the two slow streams and the slowing one, the lazy switch is the margin rule to a tenth of a cell, and at one jump in 2,500 it is a tenth above. The confirmation the earlier essay paid for everywhere is now almost free.
The two streams where it still costs something are the two where the pace is fast at some point, one jump in 1,000 and the stream that speeds up to it. There the count asks most, and the price sometimes refuses: a quarter of a refusal a stream on each. A refused proposal leaves the watch looking when the corners would have been right, which at that pace costs about as much as the earlier essay’s confirmation did. The half cell is not the price of the search; it is the price of the refusals.
So the first half of the prediction holds on four streams and misses on two, by four tenths of a cell. That is close enough to say the price has been made cheap. Whether it has been made useful is the other half.
What the searching costs now
What the confirmation searches falls from 0.42–2.10 cells a query, priced at every look, to at most 0.10 priced only when the count asks — it asks between none and 1.8 times a stream. Thirty looks a stream become one or two prices, and each price is one search of twenty queries. The slow streams make the point most plainly: at one jump in 10,000 the count never proposes, so the lazy switch searches nothing, where the confirmation at every look paid a full cell a query to confirm proposals that never came.
The earlier essay’s largest cost was at one jump in 5,000, 2.1 cells a query, because at that pace the watch is away from the corners most of the time and every look away from them paid for a price. Asked a quarter of a time a stream, the lazy price there costs a hundredth.
That accounting is the whole of what the proposal could win on the jump streams. The prices it reads are the same prices the earlier switch read at the moment of a proposal, so they confirm and refuse much as before. It has removed the cost of the instrument without changing what the instrument says.
The dial still does nothing
The tolerance still does nothing: from nought to thirty cells a query the lazy switch’s cost moves by at most 0.3 cells on any stream, because the prices it reads at a proposal are far from every tolerance. At one jump in 1,000 it costs 144.7 cells a query at tolerances of nought, three and ten and 144.4 at thirty, against the margin rule’s 144.1; at one in 2,500, 117.9 at every tolerance. On the drifting streams, where the tolerance was meant to separate the count’s misreadings from its correct proposals, it is as flat: 119.9 at nought and 119.8 from three up at one jump in 2,500, and 129.2 to 129.1 when the drift is fast.
A tolerance can only matter for prices that fall near it. The earlier essay found that the prices read at proposals were mostly tens of cells from nought in one direction or the other, and nothing in reading them lazily changes that, since the same twenty queries are priced at the same moment. The question the flat costs leave is why the prices on drifting traffic should be so far to the side of agreement, and the next two plates answer it.
On drifting traffic, nothing refused
On traffic that drifts between jumps the price refuses nothing the count gets wrong: at one jump in 2,500 with a step every hundred queries the lazy switch costs 119.8 cells a query against the margin rule’s 119.7, not a cell under it, and both lose 4.3 to the watch left on. The drifting stream does what it was built to do. The count reads drift’s stretch ends as pace and proposes the corners when the watch should keep watching, and the margin rule obeys it and pays 4.3 cells a query for it. The price was meant to refuse those proposals, and it lets them through.
The other drifting streams fill in the picture. At jumps every 1,000, drift or not, the corners are right and the watch is 145.4, and both switches get most of the way there. At jumps every 5,000 with drift, the switches are a little better than the watch left on. With fast drift, every policy lies within two cells, and the lazy switch is 0.7 above the margin rule. Nowhere does the confirmation beat the rule it confirms.
That is the second half of the prediction failing, and it fails the opposite way from the risk the proposal named. The risk was that the price would refuse the count’s correct proposals because the sample held too little of the new destination. It does not refuse the incorrect ones.
Why the price agrees
At the moment the count proposes, the corners usually look far cheaper than the placement: 27 of 35 prices fall at or under three cells a query and 13 of them more than ten cells under nought, because a proposal follows a move of the destination and the placement being priced was fitted to where the traffic had been. On the drifting stream at 2,500 the prices are −43.5, −51.6, −59.5 and −125.7: the corners, by the evidence of the last twenty queries, were forty to a hundred and twenty cells a query cheaper than what the watch was using.
That evidence is true, and it is the wrong question. The count proposes when a stretch has just ended, which means the destination has just moved more than ten cells. The watch’s placement was fitted to the old destination, so on the twenty queries since the move it is bad, often worse than the corners. But the watch is about to refit: at its next look it will price candidates near the new destination and replace its worst landmark. The comparison that would tell the switch whether to stop watching is the corners against the placement the watch is about to have, not against the one it is about to discard.
So the price, read at the moment of a proposal, is biased toward agreement by construction. It compares the corners with a placement at its stalest, at exactly the moment staleness is greatest. On jump streams that bias does little harm, since after a jump the corners often are the better choice for a while. On drifting streams it is the whole failure: drift moves the destination a few cells, the count calls it a stretch end, the old placement looks stale on the newest queries, and the price agrees to give up a watch that would have refitted in a few hundred queries and gone on winning.
Asked rarely, refused more rarely
The count asks a few times a stream and the lazy price almost always agrees: 1.8 refusals in 12.0 proposals a stream summed over ten streams, 1.3 of 6.8 on the four that drift, where the refusals were meant to be. On the drifting stream at 2,500, where the count’s misreadings cost 4.3 cells a query, the price refused none of its 1.5 proposals a stream.
The only stream with a refusal rate worth the name is the fast drift, one in two and a half. There the destination moves a step every thirty-three queries, the placement is stale at every moment, and the comparison is noisier, so it sometimes lands on the far side of the tolerance. The refusals cost a little there too: the lazy switch is 0.7 above the margin rule on that stream.
Twelve proposals a stream over ten streams is also a statement about how much a confirmation could ever change. If every refusal were right, each would be worth a window or two of watching. The margin rule’s whole loss on the drifting stream, 4.3 cells a query, comes from one and a half proposals a stream that kept the corners for about a seventh of it, and the price would have had to refuse nearly all of them to recover it.
A second reading taken at the wrong moment
The proposal asked whether a second reading pays only where it can disagree with the first, and whether a stream exists on which it does. The drifting stream is such a stream: there the count is wrong and the money, read properly, would say so. But the price did not disagree there, because it was read at the moment its own subject was weakest. The count and the price are not two independent witnesses. The count fires when the destination moves, and the price, read in the next breath, measures the cost of that same move to a placement that has not yet answered it.
The general shape recurs in this strand. A watch that switches itself off priced the corners at every look and found the price too noisy to act on alone. The count asks and the price answers made the price a confirmation and found it agreed with the count three times in four. Reading it lazily makes it cheap and shows why it agrees: two readings triggered by the same event share the event’s bias. A confirmation is worth having only when it measures something the first reading cannot see, and the stale placement’s cost on the newest queries is something the count already implies.
There is also a lesson about cost accounting. Half the earlier essay’s loss was the price of pricing, and that half is gone. The remaining half on the fast streams is the price of refusals that were wrong, and on the drifting streams the margin rule’s own loss stands untouched. Making a check cheaper is worth doing, and it does not make the check correct.
What the streams do not settle
One drift rate, mostly. The drifting streams step the destination once in a hundred queries, and one stream once in thirty-three. Slower drift produces fewer stretch ends and fewer misreadings, and the margin rule’s loss would shrink with them.
The sample is twenty queries. The price is read on the last twenty queries, all of which follow the move that triggered the proposal when the move was recent. A longer sample would hold queries to the old destination too and price the placement less harshly, but it would also lag a real jump.
Four maps. Proposals are rare, one or two a stream, so the plates rest on a few dozen prices in all. The direction of the bias is plain in them; its size is not well measured.
Still open: the corners against the refit
The price agreed because it compared the corners with a placement about to be replaced. At the moment of a proposal the watch can price the replacement as well: the same search it makes at every look, four candidates near the new destination standing in for its worst landmark, gives the cost of the placement it would refit to. A confirmation that compared the corners with the best of those candidates would ask whether stopping is better than the refit, which is the decision the switch is actually making.
The measurement that follows prices, at each proposal, the corners against the best refitted placement on the same twenty queries — four candidate searches and one of the corners, charged — and refuses the proposal when the refit is cheaper by more than the tolerance. It runs on every jump stream and every drifting stream. The prediction is that on the drifting stream at 2,500 it refuses most proposals and comes within a cell of the watch left on, 115.4, while costing under half a cell more than the margin rule on the jump streams. It could fail at the fast pace: when the destination jumps every thousand queries, a refit near the new destination also looks good on twenty queries to it, so the price would refuse the proposals that are right and lose the corners’ advantage there. The question is whether any price read on the queries after a move can tell a destination that will stay from one that will not, or whether that is a fact about the future that only the count’s history can guess.
Named alongside this one
Essays reaching for the same objects. Nobody chose these; they are what the concept index makes visible.
- A switch that hears the traffic stop landmark · measured count · query distribution · regime · shortest path · stopping rule
- A placement after the traffic moved landmark · query distribution · regime · shortest path
- A refit that changes one landmark landmark · query distribution · regime · shortest path
- A horizon the stream can supply landmark · query distribution · shortest path
- A refit priced before it is made landmark · query distribution · shortest path
- A watch that looks less landmark · query distribution · shortest path
The objects this essay names
Each one links to every other essay that touches it.
LandmarkMeasured countQuery distributionRegimeShortest pathStopping rule