马尔可夫不等式, 切比雪夫不等式, 大数定律

防盗https://www.cnblogs.com/setdong/p/17325420.html

1. Markov’s inequality

Theorem: $X$ 为非负随机变量, 且 $\mathbb{E}[X]<\infty$. 那么对于任意 $t>0$ 有
P[X≥tE[X]]≤1t\\mathbb{P}[X\\geq t\\mathbb{E}[X]]\\leq\\frac{1}{t} P[X≥tE[X]]≤t1​
或对于任意的 $ϵ>0$ 有
P[X≥ϵ]≤E[X]ϵ\\mathbb{P}[X\\geq\\epsilon]\\leq\\frac{\\mathbb{E}[X]}{\\epsilon} P[X≥ϵ]≤ϵE[X]​
证明, 以上两式等价, 这里证第一个:

由定义有
P[X≥tE[X]]=∑x:x≥tE[X]P[X=x]\\mathbb{P}[X\\geq t\\mathbb{E}[X]]=\\sum_{x:x\\geq t\\mathbb{E}[X]}\\mathbb{P}[X=x] P[X≥tE[X]]=x:x≥tE[X]∑​P[X=x]
对于$x\ge t\mathbb{E}[X]$ 部分, 有 xtE[X]≥1\\frac{x}{t\\mathbb{E}[X]}\\geq 1tE[X]x​≥1, 所以
P[X≥tE[X]]≤∑x:x≥tE[X]P[X=x]xtE[X]\\mathbb{P}[X\\geq t\\mathbb{E}[X]]\\leq\\sum_{x:x\\geq t\\mathbb{E}[X]}\\mathbb{P}[X=x]\\frac{x}{t\\mathbb{E}[X]} P[X≥tE[X]]≤x:x≥tE[X]∑​P[X=x]tE[X]x​
对于$x<t\mathbb{E}[X]$ 部分, 有 P[X=x]xtE[X]≥0\\mathbb{P}[X=x]\\frac{x}{t\\mathbb{E}[X]}\\geq 0P[X=x]tE[X]x​≥0 , 所以加上这些非负部分, 有:
P[X≥tE[X]]≤∑xP[X=x]xtE[X]=E[X]tE[X]=1t\\mathbb{P}[X\\geq t\\mathbb{E}[X]]\\leq\\sum_{x}\\mathbb{P}[X=x]\\frac{x}{t\\mathbb{E}[X]}=\\frac{\\mathbb{E}[X]}{t\\mathbb{E}[X]}=\\frac{1}{t} P[X≥tE[X]]≤x∑​P[X=x]tE[X]x​=tE[X]E[X]​=t1​

2. Chebyshev’s inequality

Theorem: $X$ 为随机变量, 且 $\text{Var}[X]<\infty$ (方差). 那么对于任意 $t>0$ 有
P[∣X−E[X]∣≥tVar[X]12]≤1t2\\mathbb{P}[|X-\\mathbb{E}[X]|\\geq t\\text{Var}[X]^{\\frac{1}{2}}]\\leq\\frac{1}{t^2} P[∣X−E[X]∣≥tVar[X]21​]≤t21​
或对于任意$ϵ>0$ 有
P[∣X−E[X]∣≥ϵ]≤Var[X]ϵ2\\mathbb{P}[|X-\\mathbb{E}[X]|\\geq \\epsilon]\\leq\\frac{\\text{Var}[X]}{\\epsilon^2} P[∣X−E[X]∣≥ϵ]≤ϵ2Var[X]​
证明:

首先有
P[∣X−E[X]∣≥tVar[X]12]=P[(X−E[X])2≥t2Var[X]]\\mathbb{P}[|X-\\mathbb{E}[X]|\\geq t\\text{Var}[X]^{\\frac{1}{2}}]=\\mathbb{P}[(X-\\mathbb{E}[X])^2\\geq t^2\\text{Var}[X]] P[∣X−E[X]∣≥tVar[X]21​]=P[(X−E[X])2≥t2Var[X]]
然后对上式右侧应用 Markov’s inequality, 其中$X$ 是 (X−E[X])2(X-\\mathbb{E}[X])^2(X−E[X])2, $ϵ$ 是 t2Var[X]2t^2\\text{Var}[X]^2t2Var[X]2
P[(X−E[X])2≥t2Var[X]]≤E[(X−E[X])2]t2Var[X]=1t2\\mathbb{P}[(X-\\mathbb{E}[X])^2\\geq t^2\\text{Var}[X]]\\leq \\frac{\\mathbb{E}[(X-\\mathbb{E}[X])^2]}{t^2\\text{Var}[X]}=\\frac{1}{t^2} P[(X−E[X])2≥t2Var[X]]≤t2Var[X]E[(X−E[X])2]​=t21​
其中 E[(X−E[X])2]=Var[X]\\mathbb{E}[(X-\\mathbb{E}[X])^2]=\\text{Var}[X]E[(X−E[X])2]=Var[X] 为方差的定义.

3. Weak law of large numbers

Theorem: (Xn)n∈N(X_n)_{n\\in\\mathbb{N}}(Xn​)n∈N​ 是一列独立的随机变量, 它们有相同的期望 $\mu$ 和方差 σ2>∞\\sigma^2>\\inftyσ2>∞. Xˉn=1n∑i=1nXi\\bar{X}_n=\\frac{1}{n}\\sum_{i=1}^n X_iXˉn​=n1​∑i=1n​Xi​ 为均值. 那么对于任意的 $ϵ>0$ 有
lim⁡n→∞P[∣Xˉn−μ∣≥ϵ]=0\\lim_{n\\rightarrow\\infty}\\mathbb{P}[|\\bar{X}_n-\\mu|\\geq\\epsilon]=0 n→∞lim​P[∣Xˉn​−μ∣≥ϵ]=0
证明:

已知变量是独立的, 根据期望和方差的特性有,
E[Xˉn]=∑i=1nμn=μVar[Xˉn]=∑i=1nσ2n2=σ2n\\mathbb{E}[\\bar{X}_n]=\\sum_{i=1}^n \\frac{\\mu}{n}=\\mu\\\\ \\text{Var}[\\bar{X}_n]=\\sum_{i=1}^n \\frac{\\sigma^2}{n^2}=\\frac{\\sigma^2}{n} E[Xˉn​]=i=1∑n​nμ​=μVar[Xˉn​]=i=1∑n​n2σ2​=nσ2​
对上式使用 Chebyshev’s inequality, 其中 t=ϵ/Var[Xˉn]12t=\\epsilon/\\text{Var}[\\bar{X}_n]^{\\frac{1}{2}}t=ϵ/Var[Xˉn​]21​, 有
P[∣Xˉn−μ∣≥ϵ]≤σ2nϵ2\\mathbb{P}[|\\bar{X}_n-\\mu|\\geq\\epsilon]\\leq\\frac{\\sigma^2}{n\\epsilon^2} P[∣Xˉn​−μ∣≥ϵ]≤nϵ2σ2​
所以当 $n$ 趋于无穷时, 概率趋于 $0$. 可以理解为样本均值依概率收敛于期望值.
防盗https://www.cnblogs.com/setdong/p/17325420.html