A gap between off and on

A landmark search on a weighted maze of 2,500 cells runs fastest when its landmarks sit near where the queries end, and starting from the corners found that four landmarks at the corners are a placement that never has to be maintained. A watch can do better on traffic that settles: every window of queries it looks for a landmark near the recent destinations, among the candidates near where the queries end, and refits when the saving pays. On traffic whose destination jumps every thousand queries, a watch that looks less found the looking costs more than it saves, and the corners are cheaper.

So the watch needs a switch, and a switch that counts the jumps reads the traffic’s pace from its last $k$ stretch ends — the moments the destination has moved more than ten cells from where the current stretch began — and keeps the corners while their mean spacing reads under 1,600 queries. A count cannot hear the stretch ends stop, so a silence that overrules the count let an open spacing of 1,600 queries since the last stretch end overrule it outright. That switch heard a slowing within a window at every count, and on traffic that speeds up it was the cheapest switch measured.

Its closing section noticed what the override had done to the count. Switching the watch on is now the silence’s job; the count only decides when to switch it off, and a count that only has to decide that the traffic is fast need not use the same threshold the silence uses to decide it is slow. A switch could keep the corners only while the count reads well under 1,600, say under 1,200, and turn the watch on when the silence reaches 1,600, as now: two thresholds with a gap between them, so that the moderate pace, whose bunched stretch ends often read just under 1,600, no longer switches the watch off. The prediction was that at one jump in 2,500, on three stretch ends, an off threshold of 1,200 would keep the corners less than 5% of the time and come within a cell of the watch’s 116.4 cells a query, while keeping the override’s results on the streams that slow and speed up to within a cell. It named the risk at the fast pace, where stretch ends come every 1,121 queries on average and a reading of three must fall under 1,200 to switch the watch off at all.

Two thresholds #

The mazes, streams, landmarks and charges are the earlier essays’: four maps, 30,000 queries a stream, cells expanded by every search plus every cell the watch spends looking and refitting, divided by the queries; each switch is charged at the better of two watch windows, a thousand queries or two thousand. Every window, the switch reads the pace: the mean spacing of the last $k$ stretch ends, or the open spacing since the last stretch end once that alone has reached 1,600.

What changes is which threshold that reading is compared with. While the watch is on, the switch returns to the corners only if the reading is under the off threshold $O$. While the corners are kept, it stays with them until the reading reaches 1,600, which happens either because the count has slowed or because the silence has overruled it. Off thresholds of 1,000, 1,200 and 1,400 queries were run, and 1,600, which is the override switch exactly, on three and five stretch ends.

A gap that pays at one pace #

A second, lower threshold for switching the watch off saves 3.5 cells a query at one jump in 2,500 — 117.8 on three stretch ends with the corners kept only under 1,200, against the override’s 121.3 and the watch’s 116.4 — costs 1.7 at one jump in 1,000, and changes nothing from one in 5,000. At the moderate pace the gap does what the proposal meant: it stops the count switching the watch off on bunched stretch ends that do not mean fast traffic, and the switch’s cost falls most of the way from the override’s to the watch’s. At one jump in 5,000 every switch on three stretch ends costs 97.5 cells a query, below the watch’s 98.1, and at one in 10,000 every switch costs exactly the watch’s 80.2, since no reading ever falls under 1,600 there.

At the fast pace the gap costs what the proposal feared. A thousand queries a stretch is the pace at which the corners are right — they cost 142.7 cells a query against the watch’s 150.7 — and the override’s switch is already near them, at 142.6. With an off threshold of 1,200 the switch keeps the corners 41% of the time rather than 47%, because three stretch ends must now average under 1,200 before it will return to them, and it pays the watch’s looking for the difference.

Where the gap begins to matter #

