A decay measured from where it started

The fading nobody computes measured why an exponentially decayed counter can be kept as a single number and updated lazily. The decay over any gap is a factor that depends on the gap alone. The counter stores a value and a time and multiplies on the way past, and an idle counter costs nothing.

That property belongs to one weight function. Exponential decay is the only decay in which an arrival’s weight falls by a factor that does not depend on the arrival’s own age. Every other decay needs something more. A polynomial weight, where an arrival of age $a$ counts $(1 + a/s)^{-\alpha}$, falls slowly at first and then keeps a long tail. It is often what a monitoring question wants, because it remembers an old burst more than an exponential would. But at each reading, every arrival has faded by a different factor, so the sum cannot be carried forward in one number. Computed exactly, it needs every stamp kept.

The counter with no window in it named a third option in passing, forward decay, and described it as computing the same thing relative to a landmark. It computes something close to that. The difference is the whole of this essay.

One number, against a landmark #

Forward decay, in the form Cormode, Shkapenyuk, Srivastava and Xu described, fixes a landmark $L$ in the past and weights an arrival at time $t_i$, read at time $t$, as

$$\left(\frac{t_i - L}{t - L}\right)^{\beta}.$$

The numerator is fixed at the moment of arrival. So a counter keeps one running sum, $\sum (t_i - L)^\beta$, adds each arrival’s term once, and divides by $(t - L)^\beta$ when it is read. That is one number and a landmark, and a polynomial weight. The counter here is checked against the same weights recomputed from every stamp, and the two agree.

The age of an arrival is $t - t_i$, and its weight in terms of age is $(1 - \text{age}/(t - L))^\beta$. Age appears divided by the time since the landmark. The weight is a function of age relative to the landmark, not of age.

The two forward curves are one scheme at two moments in its life. Read twenty seconds after the landmark it forgets faster than the exponential. Read 160 seconds after, it barely forgets at all, and an arrival forty seconds old still counts more than half.

Memory that grows with the stream #

The age at which an arrival counts half is the plainest measure of how long a decay remembers.

For forward decay the half-weight age is $(1 - 2^{-1/\beta})$ times the time since the landmark: 50% at β = 1, 29% at β = 2, 16% at β = 4. Those are straight lines through the origin on the plate. Raising β shortens the memory in proportion but does not stop it growing. Exponential and backward decay have no landmark, and their lines are flat.

So “forward decay with a polynomial weight” is not a polynomial decay with a long tail kept in one number. It is a decay whose timescale is set by how long ago the counter was started. A counter started at boot forgets over a quarter of its uptime.

A rise, twenty seconds in and five minutes in #

The consequence is measurable on a stream. A Poisson stream arrives at 100 a second and rises to 400 at a stated moment. Each scheme turns its counter into a rate estimate, scaled so that a steady rate reads correctly, and the measure is how long after the rise each estimate passes the midpoint of 250 and stays above it.

At 160 seconds the forward counter anchored at the start remembers the first two minutes as strongly as the last minute, and it takes most of a minute to show a fourfold rise. It is also by far the quietest of the three before the rise, with a spread of 0.8% of the rate. That is not a virtue in this setting, because the quiet was bought with the same long memory that hides the rise. It is what a long memory looks like, and it came from the counter’s age, not from a choice.

Anchored at the start, forward decay takes 26% of the stream’s age to respond. That share follows from the weights. Before the rise the counter has accumulated weight in proportion to $(s/t)^{\beta+1}$ of its time, where $s$ is when the rise happened. The estimate passes halfway when $(s/t)^3 = 1/2$, that is at $t = 2^{1/3} s$, a delay of $0.26\,s$. The measured delays, 5.3 s after 20 and 83.2 s after 320, are that fraction to within the sampling interval. The other three schemes’ delays do not depend on when the rise comes.

Where a growing memory is the point #

None of this makes forward decay wrong. It makes it a different tool, and there are questions it answers better than anything with a fixed timescale.

