A watch that switches itself off

A watch that looks less tried to rescue a landmark search’s watch at the one pace where it loses. The placement starts at the four corners of a weighted maze, the arrangement where the landmarks stand found best when nothing is known about the traffic. Every window of queries the watch prices its landmarks on the last twenty queries against four candidates near their destinations, and refits one landmark when the estimated saving pays for the refit. Where the destination jumps every thousand queries the watch costs 150.7 cells a query and the corners, which never look, 142.7. Looking less often did not help, because the looks it skipped were the looks that found the chances, and a rule that stretched the interval between looks climbed to its longest setting and stayed there.

That page’s closing section drew the conclusion its own numbers pointed at. At one jump in a thousand there is nothing to watch for, and a watch cannot win there by looking less, only by not looking. It proposed a switch. Each time the watch looks it would also price the corners on the same twenty queries; when the corners would have been cheaper summed over its last four looks, the watch would return to the corners and stop looking for 8,000 queries, then look again to see whether the pace had changed. The prediction was a cost within two cells of the corners at one jump in 1,000, by spending most of the stream switched off, and the ten-cell watch’s 116.4 kept at one jump in 2,500, where four windows should never favour the corners. It named the way this could fail: four windows at one in 2,500 that happen to hold three jumps, a verdict for the corners, and a watch switched off at the pace where watching pays.

Two prices for the corners #

Everything but the switch is the earlier pages’. The candidates are the four nearest the recent destinations, the restriction the candidates near where the queries end found cheap, and a refit replaces one landmark, the economy a refit that changes one landmark measured. Four maps of 2,500 cells, each a weighted maze with obstacles, 30,000 queries a stream, the destination jumping to a random open cell on average every 1,000, 2,500, 5,000 or 10,000 queries or drifting to a neighbour with a chance of 0.001 to 0.03 a query. Every search is an A* search guided by the distances to four landmarks and is charged the cells it expands; every refit and every look is charged its own searches. The watch is the one a horizon the stream can supply built, which scales each estimated saving to how long traffic has lately stayed within ten cells of one destination — the distance at which a placement after the traffic moved found a fitted placement’s advantage gone — and it is reported at the better of a 1,000-query and a 2,000-query window as before. So are the switches: each is run at both windows and reported at the better one at each pace, so that no comparison on these plates is a comparison of windows.

Two switches were run, and the difference between them is what they count as the corners’ advantage.

The switch on search costs is the proposal as written. At each look it already knows what the last twenty queries cost under its own landmarks, since it served them. Pricing the corners on the same twenty queries is one more charged search of the sample, and nothing at all when the corners are the current placement. It records the difference, and when the last four differences sum to more than nought it goes back to the corners — which costs nothing, since their distance tables are kept — clears its record and makes no look for 8,000 queries.

The switch charging the watch records a different difference. It scales the sample’s saving to the window, as the watch’s own estimate of a refit’s saving does, and adds what the watch has spent on looking and refitting since its previous look. That is the literal reading of the earlier page’s last sentence: what no policy there priced was the watch itself, against a placement that never watches. A watch that refits every few windows and saves little between refits is, by this account, more expensive than the corners even when its landmarks serve each query better, and that is the case the proposal set out to catch.

At one jump in a thousand #

At the pace it was made for, the switch reaches the prediction: charging the watch for itself it costs 144.4 cells a query against the corners’ 142.7, within two cells, switched off for 59% of the stream; comparing search costs alone it costs 145.5. Both are well under the 150.7 of the watch they switch off. The proposal’s arithmetic held at one jump in a thousand — but by two different routes, and the routes matter for what follows.

The plate’s split shows the two routes. The switch on search costs goes back to the corners only when its landmarks are serving the sample worse than the corners would. That happens after a jump, when the landmarks were fitted to a destination that has gone, so it gives up a placement exactly when that placement has become stale — the right trigger. Its searches cost 137.7, and it saves on refits and looking by being off for two fifths of the stream. The switch charging the watch goes back for a different reason: four looks in which the watch spent more than its landmarks saved. On fast traffic that is most stretches of four looks. Its searches cost 134.6, which is what a watch earns on the stretches it watches, and it watches 41% of the stream. The 9.8 cells of refits and looking it spends while switched on earn back 8.1 of searches — nearly, not quite, what never starting would have saved.

