8.2 随机变量、期望与方差：平均值之外还有分布
设两个接口的延迟服从下面两种离散模型：一种在 90 ms 与 110 ms 各占一半，另一种在 20 ms 的概率为 245/249，在 5000 ms 的概率为 4/249。两者均值都是 100 ms，波动却差得很远。Python 3 的精确分数可以直接核对：
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均值单位为 ms，方差单位为 ms²。这是人为构造的概率模型，不是某个服务的测量结果。
随机变量是函数
随机变量 X 把样本结果映射为数值：
X:Ω→ℝ抛两次硬币，X 可定义为正面次数：
HH→2, HT→1, TH→1, TT→0随机的是样本结果；X 是确定映射。
一般概率空间还要求 X 可测：例如对每个实数 x，集合 {ω:X(ω)≤x} 都属于事件族 𝔽，这样 CDF 中的概率才有定义。
PMF、PDF 与 CDF
离散随机变量的概率质量函数：
p_X(x)=P(X=x)若分布有概率密度 f_X，区间概率由积分给出，单点概率严格为 0。并非所有无原子分布都有密度，分布也可能同时含离散质量和连续部分。CDF 可以统一描述这些情况。
累积分布函数适用于两者：
F_X(x)=P(X≤x)CDF 单调不减、右连续，并从 0 趋近 1。分位数可由 CDF 定义，但离散分布或平坦区间可能使分位数不唯一，需要采用约定。
本课对 0<q<1 采用广义逆约定 Q(q)=inf{x:F_X(x)≥q}。样本分位数还可能插值，必须同时说明算法；下面的示例使用不插值的 nearest-rank。
几个基础分布
Bernoulli
一次成功/失败：
X∈{0,1}, P(X=1)=p
E[X]=p
Var(X)=p(1-p)Binomial
n 次独立、同成功率 Bernoulli 试验的成功次数：
P(X=k)=C(n,k)p^k(1-p)^(n-k)
E[X]=np
Var(X)=np(1-p)若每次成功率不同或试验相关，就不是普通 Binomial 模型。
Geometric
对独立同成功率试验，设 0<p≤1，X 统计直到首次成功的总试验次数：P(X=k)=(1−p)^(k−1)p,k=1,2,...，E[X]=1/p，Var(X)=(1−p)/p²。若统计成功前失败数 Y=X−1，期望为 (1−p)/p，方差不变。p=0 时不会成功，不属于这个有限期望模型。
Poisson
常用于固定区间内稀疏事件计数，参数 λ：
P(X=k)=e^{-λ}λ^k/k!
E[X]=Var(X)=λ上式定义单个计数变量的 Poisson 分布，参数为 λ≥0。把它用作齐次 Poisson 到达过程的窗口计数时，还需要独立增量、固定速率等过程假设。真实请求有周期、突发和自激，不能只因“是计数”就套这个过程模型。
期望的线性性
离散情形：
E[X]=Σ_x xP(X=x)最重要的性质：
E[aX+bY+c]=aE[X]+bE[Y]+c不要求 X、Y 独立，但这里假设 E|X|、E|Y| 有限，避免未定义的无穷相减。
用指示变量计数很方便。等概率随机排列 n≥1 个不同元素，令 I_i 表示第 i 个元素仍在原位：
E[I_i]=1/n固定点总数 X=ΣI_i：
E[X]=ΣE[I_i]=n·1/n=1无需计算各指示变量之间的依赖。
方差度量波动
Var(X)=E[(X-E[X])²]
=E[X²]-E[X]²标准差：
σ_X=√Var(X)线性变换：
Var(aX+b)=a²Var(X)两个变量之和：
Var(X+Y)=Var(X)+Var(Y)+2Cov(X,Y)独立变量协方差为 0，于是方差相加；反方向一般不成立，零协方差不保证独立。
当两个标准差都有限且非零时，相关系数归一化线性关联，但相关为 0 也可能存在强非线性关系。
尾部和分位数
P99 延迟是使约 99% 观测不超过该值的分位数估计。它不等于“最慢 1% 的平均值”，也不说明 99% 每时每刻都满足。
平均值对极端值敏感；中位数更稳健；高分位展示尾部，但需要足够样本，且聚合方式会影响结果。
不能把各机器 P99 简单平均得到全局 P99。正确方法通常是合并可加的分布摘要或原始直方图，再计算总体分位数；摘要精度和桶边界也要说明。
一个小型反例：A 记录 99 个 1 ms 请求，B 记录 1 个 1000 ms 请求。以合并后样本的第 ceil(0.99n) 个次序统计量定义 P99：
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实例权重不同只是问题之一；即使按请求数加权平均实例分位数，通常也得不到全局分位数。这里的小样本用于核对定义，不足以精确估计长期尾延迟。
Markov 与 Chebyshev 不等式
对非负随机变量 X 和 a>0：
P(X≥a)≤E[X]/a这是 Markov 不等式，只用均值给尾部上界，通常较松。
若 μ=E[X]、0<σ²=Var(X)<∞ 且 k>0：
P(|X-μ|≥kσ)≤1/k²这是 Chebyshev 不等式，不要求正态分布。更多分布假设或独立性可以得到更紧的 Chernoff/Hoeffding 界。
若 σ=0，则 X=μ 几乎必然成立，应单独处理，不能把 kσ=0 代进带 ≥ 的公式。一般写法 P(|X−μ|≥ε)≤Var(X)/ε² 对任意 ε>0 都可用，也涵盖零方差。
上界不等于预测实际尾概率；它提供在有限信息下保证不会超过的范围。
随机算法的成本
期望运行时间：
E[T]不等于每次都在该时间内完成。还应看尾概率、最坏情况和随机性来源。
对不同键，逐次均匀随机选枢轴的标准快速排序期望 Θ(n log n)，最坏仍为 Θ(n²)。随机打乱若有偏或可被攻击者预测，期望分析的假设可能失效。
完成检查
- 写出两次抛硬币正面数的 PMF 与 CDF；
- 用指示变量求随机选 5 人中某类成员的期望数；
- 构造同均值、不同方差的两个离散分布；
- 解释为什么全局 P99 不能由实例 P99 平均得到；
- 用 Markov 或 Chebyshev 给一个尾概率上界，并说明它为什么可能很松。