1 Running Statistics Fundamentals

1.1 Definitions and common use cases

Running statistics are summary quantities updated incrementally as new observations arrive. Rather than retaining the full history of data, an algorithm maintains a small internal state (for example, counts and accumulated sums) and revises the statistic when each new sample is processed. This approach is widely used in streaming analytics, continuous monitoring systems, and online learning settings where data may be unbounded or arrives at high frequency.

Commonly maintained metrics include the running mean, variance (and derived standard deviation), minimum and maximum values, and simple rates such as counts per unit time. For tasks that require distributional information rather than only averages, running or approximate quantiles and percentile-like summaries are used.

1.2 Online vs. batch computation

In batch computation, a statistic is calculated after all data are available, often by scanning the dataset one or more times. Running statistics compute the same conceptual quantities during data arrival, updating the state after each new sample. When the update formulas are exact and implemented without numerical error, the final value obtained after processing all samples matches the batch result.

In practice, online computation may differ from batch due to floating-point arithmetic, particularly for variance-like measures that involve cancellation effects. For that reason, numerically stable update rules are an important component of running-statistic design.

1.3 State variables and update rules

A running statistic is defined by:

  1. A set of state variables that capture the information needed to update later, and
  2. Update rules that transform the previous state into a new state given the incoming value.

For example, to maintain a running mean, the state typically includes the current count and current mean. For running variance, additional state is required to track dispersion in a stable manner (often via an accumulated quantity related to squared deviations).

The core idea is that the update rule compresses the effect of the new observation into the state without storing the full sequence.

1.4 Numeric stability considerations

Many running statistics involve subtraction and squaring, which can amplify floating-point errors. Variance computation is especially sensitive because it effectively measures small differences between large terms.

To address this, implementations often use stable formulations (such as Welford-style updates) that track deviations directly rather than relying on naïve “sum of squares minus square of sum” patterns. Stability considerations also include:

  • Choosing appropriate data types (e.g., using double precision where needed)
  • Avoiding catastrophic cancellation
  • Keeping intermediate quantities within representable ranges to reduce overflow and underflow risk

2 Core Running Metrics

2.1 Running mean

The running mean is the average of all samples seen so far (or within a defined window, if used). It can be updated incrementally with fixed memory.

2.1.1 Incremental update formulas

Let \(n\) be the number of processed samples, \(\mu_n\) the mean after \(n\) samples, and \(x\) the next sample. The updated mean after \(n+1\) samples is: \[ \mu_{n+1} = \mu_n + \frac{x - \mu_n}{n+1}. \] This form avoids recomputing a sum over all past data and tends to be numerically stable because it uses the deviation \(x-\mu_n\), which often stays within a manageable magnitude.

2.1.1.1 Precision and overflow concerns

While the update above is typically stable, it still depends on floating-point precision. When processing extremely long streams, the fraction \(\frac{1}{n+1}\) can become too small to affect \(\mu_n\) in finite precision arithmetic, effectively freezing the mean. Additionally, if values are very large, the deviation term \(x-\mu_n\) may overflow if stored in limited-range types.

Practical mitigations include:

  • Using higher-precision floating-point types
  • Scaling inputs when appropriate (e.g., normalization)
  • Applying compensated summation techniques when a sum-based method is used (though for mean, the deviation update is often preferred)

2.2 Running variance and standard deviation

Running variance measures the spread of observed values. Because variance underlies many features and normalization steps, stable computation is critical.

2.2.1 Two-pass vs. one-pass approaches

A two-pass batch algorithm computes the mean first, then recomputes squared deviations from that mean. This can be accurate but requires storing or revisiting data. One-pass batch formulas exist but can be less stable due to cancellation in “sum of squares minus mean-squared” style computations.

Running variance is inherently one-pass over the stream, so stable single-pass algorithms are preferred.

2.2.2 Welford’s online algorithm

Welford’s method maintains a count, a running mean, and an accumulated quantity related to the sum of squared deviations. One common formulation tracks:

  • \(n\): number of samples
  • \(\mu\): running mean
  • \(M_2\): sum of squared deviations from the current mean

For each new sample \(x\):

  1. \(n \leftarrow n+1\)
  2. \(\delta = x - \mu\)
  3. \(\mu \leftarrow \mu + \delta/n\)
  4. \(\delta2 = x - \mu\)
  5. \(M_2 \leftarrow M_2 + \delta\cdot\delta2\)

After processing \(n\) samples, the variance can be reported as:

  • Population variance: \( \sigma^2 = M_2 / n \)
  • Sample variance (unbiased under common assumptions): \( s^2 = M_2 / (n-1) \) for \(n>1\)

