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

Two interfaces have the same average latency of 100 ms, one consistently stays between 90 and 110 ms, the other spends most of its time at 20 ms but occasionally spikes to 5 seconds. The same mean does not imply equivalent user experience or capacity risk; the full distribution of the random variable must be examined.

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.

PMF, PDF, and CDF

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

p_X(x) = P(X = x)

For continuous random variables, we use a probability density function f_X(x); the probability at a single point is typically zero, and probabilities over intervals are obtained via integration.

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.

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

The number of trials until the first success in independent repeated experiments. Two conventions exist: "counting from 1" (successes) or "counting failures from 0." The expected value differs by 1 in these cases, always clarify which convention is being used before applying.

Poisson

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

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

It relies on assumptions such as independent increments and constant rate. Real-world requests often exhibit tides, bursts, and self-exciting behavior, do not assume a Poisson distribution simply because the outcome is a count.

Expected Linearity

Discrete case:

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

The most important property:

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

No requirement that X and Y be independent.

Indicator variables make counting convenient. For a random permutation of n 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.

The correlation coefficient normalizes linear relationships, 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.

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.

If the variance is finite:

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.

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.

Randomized quicksort has an expected Θ(n log n) under a suitable randomization model, 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