8.2 Random Variables, Expectation, and Variance: Beyond the Mean

Consider two discrete latency models: one is equally likely to take 90 or 110 ms; the other takes 20 ms with probability 245/249 and 5000 ms with probability 4/249. Both means are 100 ms, with very different variability. Python 3 exact fractions verify the moments:

from fractions import Fraction

def moments(distribution):
    mean = sum(value * probability for value, probability in distribution)
    variance = sum((value - mean)**2 * probability for value, probability in distribution)
    return mean, variance

stable = [(90, Fraction(1, 2)), (110, Fraction(1, 2))]
spiky = [(20, Fraction(245, 249)), (5000, Fraction(4, 249))]
for distribution in (stable, spiky):
    mean, variance = moments(distribution)
    print(float(mean), float(variance))
# 100.0 100.0
# 100.0 392000.0

Means are in ms and variances in ms². These are constructed probability models, not measurements from a service.

Random Variables Are Functions

A random variable X maps sample outcomes to numerical values:

X:Ω→ℝ

For example, when flipping a coin twice, X could represent the number of heads:

HH→2, HT→1, TH→1, TT→0

The randomness lies in the sample outcome; X is a deterministic mapping.

On a general probability space, X must be measurable: for every real x, the set {ω:X(ω)≤x} must belong to 𝔽, so its CDF probability is defined.

PMF, PDF, and CDF

For discrete random variables, the probability mass function is defined as:

p_X(x) = P(X = x)

If a distribution has a probability density f_X, interval probabilities are integrals and every single-point probability is zero. Not every atomless distribution has a density, and distributions may mix discrete mass with a continuous part. A CDF describes all these cases.

The cumulative distribution function applies to both discrete and continuous cases:

F_X(x) = P(X ≤ x)

The CDF is non-decreasing, right-continuous, and approaches 0 as x goes to negative infinity and 1 as x goes to positive infinity. Quantiles can be defined using the CDF, but for discrete distributions or flat regions, quantiles may not be unique; special conventions are required to resolve ambiguity.

For 0<q<1, use the generalized inverse Q(q)=inf{x:F_X(x)≥q}. Sample quantiles may also interpolate, so specify their algorithm; the example below uses non-interpolating nearest rank.

Several Basic Distributions

Bernoulli

A single success/failure trial:

X ∈ {0,1}, P(X=1) = p
E[X] = p
Var(X) = p(1-p)

Binomial

n independent trials with identical success probability, counting the number of successes:

P(X=k) = C(n,k) p^k (1-p)^(n-k)
E[X] = np
Var(X) = np(1-p)

This is not a standard binomial model if the success probabilities vary across trials or if the trials are dependent.

Geometric

For independent trials with fixed success probability 0<p≤1, let X count all trials through the first success: P(X=k)=(1−p)^(k−1)p,k=1,2,..., E[X]=1/p, and Var(X)=(1−p)/p². Counting failures before success instead gives Y=X−1, with mean (1−p)/p and the same variance. At p=0, success never occurs and this finite-mean model does not apply.

Poisson

Commonly used for counting rare events over a fixed interval, parameterized by λ:

P(X=k) = e^{-λ} λ^k / k!
E[X] = Var(X) = λ

The formula defines a single Poisson-distributed count with λ≥0. Interpreting it as a window count from a homogeneous Poisson arrival process adds assumptions such as independent increments and constant rate. Real requests exhibit cycles, bursts, and self-excitation; being a count is insufficient to justify that process model.

Linearity of Expectation

Discrete case:

E[X] = Σ_x xP(X=x)

The most important property:

E[aX + bY + c] = aE[X] + bE[Y] + c

Independence is unnecessary, but assume finite E|X| and E|Y| here to avoid undefined differences of infinities.

Indicator variables make counting convenient. For a uniformly random permutation of n≥1 distinct elements, define I_i as an indicator that the i-th element remains in its original position:

E[I_i] = 1/n

