查看“吾妻不等式”的源代码

在概率论中，'''吾妻不等式'''（Azuma's inequality）是关于差有界的鞅的不等式，给出了值的集中情况，以{{le|吾妻一兴|Kazuoki Azuma}}（Azuma Kazuoki）命名<ref>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.</ref>。

== 陈述 ==
设<math>\{X_k\}</math>为[[鞅 (概率论)|鞅]]（或[[鞅|上鞅]]），且<math>|X_k-X_{k-1}|<c_k</math>[[几乎必然]]成立。则对任意正整数<math>N</math>与正实数<math>t</math>，

<math>P(X_N-X_0\ge t)\le\exp{\frac{-t^2}{2\sum_{k=1}^N{c_k^2}}}</math>

当<math>\{X_k\}</math>是下鞅时，对称地有：

<math>P(X_N-X_0\le -t)\le\exp{\frac{-t^2}{2\sum_{k=1}^N{c_k^2}}}</math>

若<math>\{X_k\}</math>是鞅，同时使用以上两个不等式并利用[[布尔不等式]]可得：

<math>P(|X_N-X_0|\ge t)\le 2\exp{\frac{-t^2}{2\sum_{k=1}^N{c_k^2}}}</math>

对[[Doob鞅]]使用吾妻不等式得到McDiarmid不等式<ref>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.</ref>，常见于[[随机化算法|随机算法]]的分析中。

== 吾妻不等式的简单例子 ==
设<math>F_i</math>是一列独立且同分布的随机变量，代表了抛硬币的结果（+1代表正面，-1代表反面，正反面出现的概率相等）。

定义<math>X_n=\sum_{i=1}^n{F_i}</math>，这是一个鞅，而且满足<math>|X_k-X_{k-1}|\le 1</math>，允许使用吾妻不等式。具体来说，我们得到

<math>P(X_n>t)\le\exp{\frac{-t^2}{2n}}</math>

如果令<math>t</math>正比于<math>n</math>，则这个不等式告诉我们，尽管<math>X_n</math>的'''最大'''可能值随<math>n</math>线性增大，但是概率随<math>n</math>[[指数衰减]]。

如果令<math>t=\sqrt{2n\ln{n}}</math>，得到：

<math>P(X_n>\sqrt{2n\ln n})\le 1/n</math>

这意味着超过<math>\sqrt{2n\ln{n}}</math>的概率随<math>n\to\infty</math>而趋于0。

== 备注 ==
[[谢尔盖·纳塔诺维奇·伯恩施坦|谢尔盖·伯恩施坦]]于1937年证明了一个类似的但条件更弱的不等式<ref>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)</ref>。见[[伯恩施坦不等式]]。

Hoeffding对独立变量证明了这个结果，而不是鞅的差，并且也注意到做一些小调整，这个结果对鞅的差也是成立的<ref>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.</ref>。

== 另见 ==

* [[集中不等式]]

== 参考资料 ==
<references />

[[Category:概率不等式]]
[[Category:鞅论]]