A switch that hears the traffic stop

A switch that counts the jumps gave a landmark search’s watch a switch that reads the traffic. The search runs on weighted mazes of 2,500 cells, starting from four landmarks at the maze’s corners; the watch looks every window of queries for a better landmark near where recent queries end and refits one when the saving pays. Where the destination jumps every thousand queries the looking costs more than it saves, and the corners, which never look, are cheaper. The switch counts stretch ends, the moments when the traffic’s destination has moved more than ten cells from where the current stretch began, takes the pace as the mean spacing of the last $k$ of them, and keeps the corners while that pace reads under 1,600 queries. On ten stretch ends it separated the paces where reading the watch’s own costs could not.

It had one structural failure. When traffic slows, the events that would show it stop arriving, so the count keeps its fast reading and the switch stays off. On a stream that slows halfway, from a jump every thousand queries to one every ten thousand, the switch on ten stretch ends cost 135.8 cells a query, worse than the corners and worse than the watch it was meant to improve.

Its closing section proposed letting the time since the last stretch end into the reading. A spacing still open, the queries since the last stretch end, is a lower bound on the next spacing; once it is longer than the mean of the recorded ones, it is evidence that the pace has slowed, as strong as a recorded spacing of that length. The switch would read the mean of the last $k - 1$ recorded spacings and the open one, whenever the open one is the longer, so that a stream gone quiet raises its own reading. The prediction was that on the stream that slows halfway the switch on ten stretch ends would turn the watch back on within about four thousand queries of the slowing and cost about 129 cells a query instead of 135.8, and that steady traffic would see nothing, since an open spacing rarely exceeds the mean for long. It named the risk at the fast pace, where one gap in twenty between jumps is longer than three thousand queries and could switch the watch back on while the traffic is still fast.

The reading does hear the silence. On ten stretch ends it hears it late, and the arithmetic of why says what to change.

The silence in the reading #

Everything but the reading is the earlier essay’s: four maps, streams of 30,000 queries, destinations jumping at random on average once in 1,000, 2,500, 5,000 or 10,000 queries, drifting a cell at a time, or changing pace halfway; every search charged the cells it expands and every look and refit its own searches, priced before it is made; every switch reported at the better of a 1,000-query and a 2,000-query window. Both switches keep the times of the last $k + 1$ stretch ends. The count reads their mean spacing. The silence switch reads the same unless the open spacing, the queries since the last stretch end, is longer than the mean of the last $k - 1$ recorded spacings; then it reads the mean of those $k - 1$ and the open one. Both look at their reading once a window and keep the corners while it is under 1,600 queries.

The two switches count the same stretch ends on every stream, and the silence switch’s reading differs from the count’s only at windows where the open spacing is the longer, which is checked at every window.

The slowing heard, late #

On the stream that slows halfway, the switch on ten stretch ends that reads the silence costs 132.9 cells a query, against the count’s 135.8 and the watch’s 127.4; it is off for 42% of the slow half instead of 75%. The prediction said about 129. The silence takes the switch back on, but late enough that the slow half is still mostly spent on the corners, where watching would have saved twenty cells a query.

With fewer stretch ends the silence is heard in time. On five it costs 126.4 cells a query and on three 124.9, both under the watch and under the corners, and off for 18% and 15% of the slow half. On twenty nothing changes, because the count of twenty never switches the watch off in the first place: it reads too late at the fast pace to reach the threshold before the slowing. The earlier essay found that every count trades the fast pace for the slow one; the silence moves that trade, and moves it most for the short counts that were already quick.

Why ten stretch ends hear late #

After the slowing, the count’s reading on ten stretch ends stays where the last stretch end left it, under the threshold, until the end of the stream; the silence’s reading rises from the moment the open spacing passes the recorded mean, and crosses the threshold thousands of queries later. The reading rises slowly because the open spacing is one term of ten. The other nine are spacings recorded while the traffic was fast, about 1,100 queries each, and they stay in the reading until new stretch ends push them out, which on slowed traffic means for a long time.