At one jump in 2,500 the gap matters only once the off threshold falls under 1,400: on three stretch ends the switch costs 121.3 cells a query with no gap and at 1,400, 117.8 at 1,200 and 118.2 at 1,000, keeping the corners 13% of the time; on five it costs 118.2 to 118.3 at every threshold and keeps them 5% of the time at 1,000. On three stretch ends an off threshold of 1,400 makes the same choices as 1,600: the readings that switched the watch off wrongly at this pace lie under 1,400, so a threshold has to reach below them to stop them. At 1,200 it does, and the cost falls by 3.5 cells. At 1,000 it falls a little less, 3.1, because the switch now also refuses some stretches of genuinely fast jumps.

The plate’s lower line is the surprise. On five stretch ends the override alone already costs 118.2 at this pace, as little as the best gap on three, and no gap moves it. A mean of five spacings is less often fooled by a bunch of stretch ends than a mean of three, so the switch on five rarely switches the watch off wrongly, and a gap has little to prevent. The gap does lower the time spent at the corners on five ends, from 12% to 5% at an off threshold of 1,000 — the proposal’s 5%, on the count it was not proposed for — but those are hours of corners that cost about what the watch costs, and removing them saves nothing.

So the prediction met its number on the wrong count and missed it on the right one. Three stretch ends with an off threshold of 1,200 keep the corners 13% of the time, two and a half times the 5% predicted, and come within 1.4 cells of the watch, not within one.

Why the moderate pace is where it pays #

The moderate pace is the one the earlier essays kept returning to because it sits nearest the switching point. A jump every 2,500 queries makes stretch ends whose mean spacing is well over 1,600, but not by so much that three of them cannot average under it: two jumps that land close together, or a walk of queries that wanders ten cells inside one stretch and counts as a stretch end of its own, pull a three-spacing mean down for a window or two. It happens often enough that the override’s switch spends 15% of the stream at the corners, which cost 126.8 cells a query here against the watch’s 116.4 — the same misreading a switch that hears the traffic stop found in the other direction, a count reading its own recent history as the traffic’s.

Each of those spells is short and each is expensive. The switch returns to the corners on a low reading, discards the landmarks the watch had fitted to the current destination, and then waits until the silence or a slower count brings the watch back, which must then refit before it saves anything — the cost a refit priced before it is made put on every refit. The gap removes the spells caused by readings between 1,200 and 1,400 and leaves the ones under 1,200, and the corners’ share falls only from 15% to 13% while the cost falls by 3.5 cells. The likeliest reading, which the plates do not separate, is that the spells it removes are the ones that interrupted a well-fitted watch, and that those are the dearest.

The pace at which the gap costs #

At one jump in 1,000, where the corners are the right placement, a gap costs what it saves elsewhere: on three stretch ends 144.3 cells a query at an off threshold of 1,200 against 142.6 with none, the corners kept 41% of the time rather than 47%; the corners alone cost 142.7 and the watch alone 150.7. On five stretch ends the cost is larger, 141.7 with no gap and 144.0 to 144.3 with one, because five fast spacings average close to the true 1,121 and seldom fall under 1,200, so the switch returns to the corners late after every lull.

The two paces pull the off threshold in opposite directions. At one jump in 2,500 it should be low, to ignore bunched stretch ends; at one in 1,000 it should be high, to return to the corners quickly once the traffic is fast again. A single number cannot be both, and the best single number depends on which pace a stream spends its time at. Over the four steady paces on three stretch ends, 1,200 saves 3.5 cells at one pace and costs 1.7 at another, and on five stretch ends every gap only costs.

Streams that change pace #

On the streams that change pace the gap changes almost nothing: slowing, three stretch ends cost 124.3 cells a query with the corners kept only under 1,200 and 124.5 with the override alone; speeding up, 118.9 and 119.3 — the gap keeps the override’s gains on both, within half a cell. That half of the prediction holds. The override’s gains on these streams came from the silence, which switches the watch on promptly when the traffic slows and is untouched by the off threshold. On the stream that speeds up, the gapped switch on three ends spends 42% of the fast second half at the corners against the override’s 40%, for reasons the plates do not separate, and the net is two fifths of a cell in the gap’s favour.

