马尔可夫不等式（Markov's inequality）
\(X\ge0\) 为非负随机变量，\(t>0\) 为常数，则有
\[\begin{align*} \mathbb P(X\ge t)\le{\mathbb EX\over t} \end{align*} \]证：
指示器函数 \(I\lbrace A\rbrace=\begin{cases}1 &\text{if }A\\0&\text{else}\end{cases}\)
在随机变量中获取一个样本 \(X_0\)，
- 若 \(X_0\ge t\)，则 \(X_0/t\ge1=I\lbrace X_0\ge t\rbrace\)，
- 若 \(X_0<t\)，则 \(X_0/t\ge0=I\lbrace X_0\ge t\rbrace\)，
即 \(X/t\ge I\lbrace X\ge t\rbrace\)
\[\begin{align*} \mathbb P(X\ge t)=\mathbb EI\lbrace X\ge t\rbrace\le\mathbb E\frac Xt={\mathbb EX\over t} \end{align*} \]切比雪夫不等式（Chebyshev's inequality）
\(X\) 为随机变量，\(t>0\) 为常数，则有
\[\begin{align*} \mathbb P(\vert X-\mathbb EX\vert\ge t)\le{\operatorname{Var}(X)\over t^2} \end{align*} \]证：
将 \((X-\mathbb EX)^2\) 和 \(t^2\) 代入马尔可夫不等式，得 \(\mathbb P[(X-\mathbb EX)^2\ge t^2]\le{\mathbb E(X-\mathbb EX)^2\over t^2}\)。整理即得到切比雪夫不等式。
推论：
设 \(X_i,i=1,2,\ldots,n\) 与 \(X\) 独立同分布，\(\bar X:=\frac1n\sum_i^nX_i\)，则 \(\operatorname{Var}(\bar X)=\operatorname{Var}(X)/n\)
\[\begin{align*} \mathbb P(\vert\bar X\vert\ge t)=\mathbb P\left(\left\vert\frac1n\sum_i^nX_i\right\vert\ge t\right)\le{\operatorname{Var}(X)\over nt^2} \end{align*} \]矩生成函数（moment generating function）
定义：\(M_X(\lambda):=\mathbb E\exp(\lambda X)\)
若 \(X_1,\ldots,X_n\) 相互独立，则
\[\begin{align*} M_{X_1+\cdots+X_n}(\lambda)=\prod_{k=0}^nM_{X_k}(\lambda) \end{align*} \]证：
\[\begin{align*} M_{X_1+\cdots+X_n}(\lambda)&=\mathbb E\exp\left(\sum_{k=0}^n\lambda X_i\right)\\ &=\mathbb E\prod_{k=0}^n\exp\left(\lambda X_i\right)\\ &=\prod_{k=0}^n\mathbb E\exp\left(\lambda X_i\right)=\prod_{k=0}^nM_{X_k}(\lambda) \end{align*} \]切诺夫界（Chernoff bounds）
\(X\) 为随机变量，\(t\ge0\) 为常数，则有
\[\begin{align*} \mathbb P(X-\mathbb EX\ge t)&\le\min_{\lambda\ge0}{\mathbb E\exp[\lambda(X-\mathbb EX)]\over\exp(\lambda t)}=\min_{\lambda\ge0}M_{X-\mathbb EX}(\lambda)\cdot\exp(-\lambda t)\\ \mathbb P(\mathbb EX-X\ge t)&\le\min_{\lambda\ge0}{\mathbb E\exp[\lambda(\mathbb EX-X)]\over\exp(\lambda t)}=\min_{\lambda\ge0}M_{\mathbb EX-X}(\lambda)\cdot\exp(-\lambda t) \end{align*} \]证：
将 \(\exp[\lambda(X-\mathbb EX)]\) 和 \(\exp(\lambda t)\) 代入马尔可夫不等式，得 \(\mathbb P(\exp[\lambda(X-\mathbb EX)]\ge\exp(\lambda t))\le{\mathbb E\exp[\lambda(X-\mathbb EX)]\over\exp(\lambda t)}\)。令 \(\mathbb P(\exp[\lambda(X-\mathbb EX)]\ge\exp(\lambda t))\equiv\mathbb P(X-\mathbb EX\ge t)\)，则要求 \(\lambda>0\)。对于 \(\lambda=0\)，显然成立。因此选择右项对于 \(\lambda\ge0\) 的下界，整理即得到切诺夫界。
例：
正态分布，对于 \(X\sim\mathcal N(\mu,\sigma^2)\) 只需要在计算中加上常数 \(\mu\)，因此只考虑 \(\mathcal N(0,\sigma^2)\)
\[\begin{align*} X&\sim\mathcal N(0,\sigma^2)\\[0.8em] \mathbb E\exp(\lambda X)&\xlongequal{\text{Taylor}}\sum_{k=0}^\infty{\lambda^k\mathbb EX^k\over k!}\\ &=\sum_{k=0}^\infty{(2k-1)!!\lambda^{2k}\sigma^{2k}\over(2k)!}\\ &=\sum_{k=0}^\infty{(\lambda\sigma)^{2k}\over(2k)!!}\\ &=\sum_{k=0}^\infty\frac1{k!}\left({\lambda^2\sigma^2\over2}\right)^k\\ &=\exp\left({\lambda^2\sigma^2\over2}\right)\\[0.5em] \mathbb P(X\ge t)&\le\min_{\lambda\ge0}M_X(\lambda)\cdot\exp(-\lambda t)\\ &=\min_{\lambda\ge0}\exp\left({\lambda^2\sigma^2\over2}-\lambda t\right)\\ &\xlongequal{\lambda\leftarrow t/\sigma^2}\exp\left(-{t^2\over2\sigma^2}\right) \end{align*} \]多次伯努利试验
\[\begin{align*} X_k&\sim B(1,p_k)\\[0.8em] \mathbb E\exp(\lambda X)&=p\exp\lambda+(1-p)\\ &=1+p(\exp\lambda-1)\\ &\le\exp[p(\exp\lambda-1)]\\[0.5em] \mathbb P\left(\sum_{k=1}^nX_k\ge t\right)&\le\min_{\lambda\ge0}M_{\sum_{k=1}^nX_k}(\lambda)\cdot\exp(-\lambda t)\\ &\le\min_{\lambda\ge0}\exp\left((\exp\lambda-1)\sum_{k=0}^np_k-\lambda t\right)\\ &=\begin{cases} \exp(t-\mu)\left(\frac\mu t\right)^t&\mu:=\sum_{k=1}^np_k,\lambda\leftarrow\ln(t/\mu),t\ge\mu\\ 1&\lambda\leftarrow0,t<\mu \end{cases} \end{align*} \]可以看出，将 \(M_X(\lambda)\) 化作 \(M_X(\lambda)\le\exp(f_X(\lambda))\) 的形式是很方便的，其中 \(f_X(\lambda)\) 是参数与 \(X\) 有关的函数。
霍夫丁引理（Hoeffding's lemma）
\(X\in[a,b]\) 为有界随机变量，对 \(\lambda\in\mathbb R\)，有
\[\begin{align*} \mathbb E\exp[\lambda(X-\mathbb EX)]\le\exp\left(\lambda^2(b-a)^2\over8\right) \end{align*} \]证明：两种方法
若定义在 \([a,b]\) 上的 \(f(x)\) 为凸函数，则有
\[\begin{align*} f(x)&\le{b-x\over b-a}f(a)+{x-a\over b-a}f(b)\\ \end{align*} \]将 \(x\) 视为随机变量 \(X\) 加上期望得到
\[\begin{align*} \mathbb Ef(X)&\le{b-\mathbb EX\over b-a}f(a)+{\mathbb EX-a\over b-a}f(b)\\ \end{align*} \]-
令 \(X\leftarrow X-\mathbb EX\)，即变量减去期望，令期望变为零 \(\mathbb EX=0\)。选择函数 \(f(X)=\exp(\lambda X),\lambda\ge0\)。
并考虑将 \(M_X(\lambda)\) 化为 \(M_X(\lambda)\le\exp f_X(\lambda)\) 的形式。得到
\[\begin{align*} &&\mathbb E\exp(\lambda X)&\le{be^{\lambda a}-ae^{\lambda b}\over b-a}\\ &&&=e^{\lambda a}{b-ae^{\lambda(b-a)}\over b-a}\\ \text{let}&&f(\lambda)&:=\ln\left(e^{\lambda a}{b-ae^{\lambda(b-a)}\over b-a}\right)\\ &&&=\lambda a-\ln(b-a)+\ln(b-ae^{\lambda(b-a)})\\ \text{then}&&f'(\lambda)&=b\left(1-{b-a\over b-ae^{\lambda(b-a)}}\right)\\ &&f''(\lambda)&=(b-a)^2{-abe^{\lambda(b-a)}\over[b-ae^{\lambda(b-a)}]^2}\\ \text{because}&&(c+d)^2&\ge4cd,\ \forall c,d\in\mathbb R\\[1em] \text{therefore}&&[b-ae^{\lambda(b-a)}]^2&\ge-4abe^{\lambda(b-a)}\\[1em] &&f''(\lambda)&\le\frac{(b-a)^2}4\\ &&f(\lambda)&=f(0)+\lambda f'(0)+\frac12\lambda^2f^"(\theta\lambda),\text{ where }0\le\theta\le1\\ &&&\le\frac18\lambda^2(b-a)^2\\[1em] \text{finally}&&\mathbb E\exp(\lambda X)&\le\exp f(\lambda)\le\exp\left(\lambda^2(b-a)^2\over8\right) \end{align*} \] -
选择函数 \(f(X)=X^2\)，\(\operatorname{Var}(X)=\mathbb EX^2-\mathbb E^2X\)。得到
\[\begin{align*} \operatorname{Var}(X)&=\mathbb EX^2-\mathbb E^2X\\ &\le{ba^2-ab^2+(b^2-a^2)\mathbb EX\over b-a}-\mathbb E^2X\\ &=-ab+(b+a)\mathbb EX-\mathbb E^2X\\ &\le\frac{(b-a)^2}4\\ \end{align*} \]\(\mathbb EX=(a+b)/2\) 时取等。
我们引入对数矩生成函数 \(f(\lambda)=\ln M_X(\lambda)=\ln\mathbb E\exp(\lambda X)\)，用 \(t\) 代替 \(\lambda\) 表示和上面的方法不同。
\[\begin{align*} &&f'(t)&=\frac1{\mathbb E\exp(tX)}{\mathrm d\over\mathrm dt}\mathbb E\exp(tX)\\ &&&={\mathbb E[X\exp(tX)]\over\mathbb E\exp(tX)}\\ &&f''(t)&={\mathbb E[X^2\exp(tX)]\mathbb E\exp(tX)-\mathbb E^2[X\exp(tX)]\over\mathbb E^2\exp(tX)}\\ \text{let}&&E&:=\mathbb E\exp(tX)\\ \text{then}&&f''(t)&=\mathbb E\left[X^2{\exp(tX)\over E}\right]-\mathbb E\left[X{\exp(tX)\over E}\right]^2\\ \text{let}&&p'(Y)&:={\exp(tY)\over E}p(Y),\text{ and }\int_a^bp'(y)\mathrm dy\equiv1\\ \text{then}&&f''(t)&=\operatorname{Var}(Y)\le\frac{(b-a)^2}4\\ \text{therefore}&&f(t)&=f(0)+tf'(0)+\frac t2f''(\theta t),\text{ where }0\le\theta\le1\\ &&&\le\frac18t(b-a)^2\\ \text{finally}&&\mathbb E\exp(t X)&=\exp f(t)\le\exp\left(t^2(b-a)^2\over8\right) \end{align*} \]其中使用了概率分布为 \(\exp(tY)p(Y)/E\) 的新变量 \(Y\)，且 \(Y\) 同样满足 \(Y\in[a,b]\)。
总之用不同的方法得出，\(M_X(\lambda)\le\exp(f_X(\lambda))\) 形式的结果。
霍夫丁不等式（Hoeffding's inequality）
\(X_i,i=1,\ldots,n\) 为独立有界随机变量，满足 \(X_i\in[a,b],-\infty<a\le b<\infty\)，令 \(\mu:=\frac1n\sum_{k=1}^n(X_i-\mathbb EX_i)\)，\(t\ge0\) 为常数，则
\[\begin{align*} \mathbb P(\mu\ge t)&\le\exp\left(-{2nt^2\over(b-a)^2}\right)\\ \mathbb P(\mu\le-t)&\le\exp\left(-{2nt^2\over(b-a)^2}\right)\\ \end{align*} \]证：
在霍夫丁引理的基础上计算切诺夫界，只计算第一项，第二项同理
\[\begin{align*} \mathbb P(\mu\ge t)&=\mathbb P\left(\sum_{k=1}^n(X_i-\mathbb EX_i)\ge nt\right)\\ &\le\min_{\lambda\ge0}\mathbb E\left[\exp\left(\lambda\sum_{k=1}^n(X_i-\mathbb EX_i)\right)\right]\exp(-\lambda nt)\\ &=\min_{\lambda\ge0}\left(\prod_{k=1}^n\mathbb E\exp(\lambda(X_i-\mathbb EX_i))\right)\exp(-\lambda nt)\\ &\le\min_{\lambda\ge0}\left(\prod_{k=1}^n\exp\left(\lambda^2(b-a)^2\over8\right)\right)\exp(-\lambda nt)\\ &=\min_{\lambda\ge0}\exp\left({n\lambda^2(b-a)^2\over8}-\lambda nt\right)\\ &\xlongequal{\lambda\leftarrow4t/(b-a)^2}\exp\left(-{2nt^2\over(b-a)^2}\right) \end{align*} \] 标签：mathbb,le,霍夫丁,Hoeffding,align,Lemma,EX,exp,lambda From： https://www.cnblogs.com/violeshnv/p/17338430.html