Markov 不等式

期望是一份"数值乘质量"的总预算：若 $X$ 以概率 $p$ 达到 $a$ 以上，仅这一部分就至少消耗 $pa$ 的预算，于是 $pa\le \mathbb{E}[X]$，移项即得不等式。一行证明是同一件事的点态说法：$a{\mathbf{1}}_{\{X\ge a\}}\le X$ 处处成立，两边取期望即可。它之所以基本，在于只动用一阶矩、对分布形状不作任何假设——这既是优点（普适、零成本）也是弱点（往往很松）。真正的威力在"换元再用"：对 $|X|$、$(X-\mu {)}^2$、$e^{tX}$ 这些精心挑选的非负变换套用同一不等式，就能把高阶矩或指数矩的知识兑换成越来越紧的尾部界。Markov 不等式因此是整个尾界工具箱的母模板。

等号可以取到：设 $X$ 以概率 $p$ 取值 $a$、以概率 $1-p$ 取值 $0$，则 $\mathbb{E}[X]=pa$，$\mathbb{P}(X\ge a)=p=\mathbb{E}[X]/a$。这说明只握有一阶矩信息时，该界不可改进。一个量纲化的读法：若某地人均年收入为 $5$ 万元，则年收入不低于 $50$ 万元的人口比例至多为 $10\mathrm{\%}$。作为松弛程度的对照：$X\sim \mathrm{Bin}(n,1/2)$ 时它只给出 $\mathbb{P}(X\ge 3n/4)\le 2/3$，一个不随 $n$ 改善的常数；Chebyshev 不等式公理库Chebyshev 不等式Chebyshev's inequality随机变量偏离均值至少给定距离的概率由方差除以距离平方控制。利用方差得到 $O(1/n)$，Chernoff 方法公理库Chernoff 方法与 Chernoff 界Chernoff method · Chernoff bounds对随机变量施加指数变换并优化参数，以获得指数级尾概率上界。再利用指数矩得到指数衰减。

非负性不可省略。设 $X$ 以各 $1/2$ 的概率取 $\pm 10$：$\mathbb{E}[X]=0$，形式套用将得出 $\mathbb{P}(X\ge 10)\le 0$，与真值 $1/2$ 矛盾。对可能取负值的变量应改用 $|X|$、正部 $X_{+}$ 或其他非负替身。此外阈值必须为正；且当 $a\le \mathbb{E}[X]$ 时右端不小于 $1$，不含任何信息——Markov 不等式只在"阈值远超均值"的尾部区域才有内容。

把随机变量取成有限表中均匀抽到的一项，Markov 不等式就变成一个确定性的计数结论：对非负数 $x_1,\dots ,x_n$ 与 $a>0$，满足 $x_i\ge a$ 的指标个数至多为

例如数据 $0,1,2,9$ 的总和为 $12$，阈值取 $6$ 时，Markov 只保证至多有 $12/6=2$ 项越过阈值，实际只有一项。这个例子清楚展示了界所使用的信息：它只知道总质量，不知道质量如何分布，因此可以安全但不精细。对运行时间、队列长度或组合对象计数使用 Markov 时，本质上做的也是同一个“总预算除以单个坏事件最低成本”的估计。

概率论的偏差不等式常从选择不同的非负变换开始：平方变换给出 Chebyshev 不等式公理库Chebyshev 不等式Chebyshev's inequality随机变量偏离均值至少给定距离的概率由方差除以距离平方控制。；指数变换及其参数优化由Chernoff 方法公理库Chernoff 方法与 Chernoff 界Chernoff method · Chernoff bounds对随机变量施加指数变换并优化参数，以获得指数级尾概率上界。集中处理，矩母函数公理库矩母函数Moment-generating function · MGF在存在邻域内以 E[e^{tX}] 编码随机变量各阶矩的函数。在其中提供尾部信息。PAC-Bayes 泛化界公理库PAC-Bayes 泛化界PAC-Bayes bound · PAC-Bayes proof template以先验到数据依赖后验的 KL 散度支付换测度代价，将先验下的指数矩控制转成同时覆盖所有 Gibbs 后验的泛化证书。的常见证明也先控制先验平均的指数矩，再用 Markov 把期望控制变成关于训练样本的高概率事件；随后还要做 change-of-measure，不能把 Markov 的一阶松界本身当作最终样本复杂度。

证明依概率收敛公理库依概率收敛Convergence in probability随机变量偏离极限超过任意正阈值的概率趋于零。的标准套路——“某非负量的期望趋于零”经 Markov 立刻升级为“该量依概率趋于零”。

统计中，若某非负估计误差的期望趋零，Markov 可证明依概率一致；若对 likelihood ratio 或 e-value 在零假设下控制期望，它还能产生随时有效的尾界。这样的保证通常较松，而且期望对象、条件历史与停止规则必须明确，不能把一次平均控制解释为精确 p 值。

在Monte Carlo 积分公理库Monte Carlo 积分Monte Carlo integration · Monte Carlo quadrature将积分改写为随机变量期望，以独立样本均值估计并用方差和概率假设量化随机误差。中，它能从非负估计误差的一阶矩给出不依赖分布形状的失败概率基线，但通常比使用方差或有界性的界更松。组合与随机图中的一阶矩方法公理库一阶矩方法First moment method用坏事件计数的期望小于一或 Markov 型界证明好对象存在。是它的整数值特例：非负整数值 $X$ 满足 $\mathbb{P}(X\ge 1)\le \mathbb{E}[X]$，期望趋零即目标结构几乎必然不存在。随机算法公理库随机化算法Randomized algorithm把随机比特作为额外输入并分析输出正确率或运行时间分布的算法。分析同样离不开它：仅由期望运行时间 $\mathbb{E}[T]$ 即得“在 $2\mathbb{E}[T]$ 步内结束的概率至少 $1/2$”，这是把 Las Vegas 算法截断为 Monte Carlo 算法的标准论证。