On five stretch ends the stream that speeds up is where the gap costs, 120.2 under 1,000 against 119.3 with none: the fast second half is the fast pace of the earlier plate, and five spacings take long to fall under 1,000.

Drift #

On drifting traffic, where a stretch end is a walk crossing ten cells, the gap moves the switch by nothing at any rate: every switch costs exactly what the watch alone costs, 107.4, 120.7, 108.6 and 123.7 cells a query at drifts of 0.001 to 0.03. A drifting destination makes stretch ends only when its walk has carried it ten cells from where the stretch began, which at a step every hundred queries takes thousands of queries, and no count of such spacings ever reads under 1,600. The switch never leaves the watch, and the watch is right: the corners cost 139 to 153 cells a query on these streams. The off threshold is never consulted.

One count wants two numbers #

The proposal asked whether a switch needs the same threshold in both directions, and the plates answer for each count separately. On three stretch ends the two jobs do want two numbers: the count is noisy enough to be fooled by bunched stretch ends at a moderate pace, and a lower off threshold catches exactly those. On five, they want one: the count is steady enough that the override’s single threshold already makes few wrong switches, and a lower one only delays the right ones. A three-end count with a gap costs 117.8 at the moderate pace and 144.3 at the fast one; a five-end count without one costs 118.2 and 141.7. The five-end count with no gap is as good at the moderate pace and better at the fast one.

That points at what the gap really is. A threshold set below the switching point by a fixed margin protects against a reading that is wrong by about that margin, and how wrong a mean of $k$ spacings can be depends on $k$. A watch that switches itself off priced the watch against the corners over its last $k$ looks for the same reason: one look’s difference was too noisy to act on. If the spacings are about as spread as their mean, as roughly memoryless traffic makes them, a mean of three is uncertain by more than half its value, a mean of five by under half, and a mean of ten by under a third. A margin that suits the first is too wide for the second, and the plates show exactly that.

What the plates assume #

Four maps and one stream each. Every cost is a mean over four mazes, each with one stream of 30,000 queries per setting. The 3.5 cells at the moderate pace is a mean over four maps whose individual differences were not separated here, and a gap of a cell or less between two switches is within what one map can move.

This traffic’s spread. Stretch ends in these streams come from the jumps and from the bunching that walking queries produce, and how uncertain a count of them is follows from that. Traffic whose stretch ends are regular would make a three-end count trustworthy and the gap unnecessary; traffic with heavier bunching would want a wider gap.

One on threshold. The silence and the count’s switching on stayed at 1,600, the value the earlier essays fitted; only the off threshold moved. A gap could also be opened upward, switching the watch on later, which was not tried.

Still open: a gap the count sets itself #

A fixed off threshold is the same at every count, and the plates say the right gap is about the count’s own uncertainty: wide for three stretch ends, unnecessary for five. A switch can compute that uncertainty, since it holds the spacings it averages. The standard error of a mean of $k$ spacings is their spread over $\sqrt{k}$, and a switch could return to the corners only when its reading plus some multiple $Z$ of that standard error is under 1,600 — so a reading of 1,100 from three wildly different spacings would not switch the watch off, and the same reading from five similar ones would.

The measurement that follows runs that switch at three, five and ten stretch ends with $Z$ of a half, one and two, the silence’s override kept at 1,600, on every stream here, beside the override alone and the best fixed gap. The prediction is that at $Z = 1$ the three-end switch matches the fixed gap’s 117.8 at one jump in 2,500 and loses less than a cell at one in 1,000, because fast traffic has spacings that are short and similar, so its standard error is small and the switch returns to the corners almost as readily as the override does. It could fail at the fast pace itself: jumps every thousand queries produce stretch ends that are bunched as well as fast, their spread may be as large as their mean, and a switch that waits for a confident reading may wait as long as the fixed gap did. The question is whether the evidence a count needs before it acts can be read from the count, or whether the right margin is a fact about the traffic that only the costs reveal.