A reading of $k - 1$ fast spacings and one open spacing crosses the threshold $T$ only when the open spacing reaches $kT - (k-1)\mu$, with $\mu$ the fast spacing: 2,558 queries of silence at three stretch ends, 3,516 at five, 5,911 at ten and 10,701 at twenty. The measured times fit that arithmetic once the windows and the slow traffic’s own stretch ends are allowed for. On ten stretch ends the watch came back on 3,000 queries after the slowing on one map and 11,000 on two, where a stretch end arriving in the slow traffic restarted the silence; on five it came back after 3,000 to 5,000 queries on the three maps where it had been off.

The closing section reasoned that an open spacing longer than the recorded mean is as strong evidence as a recorded spacing of that length. It is, as one spacing among $k$. A long count’s reading moves a tenth of the way for every query of silence beyond the old mean, and a short count’s a third. The silence a count of $k$ events can hear is diluted by the $k - 1$ events it remembers, which is the same delay of $k$ events the earlier essay found for the count itself, now applied to the absence of events.

Back on, for good #

After the slowing, the count of ten keeps the corners to the end of the stream on three maps of four; with the silence it turns the watch back on for good 3,000 to 11,000 queries after the slowing on those three. On five stretch ends the silence brings the watch back after 3,000 to 5,000 queries on the maps where it was off, and the count alone does so on one of them, after 9,000, when a stretch end in the slow traffic happened to arrive. On the second map neither switch was off after the slowing at all, since its last fast stretch ends had spaced out before the slowing came.

That is the structural failure repaired. Without the silence, a count can only learn that traffic slowed by waiting for the next event, and a slow stream supplies one every ten thousand queries; a horizon learned from the watch’s own refits ran into the same limit, since an estimate built from events learns only as fast as the events arrive. With it, every query of silence counts towards the reading, and the only question left is how much each one counts.

Steady traffic, unchanged #

On steady traffic the silence costs at most nine tenths of a cell a query at the fast pace, 142.6 against 141.7 on five stretch ends and 146.8 against 146.6 on ten, and helps at one jump in 2,500: 118.1 against 120.1 on five and 117.4 against 119.9 on ten. The named risk, lulls at the fast pace read as a slowing, is real and small. On five stretch ends a lull lifts the reading over the threshold once the open spacing passes about 3,500 queries, which between stretch ends spaced 1,121 apart on average happens about one time in twenty-five, and then only for a window or two, until the next stretch end brings the reading down.

At one jump in 2,500, the pace at which a watch looking for candidates near where the queries end first pays, the silence corrects a misfire the count makes, and the likeliest mechanism is this one. The count of five turns the watch off when a run of quick jumps happens to come together, and keeps it off until slower ones push the quick spacings out; the silence ends that sooner, because the gap after a cluster is itself a long open spacing. The count of five is off for 28% of that stream and the silence switch for 13%. On drifting traffic no switch is ever off, with or without the silence, since a drift of one cell at a time never produces stretch ends quickly enough to read under the threshold. On the stream that speeds up halfway the silence changes nothing to speak of, 119.8 against 120.6 on five stretch ends: speeding up is events arriving, which a count already hears.

What the late hearing costs #

The cost of hearing late is easy to put a size on, and it is the mirror of the cost a watch that looks less tried to cut: there the watch looked too much in fast traffic, here the switch watches too little in slow. On the slow half of the stream, the corners cost about 125 cells a query and the watch about 80, so every query a switch spends keeping the corners after the slowing costs about 45 cells. The count of ten keeps them for three quarters of the slow half, about 11,000 queries, which is about half a million cells, or 17 cells a query averaged over the whole stream: enough to turn the switch’s gain in the fast half into a loss. The silence switch on ten stretch ends keeps the corners for 42% of the slow half, about 6,300 queries and 9 cells a query over the stream; on five, for 18%, about 2,700 queries and 4 cells a query. These are estimates from the off shares and the two policies’ steady costs, not separate measurements, and they account for most of the differences between the switches on that plate.