Standard deviation is then the square root of the variance. The key benefit of Welford’s method is numerical robustness in floating-point arithmetic.

2.3 Running minimum and maximum

Running minimum and maximum track the smallest and largest values encountered so far. Their update rules are straightforward:

  • Update minimum: \(m_{\min} \leftarrow \min(m_{\min}, x)\)
  • Update maximum: \(m_{\max} \leftarrow \max(m_{\max}, x)\)

These statistics require only one stored value per metric plus a count if needed for rate or window logic. In windowed settings, however, min/max require more sophisticated handling because expired samples may have been extremal.

2.4 Running counts and rates

Running counts track how many samples have arrived. When samples are timestamped, rates can be computed as:

  • Count per unit time using a time horizon, or
  • Exponential decay weighting (if using exponentially weighted moving rates)

In streaming systems, rate definitions often specify whether time is measured in seconds, minutes, or event-time intervals, and whether the metric uses event counts or weighted quantities.

2.5 Running covariance and correlation (optional advanced metrics)

Covariance generalizes variance to pairs of variables, measuring how two quantities move together. Running covariance can be maintained similarly to variance by tracking means for each variable and an accumulated cross-deviation term.

Given streaming pairs \((x, y)\), an online covariance update maintains:

  • Means \(\mu_x, \mu_y\)
  • An accumulated cross term \(C\) representing sum of products of deviations from the means

Correlation is then computed as: \[ \rho = \frac{\text{cov}(x,y)}{\sigma_x \sigma_y}, \] where covariances and standard deviations come from the running estimates. Implementations must handle edge cases such as zero variance in one variable, which makes correlation undefined.

3 Rolling and Windowed Variants

3.1 Sliding window statistics

Sliding window statistics compute metrics over the most recent \(W\) samples (or a recent time interval). Unlike cumulative running statistics, the window “forgets” older observations.

3.1.1 Efficient window maintenance strategies

Because windowed statistics must both incorporate new samples and remove expired ones, naïvely recomputing from scratch is expensive. Efficient strategies depend on the statistic:

  • For sums and means, a running total with subtraction of expired values works well.
  • For variance, specialized maintenance is needed because removing data affects dispersion nontrivially.
  • For min/max, data structures must support efficient eviction of old extremal elements.

A common general approach uses auxiliary structures that enable updates in near-constant time per step.

3.1.2 Data structures for window updates

Popular data structures include:

  • Deques for maintaining candidates for window minimum and maximum in amortized constant time.
  • Balanced trees or heaps with lazy deletion (useful when duplicates occur and eviction must be handled correctly).
  • Two-level aggregations (chunking) where each chunk stores partial statistics and window updates combine chunk results.

For variance within windows, implementations may rely on maintaining both sums and sums of squares, or using more stable formulations that handle removal carefully.

3.2 Exponentially weighted moving statistics

Exponentially weighted moving statistics (EWMA/EW variance-like measures) discount older observations smoothly rather than sharply cutting them off at a window boundary. Each new sample receives a weight based on recency.

3.2.1 Choosing the decay factor

An EWMA update often has the form: \[ s_t = \alpha x_t + (1-\alpha)s_{t-1}, \] where \(0<\alpha\le 1\) controls responsiveness. Larger \(\alpha\) emphasizes recent values, while smaller \(\alpha\) yields smoother estimates. Selecting \(\alpha\) is often related to an effective memory length or desired half-life of influence.

3.2.2 Trade-offs: responsiveness vs. smoothness

Exponential weighting introduces a bias toward recent observations and typically reduces variance of the estimator compared with raw estimates from highly variable streams. However, too much smoothing may lag behind true changes. Too little smoothing can make the metric noisy. The best choice depends on the application’s time scale and tolerance for lag versus fluctuation.

3.3 Handling missing or irregular samples

In real streams, data can be missing or arrive at irregular intervals. Common approaches include:

  • Using event-time updates: update only when a new observation arrives, and possibly adjust decay based on elapsed time.
  • Interpreting missingness as absence: treat missing samples as unobserved rather than as zeros.
  • Carrying forward last-known estimates with explicit metadata.

For exponentially weighted methods, time-aware decay can scale the effective influence by the gap between timestamps, improving comparability across irregular sampling.

4 Quantiles and Distribution Summaries

4.1 Approximate quantiles in streams

Exact quantiles typically require access to the full sorted dataset or heavy memory. Streaming systems often use approximations that maintain compact summaries.

4.1.1 Rank-based sketch methods

Sketches approximate quantiles by tracking a summary structure that supports queries for ranks. Examples include:

  • t-digest style summaries that allocate more resolution in tails
  • Greenwald–Khanna style quantile sketches providing bounded error guarantees
  • Other rank/centroid aggregation techniques tuned for memory limits