A report that runs from a fixed moment, such as the start of a trading day, a deployment or an incident, wants exactly the weights forward decay gives. Everything since the moment counts, recent arrivals count more, and “recent” is judged against how long the reporting period has run. At five minutes into the day the last minute should dominate. At five hours in the last hour should, not the last minute. A fixed half-life cannot do that, because five minutes and five hours ask for different half-lives. Forward decay with the landmark at the start of the period gives both from one number, and the growing memory measured above is the feature that makes it work.

It also merges cleanly, which matters for the same kind of report. Two counters over two shards of a stream that share a landmark hold sums of terms $(t_i - L)^\beta$, and the sum over both shards is their sum. The summaries that add found that property worth a great deal in sketches, and forward decay has it with no alignment step. Exponential counters merge too, but each has to be faded to a common time first, because each is stored as of its own last update.

What forward decay does not do is stand in for a fixed-timescale decay on a stream that runs indefinitely. That is what “decays relative to a landmark rather than relative to now” suggests, and the response plate shows it would have to be restarted to do so.

Moving the landmark #

The obvious repair is not to leave the landmark at the start. A landmark moved forward every so often bounds the time since it, and with it the memory.

A forward sum cannot be moved to a new landmark in place. Its terms $(t_i - L)^\beta$ cannot be re-expressed against a later landmark without the individual stamps, and arrivals before the new landmark should not count at all. So moving the landmark means starting a new counter and discarding the old one. Just after a restart, the new counter has seen almost nothing and its estimate is unreliable.

The scheme measured here keeps two counters, restarted in turn every sixteen seconds and offset by eight. It reads whichever is older, provided it is at least eight seconds old. The landmark is then always between eight and sixteen seconds back, the half-weight age between 2.3 and 4.7 seconds, and the state is two numbers and two landmarks.

Restarting has a cost that the half-weight age does not show. A counter just after its restart has seen a few seconds of arrivals and weights them heavily, so its estimate is as uncertain as a short window’s. The window that is not full measured the same problem for a window whose occupancy varies. The eight-second minimum age exists to avoid it, and it is also why two counters are needed rather than one.

On the response plate that scheme answers in 2.4 to 3.3 seconds at every rise time, faster than the exponential. On the step plate it is also noisier, 2.7% against 2.0%. A faster response and more noise usually go together, so the fair comparison has to hold one of them fixed.

Noise against speed #

Each scheme has one parameter that sets how long it remembers: the half-life, the scale, or the restart period. Sweeping it traces the trade between how quickly a scheme follows a change and how much its estimate wanders while nothing is changing.

The three sweeps lie close to one curve. At a response of about two and a half seconds all three have a spread near 4%. At about five seconds all three are near 2.6%. The restarted forward scheme reaches further towards speed, at a second, but it pays for it at exactly the rate the other two would. On this measure, the shape of the weight function does not buy a better trade. A decay that follows a change quickly is noisy by about the same amount whatever shape its weights have, and only the timescale matters.

There is a simple reason to expect that. Any of these estimates is a weighted count of Poisson arrivals. Its spread is set by how many arrivals effectively contribute, the square of the total weight divided by the sum of the squared weights. Its speed is set by how far back the weight sits, roughly the weighted mean age. For weight shapes that fall off smoothly, those two quantities move together: a shape that averages over more arrivals must reach further back to find them. The shape changes the constant relating the two only a little, and the plate measures how little. Counting past what the register holds met a similar bargain in a probabilistic counter, where lower error had to be bought with more bits. Here lower spread is bought with delay, and the weight shape barely changes the price.

That removes most of the case for a polynomial weight on a rate estimate, and it points at the one that remains. A polynomial tail is about remembering something rare for longer, a spike an hour ago that should still register. Neither the spread nor the response measures that. What the plate does settle is that exponential decay, in one number and one stamp, sits on the same curve as the others. For the question it answers, a more elaborate weight is not buying accuracy.

Why exponential decay alone fits in one number #

The one-number property is worth stating exactly, because it explains why every scheme other than exponential decay pays somewhere.

