A silence that overrules the count

A switch that hears the traffic stop worked on a landmark search’s watch and the switch that turns it off. The search runs on weighted mazes of 2,500 cells starting from four landmarks at the 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 four corners, which never look, are cheaper. A switch that counts the jumps reads the traffic’s pace as the mean spacing of its last $k$ stretch ends, the moments the destination has moved away from where the current stretch began, and keeps the corners while that pace reads under 1,600 queries.

A count of events cannot see the events stop. The earlier essay let the open spacing, the queries since the last stretch end, into the reading as one spacing among $k$ whenever it was the longer, and the switch heard a slowing. On ten stretch ends it heard it late, because the silence was averaged with nine fast spacings: after traffic whose stretch ends came every 1,121 queries, the reading crosses 1,600 only when the open spacing reaches $k \cdot 1{,}600 - (k-1) \cdot 1{,}121$, about 5,900 queries at ten.

Its closing section pointed at what the averaging ignores. An open spacing of 1,600 queries is already, by itself, a spacing slower than the threshold, and nothing the recorded spacings say can make the next one shorter than one that has not yet ended. It proposed letting the open spacing overrule the reading: keep the corners only while the recorded pace and the open spacing are both under 1,600, and turn the watch on the moment the silence alone passes it. It predicted that on the stream that slows halfway every count, ten and twenty included, would turn the watch on within about two thousand queries and cost about 125 cells a query, so that the count’s length stopped mattering there, and that at one jump in 2,500 the override would do at least as well as the silence. It named the risk at the fast pace, where a gap of 1,600 queries between stretch ends comes about one time in four.

The override hears the slowing at once. The count’s length still matters, and the reason it does has moved.

A reading the silence can overrule #

Everything but the reading is the earlier essays’: four maps, streams of 30,000 queries, destinations jumping 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 is charged the cells it expands and every look and refit its own searches; every switch is reported at the better of a 1,000-query and a 2,000-query window. The override switch reads exactly what the count reads, the mean spacing of the last $k$ stretch ends, unless the open spacing has reached 1,600 queries; then it reads the open spacing itself. It looks at its reading once a window, as the others do, and keeps the corners while the reading is under 1,600.

The difference from the silence switch is one of kind. The silence switch weighs the open spacing as evidence, one spacing among $k$, so a long silence after fast traffic has to outvote the record. The override treats it as a fact: a spacing that has lasted 1,600 queries is slower than the threshold however it ends, so the traffic is, for now, slow. The switch’s reading is checked at every window against the count’s: equal whenever the open spacing is under 1,600, equal to the open spacing whenever it is not.

The slowing heard within a window #

On the stream that slows halfway, the override costs 124.5 cells a query on three stretch ends, 125.9 on five and 127.9 on ten, where the count costs 128.9, 130.3 and 135.8 and the silence 124.9, 126.4 and 132.9. At every count it is the cheapest of the three switches, and on ten stretch ends it removes most of what the silence left: 127.9 against 132.9, within half a cell of the watch, which looks at every window and never switches at all.

On ten stretch ends the override turns the watch on within 1,000 queries of the slowing on the two maps where it was keeping the corners, and was already watching at the slowing on the other two. The silence switch took 3,000 queries on one map and 11,000 on two; the count never turned the watch on at all on three maps of four. A thousand queries is a single window: the override acts at the first look after the silence reaches 1,600 queries, which is the first or second look after the slowing. Once the watch is on, it stays on for most of the slow half. On one map it goes back to the corners twice in the rest of the stream, when a stretch end arrives and the count’s record, still mostly fast spacings, reads under the threshold again until the next silence reaches 1,600.

What still separates the counts #

With the override, the switches on three, five and ten stretch ends all keep the corners for 8% of the slow half, where the count keeps them 65%, 65% and 75% and the silence 15%, 18% and 42%. In the slow half the length of the count has stopped mattering, as predicted. The prediction’s figure for the whole stream, that every count would cost about 125 cells a query, has not come true: three stretch ends cost 124.5 and ten cost 127.9, a spread of 3.4 cells.

The spread is in the fast half. There the override keeps the corners 48% of the time on three stretch ends, 38% on five and 18% on ten. In fast traffic the corners are the right choice, and a count can only choose them once its record is full. The stream starts with no stretch ends recorded, and a reading of $k$ spacings needs $k + 1$ of them. At one every 1,121 queries, the four that a count of three needs come within about four and a half thousand queries, while the eleven a count of ten needs take about twelve thousand of the fast half’s fifteen thousand, and the switch on ten watches through all of that. A count of twenty needs twenty-one stretch ends, about twenty-three thousand queries, longer than the fast half lasts, so that switch never reads the fast pace on this stream and is the watch throughout.

So the count now does one job instead of two. Before, it had to read the traffic going fast, which needs a short memory, and going slow, which it could not do at all; the silence switch read both but heard the slowing late at long counts. With the override the silence does the second job outright, and the count is left with the first, where a short count is better. The length that mattered for both reasons now matters for one, and the best count is the shortest.

A lull that is real for as long as it lasts #

On the stream that speeds up halfway, the override is the cheapest switch at every count: 119.3 cells a query on three and five stretch ends and 122.7 on ten, against the count’s 121.1, 120.6 and 124.6 and the silence’s 120.2, 119.8 and 124.2. This is the stream on which the named risk should show. In the fast half a gap of 1,600 queries between stretch ends is common, and every such gap turns the watch on for a window and pays a look. It does: the override keeps the corners for 40% of the fast half on three stretch ends where the count keeps them 63%, and every one of those extra windows of watching is a look the count did not pay for.