At one jump in a thousand, then, a watch that notices it is not paying for itself and stops is almost as good as never having started, which is the policy starting from the corners put at the start of every watch because it costs nothing to keep. The question the proposal raised was whether the noticing would also happen where it should not.

At every pace where watching pays #

At one jump in 2,500 the switches cost 125.3 and 126.1 cells a query, the corners’ cost to within a cell and a half, where the watch they switch off costs 116.4. This is the failure the proposal named, and the plate shows it is larger than the proposal feared. The watch’s whole advantage at this pace is gone; the switches have turned a watch that saves 8% of the corners’ cost into a placement that saves almost nothing.

It does not stop there. At one jump in 5,000 the switches cost 103.9 and 103.1 against the watch’s 98.1, and at one in 10,000 the switch charging the watch still pays 7.9 cells a query more than the watch. At every pace slower than one in 1,000, which is every pace where the earlier pages found watching worth doing, both switches make the watch worse. The switch on search costs comes closest at the slowest pace, 81.2 against 80.2, because stale placements are rarest there; the switch charging the watch makes the watch worse by 9.7, 5.0 and 7.9 cells at the three slower paces — by no less at the slowest than at the one before it — which is not what a switch reading the pace would do.

The trade, for the switch charging the watch at the four paces together, is a gain of 6.3 cells a query at the fastest against losses of 9.7, 5.0 and 7.9 at the other three. A designer who knew the pace in advance would not need a switch at all, and would choose the corners at one jump in a thousand and the watch everywhere else. The switch was meant to make that choice from evidence, and the evidence leads it to roughly the same choice, the corners, at the two fastest paces alike.

What a look reads #

At one jump in 1,000 and at one in 2,500 the switch reads the same thing: the corners look cheaper at four looks in five, the mean difference is 12,249 cells a window at one pace and 11,257 at the other, and the spread of single looks is about sixty thousand cells at both. Four looks at either pace sum to a verdict for the corners most of the time, and they would do so at any number of looks, because the means do not differ. The signal the switch acts on does not carry the pace.

The shape of the spread says why. Most looks find nothing to refit: the landmarks are already as good as the four nearby candidates on the last twenty queries, or the saving does not pay for a refit. A look that finds nothing costs its own searches — four candidates priced on twenty queries, and the corners priced once more — and saves nothing, so its difference is a few thousand cells in the corners’ favour. That is the cluster on the plate between 4,000 and 11,000, at every pace. The watch’s value arrives in the few looks that come soon after a jump and refit toward the new destination. Those looks show large savings at the next sample, tens of thousands of cells scaled to a window, and they are the long tail on the left of each spread.

At one jump in 10,000 the tail is most of the distribution, because there the destination stays long enough for every refit to keep paying at look after look, and the median look favours the watch by thirty-one thousand cells. At one in 2,500 the tail is a fifth of the looks. That fifth is enough for the watch to win overall — the earlier page measured that — and not enough for it to win a typical stretch of four. A sum over four looks is a sample of four from a distribution whose value lies in a fifth of it, and it misses the fifth more often than not.

The triggers confirm this directly. Of the ten times the charging switch went back to the corners at one jump in 2,500, five came after four looks with no refit between them, each difference between 4,300 and 16,900 cells — the price of looking and finding nothing, four times over. At one in 10,000 and a 1,000-query window, five of its six switches were the same: four idle looks in a row, at a pace where the next jump is on average five thousand queries away and the watch saves over a third of the corners’ cost. What the switch is detecting is idleness, and idleness is not a property of fast traffic. Every stream has stretches between chances. At the slow paces they are long.

One stream #

