Markov Inequality

定义 Definition

马尔可夫不等式：概率论中的基本不等式。对任意非负随机变量 \(X \ge 0\) 和任意 \(a>0\)，有
\[ \Pr(X \ge a)\le \frac{\mathbb{E}[X]}{a}. \] 它常用于在缺少分布细节时，对“随机变量取得很大值的概率”给出上界。另有更一般形式：若 \(g\) 为非负且单调递增函数，则
\[ \Pr(X \ge a)\le \frac{\mathbb{E}[g(X)]}{g(a)}. \]

发音 Pronunciation (IPA)

/ˈmɑːr.kɔːf ˌɪn.ɪˈkwɒl.ə.ti/（BrE）
/ˈmɑːr.kɔːf ˌɪn.ɪˈkwɑː.lə.t̬i/（AmE）

例句 Examples

If \(X\) is nonnegative, Markov inequality gives an upper bound on \(P(X \ge a)\).
如果 \(X\) 是非负的，马尔可夫不等式可以给出 \(P(X \ge a)\) 的上界。

In analyzing randomized algorithms, Markov inequality is often used to show that the probability of an unusually large running time is small compared with the expected time.
在分析随机算法时，马尔可夫不等式常用来说明：运行时间异常偏大的概率相对其期望值而言是很小的。

词源 Etymology

“Markov”来自俄国数学家安德烈·马尔可夫（Andrey Markov）的姓氏；“inequality”意为“不等式”。该不等式属于概率论早期的核心工具之一，常作为进一步结果（如切比雪夫不等式、集中不等式等）的基础或出发点。

相关词 Related Words

• Chebyshev
• Inequality
• Expectation
• Probability
• Random Variable
• Tail Bound
• Concentration
• Jensen

文学与经典著作 Literary Works

• Probability: Theory and Examples（Rick Durrett）：在基础不等式与尾界（tail bounds）部分使用并讨论马尔可夫不等式。
• A First Course in Probability（Sheldon Ross）：作为概率论入门的重要工具出现，用于给出概率上界。
• Alon & Spencer: The Probabilistic Method：在概率方法与随机结构分析中频繁使用马尔可夫不等式作为基本估计手段。