And it is cheaper for it. A gap of 1,600 queries in fast traffic is a stretch during which the destination has stayed where it was for 1,600 queries, which is exactly the traffic the watch is built for: a look finds a landmark near where the queries now end, and the refit, priced before it is made, pays for itself within the stretch. The risk the closing section named assumed that a lull is noise in a fast pace. For the watch it is not; for as long as it lasts, a lull is slow traffic, and turning the watch on for it is the right decision made for the right length of time.

Steady traffic #

On steady traffic the override costs what the silence does to within a cell and a half at every pace and count, and at one jump in 2,500 it is cheaper than the count: 118.2 against 120.1 on five stretch ends and 117.7 against 119.9 on ten. Against the silence at that pace it is level, 118.2 against 118.1 on five stretch ends and 117.7 against 117.4 on ten, so the prediction that it would do at least as well is right to within three tenths of a cell. At the fast pace it is within a cell of both: on three stretch ends 142.6 against the count’s 142.3, on ten 146.1 against 146.6. The largest difference from the silence anywhere is at one jump in 5,000 on three stretch ends, 97.5 against 96.0, where the short count’s few lapses into the corners fall at different moments. On a destination that drifts a cell at a time no switch ever reads the fast pace, and every switch is the watch at every rate of drift.

The pace of one jump in 2,500 queries is where every switch still loses something. The watch costs 116.4 there, and every switch that ever keeps the corners costs more, from 117.4 to 121.6. At that pace stretch ends come a little more than 2,500 queries apart on average, but often enough two or three come close together for a short count to read under 1,600 and switch the watch off for a while. That is the count’s one remaining job, done imperfectly, and it is where the next measurement starts.

Evidence and fact #

The two switches differ in what they take the open spacing to be. A watch that switches itself off first gave the watch a way to stop looking, and every switch since has had to decide when to believe that the traffic has changed. The silence switch averages the open spacing with the record because it treats the record as evidence about the next spacing and the open spacing as more evidence of the same kind. The override does not average, because the open spacing is a lower bound rather than a sample: it says the current spacing is at least this long, and once that bound passes the threshold, no record can lower it.

That is a property of the threshold rule, not of this traffic. A switch whose decision is “is the pace slower than $T$” can be answered by a single open spacing longer than $T$, and only in one direction. No open spacing can show the pace is fast; only stretch ends arriving close together can, and that is why the count is still needed, and why its length still matters for the direction only it can see. A horizon the stream can supply made the same kind of point about what a stream can and cannot say about its own future: a stream can say how long it has been quiet, and nothing else about the quiet.

What the prediction got right #

The closing section predicted that, with the override, every count would turn the watch on within about two thousand queries of the slowing and cost about 125 cells a query on the stream that slows, so that the length of the count stopped mattering, and that at one jump in 2,500 the override would do at least as well as the silence. It turns the watch on within 1,000 queries wherever it needed to, and in the slow half the length of the count stops mattering, 8% at every count. Over the whole stream the counts differ by 3.4 cells a query, because the fast half still rewards a short count. At one jump in 2,500 it is level with the silence, within three tenths of a cell. The named risk, lulls in fast traffic, turned out to be a saving.

The question was 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. It is a fact to obey, and for the watch a lull long enough to trip the override is a change, for as long as it lasts.

What the switch leaves out #

One threshold, in both directions. The override and the count share the threshold of 1,600 queries. The count switches off at it and the silence switches on at it, which is what lets the moderate pace flip the switch back and forth.

Four maps, one seed a map. The differences between the switches at the fast and moderate paces are a cell or less, the size of the variation between maps.

A record that starts empty. Every switch begins each stream with no stretch ends and watches until it has $k + 1$ of them, and on the stream that slows that warm-up is most of what separates the counts. A switch that started from a record carried over from earlier traffic, or from the earlier essays’ measured spacing at each pace, would reach its first reading at once, and the long counts would lose less of the fast half than they do here.

Windows of 1,000 or 2,000 queries. The override can act only at a window boundary, so it hears a slowing at most one window late; a switch that read the silence at every query would hear it at once, at a cost this accounting does not price.

Still open: two thresholds #

The override took the switching on from the count, and left it the switching off. A count that only has to decide when the traffic is fast need not use the same threshold as the silence that decides it is slow. A switch could keep the corners only while the count’s reading is well under 1,600 queries, 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 now read just under 1,600, no longer switches the watch off.

The measurement that follows sets the off threshold at 1,000, 1,200 and 1,400 queries, keeps the override at 1,600, and repeats every stream at three and five stretch ends. The prediction is that at one jump in 2,500 the switch on three stretch ends with an off threshold of 1,200 keeps the corners less than 5% of the time and comes within a cell of the watch’s 116.4, while keeping the override’s 124.5 on the stream that slows and 119.3 on the one that speeds up to within a cell. It could fail at the fast pace, where stretch ends come every 1,121 queries on average: a reading of three of them has to fall under 1,200, and if it does so too rarely the switch keeps the watch on fast traffic and pays the eight cells a query the corners save. The question is whether a switch needs the same threshold in both directions, or whether the two jobs want two numbers.