Adjusting EWMA Decay for Irregularly Timed Observations
Summary
The document explains how to update an exponentially weighted moving average when observations arrive at uneven time intervals. It uses elapsed time between samples and a specified half-life to set the update weight. For a true half-life, the decay factor must be based on the natural logarithm of one half multiplied by elapsed time divided by the half-life; using elapsed time divided by the half-life alone gives a different decay rate.
The derivation checks the intended behavior: after one half-life, the prior estimate's remaining contribution should be one half. It does this by expressing that remaining weight over repeated updates and solving for the time-dependent alpha. A second answer proposes approximating an irregular duration as a number of fixed unit intervals and applying the regular update repeatedly, with average work depending on that interval count. The methods assume a chosen half-life and a consistent time unit; the discussion does not address initialization choices beyond retaining the first observation or the effects of noisy data.
Key ideas
- An irregular-time EWMA should use elapsed time to determine its update weight.
- For a specified half-life, the exponential decay exponent includes the natural logarithm of one half.
- The half-life condition means the previous estimate retains half its contribution after that duration.
- An alternative is to repeat a fixed-interval update for the number of unit intervals represented by the elapsed time.
Tags
Full text
# Online algorithm for calculating EWMA at irregular intervals?
# Online algorithm for calculating EWMA at irregular intervals?
What is a fast online algorithm for calculating the EWMA (exponentially weighted moving average) of an input variable observed at irregular intervals?
I know the formula for when sampling at regular intervals:
Calculating alpha from halflife:
$$ \alpha = 1 - e^{\frac{\ln{.5}}{H}} $$
Calculating the EWMA of x:
$$ E = \alpha\cdot x + (1-\alpha)\cdot E_{-1} $$
What is an algorithm for doing the same where the sampling interval is irregular?
Edit:
I have found an algorithm online, which purports to achieve an irregular EWMA.
```
double operator()(double x)
{
if (isnan(prev_ewma_)) // we don't decay the first sample
{
prev_ewma_ = x;
prev_time_ = Time::now();
return x;
}
double time_decay = Time::now() - prev_time_;
double alpha = 1 - std::exp(-time_decay / halflife_);
double ewma = alpha * x + (1 - alpha) * prev_ewma_;
prev_ewma_ = ewma;
prev_time_ = now;
return ewma;
}
```
Is this algorithm correct?
## Answer by Steve Landers (score 3)
https://quant.stackexchange.com/a/50703
The above code for an irregular EWMA doesn't quite give a half-life - the code is missing the $e^{\ln(.5)}$ term found in the preceding formula. To get a true half-life, the code should look like this:
```
double operator()(double x)
{
if (isnan(prev_ewma_)) // we don't decay the first sample
{
prev_ewma_ = x;
prev_time_ = Time::now();
return x;
}
double time_decay = Time::now() - prev_time_;
double alpha = 1 - std::exp(std::log(0.5) * time_decay / halflife_);
double ewma = alpha * x + (1 - alpha) * prev_ewma_;
prev_ewma_ = ewma;
prev_time_ = now;
return ewma;
}
```
To show that this works, we look at how alpha is used in the EWMA formula.
$$E = \alpha \cdot x + (1-\alpha) \cdot E_{-1}$$
We expect that after the half-life has elapsed, exactly half of $E_{-1}$ will remain in our filtered value. For each filtering timestep, the remaining value of $E_{-1}$ will be multiplied by $1-\alpha$, meaning we want to solve for $\alpha$ such that
$$0.5 = (1-\alpha)^N$$
where $N$ is the the number of samples we filter on during our half-life. For a fixed timestep $dt$ (time_decay in the code), we calculate $N$ as
$$N = \frac{H}{dt}$$
where $H$ is the half-life. This gives us
$$0.5 = (1-\alpha)^{\frac{H}{dt}}$$
Plugging in our new formula for $\alpha$:
$$\alpha = 1 - e^{\ln(0.5) \cdot \frac {dt} {H}}$$
$$(e^{\ln(0.5)\cdot \frac {dt} {H}})^{\frac{H}{dt}}$$
$$e^{\ln(0.5)} = 0.5$$
Exactly half of the original value will remain.
## Answer by madilyn (score 2)
https://quant.stackexchange.com/a/35838
You count the number of 'unit intervals' within that irregular duration between two events and repeat the update function by the count. Amortized time is the average number of unit intervals.
In practical use cases, the 'unit intervals' are larger (subsampling), so this is done in amortized constant time.Shown in full with attribution under the source's licence. Licence: CC BY-SA 4.0 (Stack Exchange)
This summary was written by Stratmill's research agent from the original; it is not a copy of the source.