These methods aim to provide good accuracy for quantile queries while using fixed or slowly growing memory.

4.1.2 Histogram and binning approaches

A histogram approach partitions the value range into bins and maintains bin counts incrementally. Quantiles are then derived by finding the bin where cumulative mass crosses the desired rank. Accuracy depends on bin width and how the range is handled:

  • Fixed bins require prior knowledge of scale
  • Adaptive bins re-bin as new values appear, increasing complexity
  • Hybrid approaches combine coarse bins with refinement near query points

Histogram methods are simple and fast but may yield discretization error.

4.2 Moment-based distribution summaries

Beyond mean and variance, additional moments (skewness, kurtosis) can summarize shape using incremental formulas. While moments do not directly provide quantiles, they offer a compact way to describe asymmetry and tail heaviness.

Moment estimates can be sensitive to outliers and may require stable update rules to avoid numerical issues, especially for higher-order moments.

4.3 Percentiles and confidence intervals (conceptual)

Conceptual interval estimates for percentiles in streaming settings require understanding both sampling variability and approximation error from the summary method. Because streaming quantile sketches may have algorithm-dependent errors, confidence intervals are often discussed in terms of:

  • Approximation error bounds of the sketch
  • Statistical uncertainty due to finite samples
  • Assumptions about stationarity or distributional stability

In practice, confidence intervals for streaming percentiles may be provided when the underlying method supports them, or they may be approximated using bootstrap-like resampling on stored summaries.

5 Algorithms and Implementation Patterns

5.1 Initialization and warm-up periods

Running statistics require initial conditions. Typical patterns include:

  • Start with \(n=0\) and update after the first observation.
  • For variance-like metrics, report undefined or zero until a minimum number of samples is available (e.g., variance requires at least two samples for sample variance).
  • For windowed and exponentially weighted methods, early estimates may be biased because less data has accumulated; some systems use warm-up periods or bias correction.

Initialization choices affect early behavior but do not usually change the long-run convergence if updates are correct.

5.2 Batch-to-stream migration considerations

When migrating an existing batch pipeline to streaming:

  • Replace full-dataset scans with state updates maintained per metric.
  • Verify whether the statistic’s definition changes (e.g., population vs. sample variance).
  • Ensure that data ordering assumptions are understood, especially when late-arriving events or replays occur.
  • Validate that normalization or feature scaling uses only information available at the time in the stream, to avoid leaking future data.

The goal is to preserve metric semantics while respecting streaming constraints.

5.3 Performance and memory complexity

Core running statistics usually use constant memory and constant update time per sample. Windowed statistics vary: sliding windows can incur higher overhead depending on the data structure and required operations (especially for min/max and quantiles).

Key performance considerations include:

  • Per-update CPU cost
  • Memory footprint for state and auxiliary structures
  • Whether the algorithm supports parallel processing and merging

5.4 Parallelism and merging partial statistics

Many running statistics can be merged across partitions, which enables parallel or distributed processing. For mean and variance, mergeability depends on storing compatible state variables (counts and accumulated deviation terms).

A typical strategy:

  1. Compute partial running statistics on separate shards or threads.
  2. Combine the partial states using merge formulas that yield the same result as processing the concatenated stream in exact arithmetic.

For quantiles, mergeability is method-dependent: some sketches support merging directly, while others require reprocessing or more complex reconciliation.

5.5 Testing correctness with edge cases

Correctness tests for running statistics commonly include:

  • Empty stream and single-sample stream handling
  • Duplicate values and constant streams (variance should be zero)
  • Very large magnitude values to check overflow behavior
  • Very large \(n\) to probe floating-point precision limits
  • Irregular timestamp sequences for time-aware decay or rate computations
  • Window boundary conditions (exactly \(W\) items, then \(W+1\), etc.)

Reference tests compare streaming outputs with batch computations under the same definitions, within a tolerance appropriate for floating-point differences.

6 Practical Applications

6.1 Monitoring and alert thresholds

Running metrics are often used to trigger alerts when signals deviate from normal behavior. Mean and variance can form the basis of thresholds (for example, identifying when a value strays several standard deviations from the running center). Windowed or exponentially weighted variants help adapt alerts to changing conditions.

In monitoring, choice of update speed and smoothing affects both false positives and missed detections, making parameter selection part of system tuning.

6.2 Real-time dashboards and telemetry

Dashboards commonly display live summaries such as average latency, rolling error rates, or recent maxima. Running statistics provide a compact view without storing full traces. Implementations typically balance freshness (recent changes should appear quickly) with stability (the display should not fluctuate excessively).