The fast half is where the switches earn their keep, and there all of them earn about the same: the corners at the fast pace cost 142.7 against the watch’s 150.7, so a switch that is off for most of the fast half saves six or seven cells a query on the stream. What separates the switches on the stream that slows is almost entirely the slow half, and the slow half is where a switch has to hear silence, the one thing a count of events cannot hear by itself.

The best of the switches #

The switch on five stretch ends with the silence costs 142.6 cells a query at one jump in 1,000, 118.1 at one in 2,500, 98.1 and 80.2 at the slow paces, 126.4 on the stream that slows and 119.8 on the stream that speeds up. The best policy known for each steady pace, the corners at the fast pace and the watch at every slower one, costs 142.7, 116.4, 98.1 and 80.2. The switch is within 1.7 cells of it on every steady stream and under both the corners and the watch on both streams that change pace, which no fixed policy and no switch before it managed.

A watch that switches itself off had concluded that a watch cannot tell from its own costs whether it should be watching. The traffic tells it, if the switch counts events and listens to their absence too, and does both over a short memory. The earlier essay’s trade between noise and delay remains, and five stretch ends is where these four paces put the balance.

What the prediction got right #

The closing section predicted that on the stream that slows halfway the switch on ten stretch ends would turn the watch back on within about four thousand queries of the slowing and cost about 129 cells a query. It turns the watch back on after 3,000 to 11,000 queries and costs 132.9, because the open spacing is averaged with nine fast spacings and the reading crosses the threshold only after about six thousand queries of silence. It predicted nothing would change on steady traffic, and nothing does beyond a cell; at one jump in 2,500 the silence helps. It named the risk that a long gap at the fast pace would switch the watch back on, and the cost of that is under a cell a query.

The question was whether a switch can read silence without reading every lull as a change of pace. It can, because a lull is one long spacing in a reading of several, and the same dilution that makes ten stretch ends slow to hear a slowing makes five stretch ends deaf to a single lull. The silence was the missing half of the count; the length of the count still decides how quickly either half is heard.

What the streams leave out #

Two paces apart. The streams that change pace go from one jump in 1,000 to one in 10,000 or back, a factor of ten. A slowing by a factor of two and a half, to the pace where watching first pays, would give the silence much less to hear.

One threshold. Every switch keeps the corners under 1,600 queries, the geometric mean of the two paces the earlier essay set out to separate. A threshold set for the silence alone, rather than for the recorded spacings, was not tried.

Four maps. As before, four maps and one stream each per setting; the times to turn back on vary from 3,000 to 11,000 queries between maps, and a count of maps is what such a spread rests on.

Still open: silence that overrides the count #

The silence enters the reading as one spacing among $k$, so a switch on ten stretch ends needs six thousand queries of it before it acts. But an open spacing of 1,600 queries is already, on its own, a spacing slower than the threshold, and nothing the recorded spacings say can make the next spacing shorter than one that has not yet ended. A switch could treat the open spacing as an override rather than a term: keep the corners only while the recorded pace is under the threshold and the open spacing is too, and turn the watch back on the moment the silence alone passes 1,600 queries.

The measurement that follows gives the switches on 5, 10 and 20 stretch ends that override and repeats every stream. The prediction is that on the stream that slows halfway every count, ten and twenty included, turns the watch back on within about two thousand queries of the slowing and costs about 125 cells a query, so the length of the count stops mattering there, and that at one jump in 2,500 the override does at least as well as the silence. It could fail at the fast pace, where a gap longer than 1,600 queries comes about one time in four between stretch ends spaced 1,121 apart on average, and every such gap would turn the watch on for a window and pay a look. The question is whether the open spacing is evidence to weigh or a fact to obey, and whether a switch that obeys it can still tell a lull from a change.