A switch that counts the jumps

A watch that switches itself off gave a landmark search’s watch a way to stop. The placement starts at the four corners of a weighted maze; every window of queries the watch prices its landmarks on the last twenty queries against candidates near their destinations, and refits one landmark when the saving pays. Where the destination jumps every thousand queries the watch costs more than the corners, which never look, and the switch was meant to notice that and stop. It noticed, and it also stopped at every slower pace, because what it read — the corners’ advantage on each look’s sample, less the watch’s own spending — had the same mean at one jump in 1,000 and at one in 2,500. The watch’s value arrives in a few large looks after jumps, and any four looks are mostly the others.

That page’s closing section concluded that cost is a poor witness to pace and proposed reading the pace directly. The traffic’s destination moving more than ten cells from where a stretch of traffic began — a stretch end — is a countable event, and the earlier pages already track it to learn the watch’s horizon. A count of events has a known noise: k of them estimate their rate to about one part in $\sqrt{k}$. The paces to be told apart differ by a factor of two and a half. The proposal was a switch that keeps the times of the last ten stretch ends, takes the pace as their mean spacing, and keeps the corners with no looking while that spacing is under a threshold between the two paces. It predicted a cost within three cells of the corners at one jump in 1,000, after the first ten thousand queries, and the watch’s own cost at every slower pace. It named the failure: drifting traffic also produces stretch ends, and a fast drift might be read as fast jumps.

The switch #

Everything else is the earlier pages’: four maps of 2,500 cells, each a weighted maze, 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, or changing pace halfway; every search charged the cells it expands, every look and refit its own searches. The watch is the one a horizon the stream can supply built, and every policy, the switches included, is reported at the better of a 1,000-query and a 2,000-query window, the convention the earlier page settled on.

The switch keeps the times of the last $k+1$ stretch ends — the queries at which the destination was first more than ten cells from where the current stretch began — and at each window takes their mean spacing as the pace. While the pace is under $T$ queries, it keeps the corners and makes no look; otherwise the watch runs as before. Counting costs nothing, since the destinations are those of queries already served. The proposal’s switch is $k = 10$ and $T = 1{,}600$, the geometric mean of the two paces. Also run: $k$ of 3, 5 and 20 at the same threshold, and thresholds of 1,250 and 2,000 at $k = 10$.

Before any stream, the gamma distribution says what to expect. If stretch ends arrived at random with mean spacing $\mu$, the mean of $k$ spacings would fall under $T$ with a computable chance, and that chance is the switch’s error rate: at the slow pace, a false alarm; at the fast pace, a hit. On these streams stretch ends come every 1,121 queries at one jump in 1,000 and every 2,469 at one in 2,500.

The count separates the paces #

Counting stretch ends separates the paces where reading costs could not: the proposal’s switch on ten of them brings the watch from 150.7 cells a query to 146.6 at one jump in 1,000, and costs 119.9 against the watch’s 116.4 at one in 2,500 and the watch’s own cost at the two slower paces. The switch on costs had cost 126.1 at one jump in 2,500 and been off for 60% of that stream; the count’s switch is off for 15%.

The prediction is met at the slow paces and missed at the fast one. At one jump in 1,000 the switch was predicted to come within three cells of the corners; it comes within four, 146.6 against 142.7. The proposal’s own arithmetic says why: no reading exists until ten stretch ends have passed, about eleven thousand queries at this pace, and the watch pays its full cost until then. On one map the first reading under the threshold came at 28,000 queries.

Every count trades one pace for the other #

Every count of stretch ends buys the fast pace with the slower one: five stretch ends cost 141.7 cells a query at one jump in 1,000 — under the corners — and 120.1 at one in 2,500, where twenty cost 149.9 and 116.4, and the point that knows the pace in advance, 142.7 and 116.4, is out of every count’s reach. A short count reads early and wrongly; a long count reads late and rightly. The thresholds barely matter: at ten stretch ends, moving the threshold from 1,250 to 2,000 queries changes the cost at either pace by a cell or two.

That a switch on three or five stretch ends comes in under the corners at the fast pace, by a cell, is the one surprise on the plate, and it is smaller than the spread between maps. The switch returns to the corners whenever it is off, so what it adds is the watching it does before its first reading and in the windows where a reading strays over the threshold; those stretches evidently cost the watch no more than they save. It is not a reason to prefer a short count, whose cost at the slower pace is the larger number.

The arithmetic of a count #

The false alarms follow the arithmetic of a count: at one jump in 2,500, where stretch ends come every 2,469 queries, the chance that a mean of k spacings falls under 1,600 is about 30%, 22%, 11% and 4% for k of 3, 5, 10 and 20, and the switches are off 38%, 28%, 15% and nought of the stream. The measured shares run a little above the formula, because one false reading switches the watch off until a reading rises above the threshold again, a stretch longer than one window. At the fast pace the formula’s chance of a correct reading is between about four in five and nearly all, and the switches are off only 23% to 57% of the stream, because the first reading waits for $k$ stretch ends and the first few thousand queries are spent watching.

So the trade on the earlier plate is not a matter of tuning. A reading from $k$ events spreads by about one part in $\sqrt{k}$, so its chance of straying across a threshold shrinks only slowly as $k$ grows, and it is not available until $k$ events have happened. A switch that must be right at both paces within a 30,000-query stream needs enough events to be sure and few enough to be early, and at a pace ratio of two and a half there is no count that gives both.

On a single stream the delay is plain. The switch on ten stretch ends has nothing to read for the first ten thousand queries or so, and pays the watch’s cost through them; once it has a reading, the reading sits near the stream’s true spacing, under the threshold, and the switch is off for most of what is left. The third of the stream before the first reading is where the three or four cells between it and the corners go.