On one stream at one jump in 2,500, the switch charging the watch spends two thirds of the stream switched off, and eight of the stream’s twelve jumps arrive while it is not looking. Its first switch comes at query 4,000, after looks at 1,000, 2,000, 3,000 and 4,000 found nothing worth a refit. The destination it was ignoring then moves at 4,168, 5,576, 10,125, 10,841, 11,485 and 11,533 — a burst of six jumps the switch sleeps through. It wakes at 12,000, looks four times, finds nothing again and is off by 15,000 for another eight thousand queries, and when it wakes at 23,000 it refits twice in quick succession, which is the watch working, and is switched off once more by 26,000 to the end of the stream.

This stream’s pattern is the plate before it seen in time. A watch on this stream makes few refits, and each one pays for thousands of queries afterwards. Between them it looks, and finds nothing, and the switch counts each such look against it. Four in a row are enough, and at one refit every few thousand queries, four in a row are the ordinary state of affairs.

The switch on search costs is off for 27% of the same stream. It stays on through the early burst, refitting at 6,000 and 8,000, and its one switch comes at 18,000, when the landmarks it fitted at 8,000 are serving the sample worse than the corners would. That is the stale-placement trigger the first plate described, and it is the right trigger to have — a fitted placement that has gone stale is worse than the corners — but its response is wrong. Going back to the corners for eight thousand queries undoes a placement that could have been refitted at the next look, and the jump at 20,041 arrives while it is off.

Off at every pace #

A switch that could read the pace would be off for the whole of the fastest stream and for none of the others. The switch charging the watch is off for 59% of the fastest, 60% at one jump in 2,500 and 20% at one in 10,000, and for up to 29% of drifting streams. Its share switched off does not move at all between the pace where switching off is right and the pace where it is most wrong. The switch on search costs shows a gradient — 40%, 27%, 20%, 7% — because stale placements are commoner when jumps are frequent, but it is off for over a quarter of the stream at one in 2,500, where it should never be off, and for well under half at one in 1,000, where it should always be.

Three changes to the switch’s two settings were tried before this was believed, all on the switch charging the watch, all on jumping traffic at a 1,000-query window. Judging over the last eight looks rather than four, it costs 147.9 cells a query at one jump in 1,000 and 132.8 at one in 2,500. Judging over sixteen, 151.5 and 130.1, switching off once a stream rather than twice. Judging over four but pausing only 2,000 queries, 150.3 and 123.2. Every one of them is worse than the four-look switch at the fast pace and still worse than the watch at the slower one. A longer judgement does not separate the paces, which is what the pooled spreads predict: the means are the same, so more looks only make a verdict for the corners more certain. A shorter pause lowers the cost of each wrong switch and raises the number of switches, from two and a half a stream to five.

Drifting traffic, and traffic that changes pace #

On drifting traffic both switches stay within two and a half cells a query of the watch, and at two step chances one of them is a fraction of a cell under it — though the switch charging the watch is off for up to 29% of the stream. Drifts were never the switch’s target: the corners are far worse than the watch here, 139.3 to 153.2, and a switch that could tell would never leave the watch. It leaves because a slow drift has long stretches between refits made of idle looks, as every slow stream does. Why it costs so little to leave is not separated by these streams. A destination that moves a cell at a time is still near where it was when the switch comes back on after eight thousand queries, so the first look after the pause can refit to roughly the placement the switch gave up; that is one account, and a placement that was earning little at the moment the switch left is another.

On the two streams that change pace halfway, the switches come out at or a little under the watch, and the margins are smaller than the spread between maps. On traffic that jumps every 1,000 queries and then every 10,000, the switch on search costs pays 126.8 cells a query against the watch’s 127.4, and the switch charging the watch 128.9, off for 47% of the stream. On the reverse stream, slow then fast, both switches beat the watch narrowly, 122.2 and 122.3 against 123.8, because a switch that turns off in the fast half loses less there than the watch does. These are the only streams where a switch beats both of the policies it was built from, by 0.6 and 1.6 cells, and on streams that hold one pace — which is what the switch would have to recognise to be worth having — it never does.

A verdict that idles cannot reach #