Total number of fixed points X=ΣI_i:

E[X] = Σ E[I_i] = n · (1/n) = 1

No need to compute dependencies among the indicator variables.

Variance as a Measure of Fluctuation

Var(X) = E[(X - E[X])²]
       = E[X²] - E[X]²

Standard deviation:

σ_X = √Var(X)

Linear transformation:

Var(aX + b) = a²Var(X)

Variance of the sum of two variables:

Var(X + Y) = Var(X) + Var(Y) + 2Cov(X, Y)

The covariance between independent variables is zero, so their variances add directly. This property does not hold in reverse: zero covariance does not guarantee independence.

With finite, nonzero standard deviations, the correlation coefficient normalizes linear association, but a correlation of zero can still indicate strong nonlinear dependencies.

Tail and Quantiles

P99 latency is an estimate of the 99th percentile, meaning that approximately 99% of observed requests have response times no greater than this value. It does not equal the average of the slowest 1% of requests, nor does it imply that 99% of requests are always within this bound.

The mean is sensitive to outliers; the median is more robust; higher percentiles reveal the tail behavior, but require sufficient sample size, and the resulting values can be influenced by how the data is aggregated.

You cannot simply average P99 values across machines to obtain a global P99. The correct approach typically involves combining additive distribution summaries or raw histograms, then computing the overall percentile. Both the accuracy of the summary and the bucket boundaries must be clearly documented.

For a small counterexample, A records 99 requests at 1 ms and B records one at 1000 ms. Define pooled P99 as order statistic ceil(0.99n):

from math import ceil

def nearest_rank(values, q):
    if not values or not 0 < q <= 1:
        raise ValueError("nonempty sample and 0 < q <= 1 required")
    return sorted(values)[ceil(q * len(values)) - 1]

a, b = [1] * 99, [1000]
print((nearest_rank(a, .99) + nearest_rank(b, .99)) / 2)  # 500.5
print(nearest_rank(a + b, .99))                         # 1

Unequal instance weights are only part of the problem: weighting instance quantiles by request count generally still fails to produce the global quantile. This small sample checks the definition, not long-run tail accuracy.

Markov and Chebyshev Inequalities

For non-negative random variables X and a>0:

P(X≥a) ≤ E[X]/a

This is Markov's inequality, which provides an upper bound on the tail probability using only the mean, typically a loose bound.

For μ=E[X], 0<σ²=Var(X)<∞, and k>0:

P(|X - μ| ≥ kσ) ≤ 1/k²

This is Chebyshev's inequality, which does not require normality. Tighter bounds like Chernoff or Hoeffding inequalities can be derived under additional assumptions such as distributional properties or independence.

If σ=0, then X=μ almost surely; treat it separately rather than inserting kσ=0 into the ≥ formula. The general form P(|X−μ|≥ε)≤Var(X)/ε² for ε>0 also handles zero variance.

These upper bounds do not equal the actual tail probabilities; instead, they guarantee a maximum that cannot be exceeded given only limited information.

Cost of Randomized Algorithms

Expected running time:

E[T]

does not mean the algorithm completes within that time every time. It's also important to consider tail probabilities, worst-case scenarios, and the source of randomness.

For distinct keys, standard quicksort with uniformly random pivots has expected Θ(n log n) time, though the worst-case remains Θ(n²). If the random shuffling is biased or predictable to an adversary, the assumptions underlying the expected-time analysis may fail.

Completion Checklist

1. Derive the PMF and CDF of the number of heads when flipping a fair coin twice.
2. Use indicator variables to compute the expected number of members of a certain category in a randomly selected group of five people.
3. Construct two discrete distributions with the same mean but different variances.
4. Explain why the global 99th percentile cannot be obtained by simply averaging individual instance 99th percentiles.
5. Use Markov's or Chebyshev's inequality to provide an upper bound on a tail probability, and explain why this bound might be loose.

References

• MIT OpenCourseWare: Introduction to Probability