Why the traffic tells what the costs could not #

The two switches differ in what they read, and the difference is the whole of the result. The switch on costs read, at each look, the watch’s own spending against what the corners would have cost on the same twenty queries. That number mixes two things: how often the destination moves, which is the pace, and how often the watch finds nothing worth a refit, which is a property of the watch. A refit priced before it is made built the watch to look every window and refit only when a refit pays, so most looks at every pace find nothing, and the switch on costs read those idle looks as the corners winning. Its mean reading was the same at the two fast paces because the idle looks dominate both.

A stretch end has no such mixture. It happens when the destination moves, whatever the watch is doing, and it is counted from the queries already served at no cost to anyone. Its rate is the pace and nothing else: 1,121 queries between stretch ends at one jump in a thousand, 2,469 at one in 2,500, 4,799 and 9,094 at the two slower paces, each within an eighth of the jump rate itself. A reading made of those numbers can only be wrong by being too few, which is a noise the arithmetic of a count describes exactly, and not by measuring the wrong thing.

That is why the count can be trusted where the costs could not, and also why it inherits a count’s limits. It knows the pace only as well as the events that have happened, and starting from the corners is the reminder that a watch begins every stream knowing nothing: the corners are its placement until the first refit, and the count’s switch is the watch until its first reading. Neither has evidence before the stream supplies it, and the stream supplies events at the pace being estimated, slowest when they are most needed to show a slowing.

Drifts, and traffic that slows #

On drifting traffic no count of stretch ends ever switches the watch off: every switch costs exactly the watch’s 107.4, 120.7, 108.6 and 123.7 cells a query at the four step chances. The proposal’s named failure does not occur. A destination that moves one cell at a time needs, on average, about a hundred steps to wander ten cells from where it started, and at the fastest drift, one step in thirty-three queries, that is thousands of queries; over four maps the drifting streams produced sixteen stretch ends at the fastest rate and none at the two slowest. A pace read from them is never under 1,600, and the watch, which saves thirty to thirty-five cells a query over the corners on drifting traffic, is never switched off.

A count of stretch ends cannot see traffic slow down: on a stream that jumps every 1,000 queries and then every 10,000, the switch on ten stretch ends costs 135.8 cells a query, more than the corners’ 133.2 and the watch’s 127.4. In the fast half it switches off, as it should. In the slow half stretch ends come every ten thousand queries, so in the remaining fifteen thousand there are one or two, and the reading — the mean spacing of the last ten — still holds eight or nine fast spacings and stays under the threshold. The switch keeps the corners through the slow half, where the watch would have saved a third of their cost.

This is the failure the proposal did not name, and it is structural. A count reads the pace from events, and slowing down is the absence of events. Every other failure on these plates is a matter of degree — a delay, a noise — but this one has no degree: a reading made only of events that have happened cannot register the events that have stopped. On the reverse stream, slow then fast, the switches do what they do at steady paces, and the shorter counts beat the watch by two or three cells.

What a switch needs to know #

Summed over the four steady paces, the watch pays 8.0 cells a query more than a policy that knew the pace, all of it at one jump in 1,000; the switch on five stretch ends pays 2.7, a third of that; the switch on ten pays 7.4; the corners 84.3. On steady traffic a count of a few stretch ends removes two thirds of the watch’s excess, which the switch on costs could not do at any setting. A watch that looks less and its successor spent two pages establishing that the watch’s own records cannot tell it the pace; the traffic’s records can, roughly and late.

The switch needs to know two things the count gives it in opposite proportions: whether the traffic is fast now, and whether it has stopped being fast. The first needs a few events; the second needs the absence of events to count as evidence. What the queries know that the map does not found a query log worth reading exactly where it is not uniform, and a stretch end is the most non-uniform thing in the log; its absence is the most uniform, and it is the part of the evidence a count throws away.

Where these streams stop #

One threshold rule. The switch compares a mean of spacings with a threshold. A rule that weighted recent spacings more, or compared the latest spacing alone with the mean, would read changes of pace sooner and noise more.

A stretch defined at ten cells. A stretch ends when the destination is more than ten cells from where it began, the distance a placement after the traffic moved found a fitted placement stops helping, and the candidates the watch prices are the four nearest the recent destinations, as the candidates near where the queries end chose them. A smaller distance would count drift steps as events and bring back the failure the proposal feared.

Four maps. Every number is a mean over four maps. At one jump in 1,000 the switch on ten stretch ends was first switched off between 9,000 and 28,000 queries depending on the map, and its cost on one map is not its cost on another.

Still open: a reading that counts the silence #

The count’s one structural failure is that it cannot see events stop. The fix is to let the time since the last stretch end enter the reading. A spacing that is still open — the queries since the last stretch end — is a lower bound on the next spacing, and once it exceeds the mean of the recorded spacings it is evidence that the pace has slowed, as strong as a recorded spacing of that length would be.

The measurement that follows gives the switch a reading that is the mean of the last $k - 1$ recorded spacings and the open one whenever the open one is longer than their mean, so that a stream that has gone quiet raises its own reading, and runs it on every pace and on both streams that change pace. The prediction is that on the stream that slows halfway the switch on ten stretch ends turns the watch back on within about four thousand queries of the slowing, costing about 129 cells a query instead of 135.8, and that nothing changes on steady traffic, where an open spacing rarely exceeds the mean for long. It could fail at the fast pace, where a single long gap between jumps — one in twenty at this pace is longer than three thousand queries — would raise the reading over the threshold and switch the watch back on for a stretch of traffic that is still fast. The question is whether a switch can read silence without reading every lull as a change of pace, which is the same question the count answered for events, asked of their absence.