吾妻不等式

十月 19, 2023

在機率論中，吾妻不等式（Azuma's inequality）是关于差有界的鞅的不等式，给出了值的集中情况，以日本數學家吾妻一興（英语：Kazuoki Azuma）（Azuma Kazuoki）命名^[1]。

陈述编辑

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

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

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

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

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

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

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

吾妻不等式的简单例子编辑

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

定义 $X_{n}=\sum _{i=1}^{n}{F_{i}}$ ，这是一个鞅，而且满足 $|X_{k}-X_{k-1}|\leq 1$ ，允许使用吾妻不等式。具体来说，我们得到

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

如果令 $t$ 正比于 $n$ ，则这个不等式告诉我们，尽管 $X_{n}$ 的最大可能值随 $n$ 线性增大，但是概率随 $n$ 指数衰减。

如果令 $t={\sqrt {2n\ln {n}}}$ ，得到：

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

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

备注编辑

谢尔盖·伯恩施坦于1937年证明了一个类似的但条件更弱的不等式^[3]。见伯恩施坦不等式。

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

另见编辑

集中不等式

参考资料编辑

^ 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.
^ 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.
^ 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)
^ 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.

十月 19, 2023

吾妻不等式, 在機率論中, azuma, inequality, 是关于差有界的鞅的不等式, 给出了值的集中情况, 以日本數學家吾妻一興, 英语, kazuoki, azuma, azuma, kazuoki, 命名, 目录, 陈述, 的简单例子, 备注, 另见, 参考资料陈述, 编辑设, displaystyle, nbsp, 为鞅, 或上鞅, displaystyle, nbsp, 几乎必然成立, 则对任意正整数n, displaystyle, nbsp, 与正实数t, displaystyle, nbsp, . 在機率論中吾妻不等式 Azuma s inequality 是关于差有界的鞅的不等式给出了值的集中情况以日本數學家吾妻一興英语 Kazuoki Azuma Azuma Kazuoki 命名 1 目录 1 陈述 2 吾妻不等式的简单例子 3 备注 4 另见 5 参考资料陈述编辑设 X k displaystyle X k nbsp 为鞅或上鞅且 X k X k 1 lt c k displaystyle X k X k 1 lt c k nbsp 几乎必然成立则对任意正整数N displaystyle N nbsp 与正实数t displaystyle t nbsp P X N X 0 t exp t 2 2 k 1 N c k 2 displaystyle P X N X 0 geq t leq exp frac t 2 2 sum k 1 N c k 2 nbsp 当 X k displaystyle X k nbsp 是下鞅时对称地有 P X N X 0 t exp t 2 2 k 1 N c k 2 displaystyle P X N X 0 leq t leq exp frac t 2 2 sum k 1 N c k 2 nbsp 若 X k displaystyle X k nbsp 是鞅同时使用以上两个不等式并利用布尔不等式可得 P X N X 0 t 2 exp t 2 2 k 1 N c k 2 displaystyle P X N X 0 geq t leq 2 exp frac t 2 2 sum k 1 N c k 2 nbsp 对Doob鞅使用吾妻不等式得到McDiarmid不等式 2 常见于随机算法的分析中吾妻不等式的简单例子编辑设F i displaystyle F i nbsp 是一列独立且同分布的随机变量代表了抛硬币的结果 1代表正面 1代表反面正反面出现的概率相等定义X n i 1 n F i displaystyle X n sum i 1 n F i nbsp 这是一个鞅而且满足 X k X k 1 1 displaystyle X k X k 1 leq 1 nbsp 允许使用吾妻不等式具体来说我们得到P X n gt t exp t 2 2 n displaystyle P X n gt t leq exp frac t 2 2n nbsp 如果令t displaystyle t nbsp 正比于n displaystyle n nbsp 则这个不等式告诉我们尽管X n displaystyle X n nbsp 的最大可能值随n displaystyle n nbsp 线性增大但是概率随n displaystyle n nbsp 指数衰减如果令t 2 n ln n displaystyle t sqrt 2n ln n nbsp 得到 P X n gt 2 n ln n 1 n displaystyle P X n gt sqrt 2n ln n leq 1 n nbsp 这意味着超过2 n ln n displaystyle sqrt 2n ln n nbsp 的概率随n displaystyle n to infty nbsp 而趋于0 备注编辑谢尔盖伯恩施坦于1937年证明了一个类似的但条件更弱的不等式 3 见伯恩施坦不等式 Hoeffding对独立变量证明了这个结果而不是鞅的差并且也注意到做一些小调整这个结果对鞅的差也是成立的 4 另见编辑集中不等式参考资料编辑 Azuma K 1967 Weighted Sums of Certain Dependent Random Variables PDF Tohoku Mathematical Journal 19 3 357 367 doi 10 2748 tmj 1178243286 MR 0221571 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 Bernstein Sergei N 1937 Na opredelennyh modifikaciyah neravenstva Chebisheva On certain modifications of Chebyshev s inequality Doklady Akademii Nauk SSSR 俄语 17 6 275 277 vol 4 item 22 in the collected works 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 取自 https zh wikipedia org w index php title 吾妻不等式 amp oldid 68777025, 维基百科，wiki，书籍，书籍，图书馆，

文章

，阅读，下载，免费，免费下载，mp3，视频，mp4，3gp， jpg，jpeg，gif，png，图片，音乐，歌曲，电影，书籍，游戏，游戏。