# 吾妻不等式

## 陈述

${\displaystyle \{X_{k}\}}$ （或上鞅），且${\displaystyle |X_{k}-X_{k-1}| 几乎必然成立。则对任意正整数${\displaystyle N}$ 与正实数${\displaystyle t}$

${\displaystyle P(X_{N}-X_{0}\geq t)\leq \exp {\frac {-t^{2}}{2\sum _{k=1}^{N}{c_{k}^{2}}}}}$

${\displaystyle \{X_{k}\}}$ 是下鞅时，对称地有：

${\displaystyle P(X_{N}-X_{0}\leq -t)\leq \exp {\frac {-t^{2}}{2\sum _{k=1}^{N}{c_{k}^{2}}}}}$

${\displaystyle \{X_{k}\}}$ 是鞅，同时使用以上两个不等式并利用布尔不等式可得：

${\displaystyle P(|X_{N}-X_{0}|\geq t)\leq 2\exp {\frac {-t^{2}}{2\sum _{k=1}^{N}{c_{k}^{2}}}}}$

Doob鞅使用吾妻不等式得到McDiarmid不等式[2]，常见于随机算法的分析中。

## 吾妻不等式的简单例子

${\displaystyle F_{i}}$ 是一列独立且同分布的随机变量，代表了抛硬币的结果（+1代表正面，-1代表反面，正反面出现的概率相等）。

${\displaystyle P(X_{n}>t)\leq \exp {\frac {-t^{2}}{2n}}}$

${\displaystyle P(X_{n}>{\sqrt {2n\ln n}})\leq 1/n}$

## 备注

Hoeffding对独立变量证明了这个结果，而不是鞅的差，并且也注意到做一些小调整，这个结果对鞅的差也是成立的[4]

## 参考资料

1. ^ Azuma, K. (1967). "Weighted Sums of Certain Dependent Random Variables" (PDF). Tôhoku Mathematical Journal. 19 (3): 357–367. doi:10.2748/tmj/1178243286. MR 0221571.
2. ^ McDiarmid, C. (1989). "On the method of bounded differences". Surveys in Combinatorics. London Math. Soc. Lectures Notes 141. Cambridge: Cambridge Univ. Press. pp. 148–188. MR 1036755.
3. ^ Bernstein, Sergei N. (1937). На определенных модификациях неравенства Чебишева [On certain modifications of Chebyshev's inequality]. Doklady Akademii Nauk SSSR (俄语). 17 (6): 275–277. (vol. 4, item 22 in the collected works)
4. ^ Hoeffding, W. (1963). "Probability inequalities for sums of bounded random variables". Journal of the American Statistical Association. 58 (301): 13–30. doi:10.2307/2282952. JSTOR 2282952. MR 0144363.