Katkat
Back

Compute and Explain Mean and Variance

AmazonApplied Scientist · Onsite
MediumApplied ScientistOnsiteStatistics & Math

Last updated

This question tests your understanding of statistical estimators for mean and variance, the derivation of Bessel's correction, catastrophic cancellation in naive computations, and numerically stable single-pass algorithms like Welford's.

Scenario

You are designing an internal metric aggregation library for an e-commerce platform that processes streaming payment latencies and large product price datasets. The pipeline requires computing sample statistics in real time across distributed workers.

Questions to Address

1. Estimator Formulas and Unbiasedness

  • State the mathematical definitions for sample mean x_bar, biased sample variance s_biased^2 (divided by N), and unbiased sample variance s_unbiased^2 (divided by N - 1).
  • Prove or clearly show why dividing by N yields an estimator with negative bias E[s_biased^2] = ((N - 1) / N) * sigma^2, and explain conceptually why Bessel's correction (N - 1) corrects for this bias.

2. Numerical Stability in Single-Pass Computation

  • A common textbook shortcut computes variance in a single pass using the identity: Var(X) = E[X^2] - (E[X])^2, or programmatically: sum_sq / N - (sum / N)^2.
  • Explain the phenomenon of catastrophic cancellation that occurs with this identity when data values are large with small variance (for example, values like [1000000001, 1000000002, 1000000003]).
  • Describe an online, numerically stable single-pass algorithm (such as Welford's algorithm) for updating the mean and running sum of squared differences M2 as new data points arrive. Provide the exact recurrence relations.

3. Edge Cases and Cross-Platform Floating-Point Discrepancies

  • Detail how your implementation should handle edge cases: N = 0, N = 1, and datasets where all inputs are identical.
  • Explain why floating-point variance values computed in Python, C++, and Java might not be bit-for-bit identical even on the identical dataset, referencing IEEE 754 precision, compiler optimizations (such as fused multiply-add / FMA), and intermediate register widths (such as x87 80-bit vs SSE/AVX 64-bit).

Hints

Hint 1

To show that the naive sample variance is biased, expand `E[(X_i - x_bar)^2]` and use the fact that `Var(x_bar) = sigma^2 / N`.

Hint 2

Catastrophic cancellation occurs when subtracting two nearly equal, very large floating-point numbers, leading to a loss of leading significant bits.

Hint 3

Welford's algorithm updates the running mean using `mean_k = mean_{k-1} + (x_k - mean_{k-1}) / k` and maintains `M2_k = M2_{k-1} + (x_k - mean_{k-1}) * (x_k - mean_k)`.

Follow-up questions

  • How would you extend Welford's method to compute variance in parallel across multiple worker nodes (Chan's algorithm)?
  • How does the choice between 32-bit (single precision) and 64-bit (double precision) floats alter the point at which catastrophic cancellation becomes problematic?
  • How would you adapt running variance estimation to maintain an exponentially weighted moving variance (EWMA) over streaming time-series data?