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)$、$n\ge 1$ 时它只给出 $\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从指数矩与 Markov 不等式推导尾界，给出独立 Bernoulli 和的乘法形式、KL 形式及适用条件。再利用指数矩得到指数衰减。

非负性不可省略。设 $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 不等式就变成一个确定性的计数结论：对 $n\ge 1$ 个非负数 $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从指数矩与 Markov 不等式推导尾界，给出独立 Bernoulli 和的乘法形式、KL 形式及适用条件。集中处理，矩母函数理路矩母函数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 可证明依概率一致；单个 e-value 若在零假设下满足期望不超过一，Markov 给出的只是该次抽样规则下的尾界。要在任意停时读取证据，还须建立e-process 或检验上鞅理路检验鞅与 e-processTest martingale · Test supermartingale · e-process · 检验上鞅区分固定时刻的 e 值与可在停时读取的证据过程，并用非负检验上鞅构造随时有效检验。的过程保证，再以Ville 不等式理路Ville 不等式Ville's inequality · Ville inequality非负上鞅在无限时间内达到给定水平的概率，由初始期望除以该水平控制。控制整条路径的越界概率；每个固定时刻分别有均值界并不足够。

在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把随机比特作为额外输入并分析输出正确率或运行时间分布的算法。分析同样离不开它：若非负整数值运行时间满足 $0<\mathbb{E}[T]<\mathrm{\infty }$，在 $\lceil 2\mathbb{E}[T]\rceil$ 步后截断，超时概率至多为 $1/2$，于是得到有限时间的 Monte Carlo 算法；$\mathbb{E}[T]=0$ 时则几乎必然立即结束。