A counter can be carried forward in one number if, between arrivals, every weight it holds changes by the same factor. Then the stored sum can be multiplied by that factor without knowing what it is made of. If the factor for an arrival depends only on the elapsed gap, and applying two gaps in a row equals applying their sum, the weight has to be an exponential in age. That is the memoryless property, and exponential decay is the only continuous weight that has it.

Forward decay avoids the requirement by never multiplying. It divides by $(t - L)^\beta$ at read time instead, and that division applies one factor to every arrival, based on the time since the landmark. It fits in one number for the same reason exponential decay does, one shared factor. The factor is simply taken against the landmark rather than against each arrival’s age, and that is where the landmark gets into the memory.

Backward polynomial decay has no shared factor at all. Two arrivals of different ages fade by different amounts over the same gap, so there is nothing to multiply the sum by. What a window costs in bits measured the state an exact window needs against an approximate one, and exact backward polynomial decay sits at the expensive end of that comparison, with no window to cap it.

What each scheme stores #

The costs in state are simple and worth putting beside the curve. The exponential counter stores a value and the stamp of its last update, the pair the fading nobody computes updated lazily. Forward decay with a fixed landmark stores a sum and a landmark, and the landmark never changes. The restarted scheme stores two of those. Backward polynomial decay computed exactly stores every stamp since the beginning of the stream, and that is the only one of the four whose state grows with the stream.

A stamp per arrival is the price a window that is a duration paid for an exact window, and backward polynomial decay pays it with no window to cap it. A common approximation is a handful of exponentials at different half-lives, summed with weights. That keeps a fixed number of numbers and gives up exactness at the tail. Nothing here measures how close such a sum gets.

What is settled and what is not #

Settled, by the weight functions: forward polynomial decay counts an arrival half at $(1 - 2^{-1/\beta})$ of the time since its landmark, 29% at β = 2, and its memory grows in proportion to that time. Its one number is a sum with a single shared divisor, the same reason exponential decay fits in one number, and the divisor is taken against the landmark. Exact backward polynomial decay has no shared factor and keeps every stamp.

Settled, by measurement on Poisson streams rising from 100 to 400 a second: anchored at the start, it takes 26% of the stream’s age to pass the midpoint, 5.3 s for a rise at 20 s and 83.2 s for one at 320 s. Exponential and backward polynomial decay with 4-second timescales take 4 to 5 seconds whenever the rise comes. Restarting the landmark every 16 s brings forward decay to 2.4 to 3.3 seconds, at a spread of 2.7% against the exponential’s 2.0%. Swept over their parameters, the three trace nearly the same curve of spread against response.

Not settled:

Spreads at long timescales. The spread is measured over the forty seconds before the rise, which holds too few independent readings for a memory longer than about eight seconds. The sweeps stop there for that reason.

Other shapes of change. Every stream here has one sudden rise. A slow drift, a single burst or a periodic swing could separate the weight shapes in a way a step does not, and the tail of a polynomial decay is presumably for exactly those.

A sum of exponentials. The practical stand-in for a polynomial tail is not measured. Neither is the error such a sum makes against the exact tail, which is the number that decides whether keeping every stamp is ever worth it.

Still open: a burst that should still count an hour later #

The trade curve says weight shape does not matter for following a rate. The question polynomial decay is actually for is different: whether a burst long past still registers, and whether the decay can tell it from noise. That needs a stream with a single burst at a known time, and a measure of how long after it each scheme’s estimate stays distinguishable from its no-burst value at a fixed false-alarm rate.

The measurement that follows puts a burst of a stated size into a steady Poisson stream and, for each scheme at matched spread, finds how long the burst remains detectable. It includes backward polynomial decay from every stamp, a sum of three exponentials at half-lives spaced by a factor of eight, and the restarted forward scheme. The prediction is that the polynomial tail keeps a large burst detectable several times longer than an exponential of the same spread, that three exponentials recover most of that, and that restarted forward decay loses it at the first restart. That last one would be the real cost of keeping a polynomial decay in one number.