Online Mean and Variance for Streaming Returns
You receive a stream of returns for $N$ instruments over $T$ days, delivered in mini-batches of $B$ days at a time. $N$ can be up to $10^4$ and $T$ up to $10^6$.
Design an algorithm that computes the exact sample mean vector $\hat{\mu} \in \mathbb{R}^N$ and diagonal sample variance vector $\hat{\sigma}^2 \in \mathbb{R}^N$ in a single pass using $O(N)$ memory, using Welford-style online updates and skipping missing values (None/NaN) per instrument.
Implement:
```python def stream_mean_var(batches, n_instruments): ... ```
batchesis a list of mini-batches; each mini-batch is a list of rows; each row has lengthn_instrumentsand holds either a number (that instrument's return that day) orNone(missing data).- For each non-
Nonevalue, update per-instrument count $n_j$, mean $\bar{x}_j$, and sum of squared deviations $M_{2,j}$; the sample variance is $M_{2,j}/(n_j-1)$. Every instrument is guaranteed at least 2 valid observations. - Return
[means, variances]: two lists of lengthn_instruments(means first, then sample variances).
Constraints: - $1 \le N \le 10^4$, $1 \le T \le 10^6$, $1 \le B \le T$ - Returns may contain None (missing data) - Only $O(N)$ memory allowed -- you cannot store the full $N \times T$ matrix
Example
stream_mean_var([[[1.0, 10.0], [3.0, None]], [[5.0, 20.0], [None, 30.0]]], 2) -> [[3.0, 20.0], [4.0, 100.0]]
Instrument 0 sees valid values 1, 3, 5 (mean 3, sample variance 4); instrument 1 sees 10, 20, 30 (mean 20, sample variance 100). The None entries are skipped so each instrument uses its own count.
Hints
- Think about how to compute variance without storing all the data -- what running quantities do you need beyond just the sum?
- Welford's algorithm avoids catastrophic cancellation by tracking the sum of squared deviations from the running mean, not the sum of squares minus the square of the sum.
- For NaN handling, maintain a per-instrument count $n_j$ so each instrument's mean and variance use only its valid observations. The update formulas are: $\delta = x - \bar{x}$, update $\bar{x}$, then $\delta_2 = x - \bar{x}_{\text{new}}$, and $M_2 \mathrel{+}= \delta \cdot \delta_2$.
Worked Solution
How to Think About It: You have more data than fits in memory, so you need incremental (online) statistics. The classic approach is Welford's algorithm, which tracks a running mean and a running sum of squared deviations (M2). The key subtlety is handling missing values (None) per-instrument: each instrument has its own valid count, so you maintain per-instrument counters.
Contract: Define stream_mean_var(batches, n_instruments). batches is a list of mini-batches; each mini-batch is a list of rows; each row has length n_instruments and holds either a number or None (missing). Process everything in a SINGLE pass with O(N) state, and return [means, variances] — two lists of length n_instruments (means first, then sample variances).
Algorithm: For each instrument j maintain n_j (valid count), mean_j, and M2_j (sum of squared deviations). For each non-None value x:
$$n_j \leftarrow n_j + 1,\quad \delta = x - \bar{x}_j,\quad \bar{x}_j \leftarrow \bar{x}_j + \frac{\delta}{n_j},\quad \delta_2 = x - \bar{x}_j,\quad M_{2,j} \leftarrow M_{2,j} + \delta\,\delta_2$$
None entries are skipped so different instruments can have different effective sample sizes (no imputation). The sample variance is M2_j / (n_j - 1) (Bessel-corrected); every instrument is guaranteed at least 2 valid observations.
Code:
```python def stream_mean_var(batches, n_instruments): n = [0] * n_instruments mean = [0.0] * n_instruments m2 = [0.0] * n_instruments for batch in batches: for row in batch: for j in range(n_instruments): x = row[j] if x is None: continue n[j] += 1 delta = x - mean[j] mean[j] += delta / n[j] delta2 = x - mean[j] m2[j] += delta * delta2 means = [mean[j] for j in range(n_instruments)] variances = [m2[j] / (n[j] - 1) for j in range(n_instruments)] return [means, variances] ```
Complexity: Time O(N*T) — each of the T rows costs O(N) to update every instrument. Space O(N) — three arrays of length N (count, mean, M2). The mini-batch size B does not affect total work.
Intuition
The naive formula for variance, $\text{Var}(X) = E[X^2] - (E[X])^2$, is numerically unstable because you are subtracting two large, nearly equal numbers. Welford's algorithm sidesteps this by tracking the sum of squared deviations from the current mean, which stays well-conditioned even for millions of observations. This is not just an academic concern -- in production quant systems processing tick data, the naive formula can produce negative variances due to floating-point errors.
The NaN handling is also practically important. In real returns data, instruments go ex-dividend, get halted, or simply have no trades on certain days. You want each instrument's statistics computed over its own valid data, not contaminated by imputation. Keeping a per-instrument count is the clean way to do this, and it falls out naturally from the online update structure.