For telemetry pipelines, consistent definitions across services (same window size, same decay) are important so comparisons remain meaningful.

6.3 Online normalization and preprocessing

Online normalization uses running statistics to transform incoming data into a standardized scale. Examples include:

  • Standardizing features using running mean and variance.
  • Normalizing streaming metrics for downstream models or anomaly detection.

When the stream is non-stationary, windowed or exponentially weighted statistics can improve adaptation. However, normalization choices influence model behavior, especially early in the stream when estimates are still uncertain.

6.4 Drift detection and basic sanity checks

Drift detection can leverage changes in running means, variances, or distribution summaries. Conceptually, a system monitors whether incoming data statistics differ significantly from previously observed patterns. Running statistics support this by providing continual estimates and enabling comparisons over time.

Basic sanity checks also use running summaries—for instance, tracking min/max to catch sensor saturation, or verifying that variance does not collapse unexpectedly unless expected.

7 Common Pitfalls and Best Practices

7.1 Off-by-one and window boundary errors

Windowed metrics are prone to boundary mistakes, such as including \(W+1\) elements or removing one step too late. These errors can be subtle because they may only show up at specific stream lengths or when values arrive precisely at window edges.

Best practices include:

  • Clearly defining whether windows are inclusive or exclusive
  • Writing tests for transition points (when the window first fills and when each element expires)
  • Using consistent indexing conventions in code

7.2 Numerical drift and cancellation

Naïve variance computation can suffer from cancellation, especially when values are large and variance is small. Over long runs, minor floating-point inaccuracies can accumulate, causing drift.

To reduce this:

  • Use stable algorithms (e.g., Welford for variance)
  • Avoid subtracting nearly equal large quantities when possible
  • Consider compensated techniques or higher precision for sensitive metrics

7.3 Biased variance estimates

Variance can be reported as a population measure or as an unbiased sample estimator. Mixing these conventions inadvertently leads to systematic differences. In running systems, the confusion often arises because streaming APIs may default to one definition.

Best practices include documenting which estimator is used and keeping the definition consistent across batch and streaming implementations.

7.4 Dealing with outliers

Outliers can strongly affect mean and variance, and they can distort exponentially weighted summaries if they occur frequently. Approaches include:

  • Using robust alternatives (median-based or trimmed estimators when feasible)
  • Monitoring min/max alongside variance
  • Employing clipping or transformation strategies before applying standard running formulas

The choice depends on whether outliers represent genuine events or sensor artifacts.

7.5 Reproducibility in streaming order

Some distributed streaming systems process events out of order, which can change running statistics because update sequences differ in floating-point arithmetic and in window membership. Even when merge formulas exist, approximate quantile methods may yield slightly different outputs.

To improve reproducibility:

  • Ensure deterministic event ordering when required
  • Use mergeable sketches or state merges carefully
  • Define acceptable numeric tolerances in validation

8 Example Workflows (Lightweight)

8.1 Updating running mean/variance in pseudo-code

The following high-level pseudo-code illustrates Welford-style updates that maintain mean and variance-like state:

  • Initialize: \(n=0\), \(\mu=0\), \(M_2=0\)
  • For each new value \(x\):
  • \(n \leftarrow n+1\)
  • \(\delta \leftarrow x - \mu\)
  • \(\mu \leftarrow \mu + \delta/n\)
  • \(\delta2 \leftarrow x - \mu\)
  • \(M_2 \leftarrow M_2 + \delta\cdot\delta2\)
  • After the stream:
  • If \(n>1\): sample variance \(= M_2/(n-1)\)
  • If \(n>0\): population variance \(= M_2/n\)

This pattern updates both center and dispersion with constant memory.

8.2 Rolling average for smoothing noisy signals

A rolling average maintains the mean of the last \(W\) samples. One typical workflow:

  • Keep a queue of the last \(W\) values
  • Keep a running sum \(S\)
  • When a new value \(x\) arrives:
  • Add \(x\) to the queue and \(S\)
  • If the queue size exceeds \(W\), remove the oldest value \(y\) and set \(S \leftarrow S - y\)
  • Rolling average \(= S / \text{queue size}\)

If the queue is not yet full, the average is computed over the available samples until the warm-up completes.

8.3 Exponential moving average for quick trend detection

An exponentially weighted moving average tracks trends with a parameter \(\alpha\):

  • Initialize \(s \leftarrow x_1\) after the first sample (or use a small warm start)
  • For each next value \(x_t\):
  • \(s \leftarrow \alpha x_t + (1-\alpha)s\)
  • Use \(s\) as the smoothed signal and compare it with the raw value to detect changes

Smaller \(\alpha\) yields smoother behavior, while larger \(\alpha\) reacts more quickly to shifts.