The proposal’s switch rests on a sound idea: a watch should compare itself against the policy that never watches, and stop when it loses. Both switches here do that comparison, and the measurement shows why neither can act on it. The comparison is right over a whole stream — the watch is dearer than the corners at one jump in a thousand and cheaper at every slower pace — and wrong over any four looks, because the watch’s advantage is concentrated in a fifth of its looks and the comparison is dominated by the other four fifths.

That is a statement about the distribution of a policy’s value, and it is the same statement a refit priced before it is made met from the other side. There, a refit was priced against the saving it would earn over a window, and the estimate failed where chances were short, because a saving is earned over a destination’s whole stay and the sample sees only its start. Here the switch prices the whole watch against the corners over four windows and fails where chances are long, because a watch’s saving is earned over many windows and four of them are mostly the quiet ones. Each decision reads a short sample of a quantity whose value lies in its tail.

A rough count says how hopeless the four-look judgement is. Single looks at one jump in 2,500 spread with a standard deviation of about 62,000 cells, so a mean of four is uncertain by about 31,000. The watch’s whole-stream advantage at that pace is about 10,400 cells a window — a third of the uncertainty. To tell that advantage from nought with the usual two standard errors would take some 145 looks, 145,000 queries, nearly five times the length of a stream. And that is the easy comparison, against nought. The switch’s actual task is to tell one jump in 1,000 from one in 2,500, where the corners’ advantage changes sign, and on its own looks the two means differ by a thousand cells. No stream supplies enough looks for that.

What the queries know that the map does not found that a query log is worth reading exactly to the extent that it is not uniform. The same holds for a watch’s record of its own looks. Most of them are uniform — a few thousand cells spent, nothing found — and they say nothing about the pace. The informative events are rarer and sharper: a jump, a refit that pays, a placement going stale. A switch that reads costs is reading the uniform part.

Where these streams stop #

One judgement window and one pause, in the main. The switches judged over four looks and paused 8,000 queries, as proposed, and the three changes tried were run only on jumping traffic and only for the switch charging the watch. A switch that weighed looks by how recently a refit had paid, or that never cleared its record, was not run.

Costs only. Both switches read cells spent and saved. Neither reads the traffic directly — how often the destination has jumped — which is the quantity the decision depends on. The earlier page’s horizon reads it noisily from five stretches; nothing here reads it from more.

Four maps. Every number is a mean over four maps, as before. At one jump in 1,000 the switch charging the watch is dearer than the corners by four or five cells a query on two maps and cheaper by one or two on the other two, so the 1.7-cell gap on the first plate is a mean and is not true of any one map.

Still open: a switch that counts the jumps #

The switches failed because cost is a poor witness to pace: it is noisy, skewed, and dominated by the looks that find nothing. The pace itself is easier to see. A destination that jumps is a countable event — the traffic’s destination moves more than ten cells — and the earlier page already tracks those stretches to learn its horizon. A count of events has a known noise: k events estimate their rate to within about one part in $\sqrt{k}$. Ten jumps estimate a pace to about a third, and the paces to be told apart differ by a factor of two and a half.

The measurement that follows gives the ten-cell watch a switch that reads the jumps rather than its costs: it keeps the times of the last ten stretch ends, estimates the pace as their mean spacing, and returns to the corners while that spacing is under a threshold set between 1,000 and 2,500 queries, looking again whenever the estimate rises above it. The prediction is that at one jump in 1,000 it is switched off for most of the stream after its first ten thousand queries and costs within three cells of the corners, and that at one jump in 2,500 and slower it almost never switches, keeping the watch’s 116.4, 98.1 and 80.2. It could fail where the earlier horizon did: drifting traffic produces stretch ends too, each time the destination crosses ten cells, and at a step chance of 0.03 the drift does that every few hundred queries — so a pace read from stretch ends would call fast drift fast traffic and switch the watch off where it saves twenty cells a query. The question is whether the event a switch should count is the jump, which only fast jumping traffic makes often, or a stretch end, which drift makes too, and whether a watch can tell them apart from its queries alone.