[toc]
$$Pr[X\ge k E[X]]\le \frac{1}{k}, \forall k \ge 1$$
证明: 反证假设 $Pr[X\ge k E[X]] > 1/k$, 则 $EX=EPr[X\ge k E[X]]>\frac{1}{k}\cdot kEX = EX$, 矛盾, 证毕
$$Pr\left[|X-EX|^2\ge t\cdot Var[X]\right]\le \frac{1}{t}$$
证明: 不妨设 $Z=(X-EX)^2$, 则 $EZ=Var[X]$, $Pr\left[Z\ge t\cdot EZ\right]\le \frac{1}{t}$ 即转为 Markov Inequation.
n 个相互独立随机变量 $X_1,\cdots,X_n\in{0,1}, \forall X_i=\left{\begin{array}{ll}0 & 1-p_i \ 1 & p_i\end{array}\right., p_i\in[0,1]$
令 $S=\sum\limits_{i=1}^nX_i, \mu=E[S], \bar{\mu}=\frac{1}{n}\mu=E[\frac{1}{n}S]$. 则, $\forall \delta>0$, $$Pr[\frac{1}{n}S\notin\bar{\mu}\pm\delta]\le 2e^{-2n\cdot\delta^2}$$
证明:
$\begin{aligned}
Pr(\frac{1}{n}S>\bar{\mu}+\delta)&=Pr(S>\mu+n\delta)\
&=Pr(e^{\lambda S}>e^{\lambda(\mu + n\delta)}), \lambda > 0\
&=Pr(e^{\lambda S}>\frac{e^{\lambda(\mu + n\delta)}}{Ee^{\lambda S}}\cdot Ee^{\lambda S})\
(Markov\ Inequation) & \le\frac{Ee^{\lambda S}}{e^{\lambda(\mu + n\delta)}} \
\end{aligned}$
这里 $E[e^{\lambda S}]=\prod\limits_{i=1}^nE[e^{\lambda X_i}]=\prod\limits_{i=1}^n(p_ie^\lambda+(1-p_i))\le \prod\limits_{i=1}^ne^{\lambda^2/\delta+\lambda p_i}\le e^{\frac{n}{\delta}\lambda^2+\lambda\mu}$
进而
$\begin{aligned}
Pr(\frac{1}{n}S>\bar{\mu}+\delta)&\le \frac{e^{\frac{n}{\delta}\lambda^2+\lambda\mu}}{e^{\lambda(\mu+\delta\mu)}}, let\ \lambda=4\delta\
&=e^{-2\delta^2n}
\end{aligned}$
所以 $Pr(\frac{1}{n}S\ge\bar{\mu}+\delta)\le e^{-2\delta^2n}$
同理: $Pr(\frac{1}{n}S\le\bar{\mu}-\delta)\le e^{-2\delta^2n}$
故 $Pr[\frac{1}{n}S\notin\bar{\mu}\pm\delta]\le 2e^{-2\delta^2 n}$
$\forall\ iid\ X_i\in[a,b]$
$$Pr[|\bar{X}-E\bar{X}| > \delta]\le 2e^{-\frac{2n\cdot\delta^2}{(b-a)^2}}$$
鞅(Martingale)序列: $Z_0,\cdots,Z_n,\cdots$, 有 $\forall Z_i, E[Z_i|Z_0,\cdots,Z_{i-1}]=z_{i-1}$
对于上述鞅序列, 若同时 $\forall i,|Z_i-Z_{i-1}|\le C_i, C_i>0$, 则 $\forall t >0$ 有
$$Pr(Z_n-Z_0\ge t)\le e^{-\frac{t^2}{2\sum\limits_{i=1}^n C_i^2}}$$
证明:
$\begin{aligned}
Pr[Z_n-Z_0\ge t]&=Pr[e^{\lambda(Z_n-Z_0)}\ge e^{\lambda t}]\
&\le \frac{1}{e^{\lambda t}}E[e^{y\lambda(Z_n-Z_0)}]\
&=\frac{1}{e^{\lambda t}}E[e^{\lambda(Z_n-Z_{n-1}+Z_{n-1}-Z_{n-2}+\cdots+Z_1-Z_0)}]\
&=\frac{1}{e^{\lambda t}}E[e^{\lambda(Z_n-Z_{n-1})}e^{\lambda(Z_{n-1}-Z_{n-2})}\cdots e^{\lambda(Z_1-Z_0)}]\
&=\frac{1}{e^{\lambda t}}E_{Z_0\sim Z_{n-1}}((\prod_{i=1}^{n-1}e^{\lambda(Z_i-Z_{i-1})})\cdot E[e^{\lambda(Z_n-Z_{n-1})}|Z_0,\cdots,Z_{n-1}])\
(Hoeffding\ Lemma)&\le\frac{1}{e^{\lambda t}}E_{Z_0\sim Z_{n-1}}((\prod_{i=1}^{n-1}e^{\lambda(Z_i-Z_{i-1})})\cdot e^{\frac{\lambda^2C_n^2}{2}})\
&\le\frac{1}{e^{\lambda t}} e^{\sum\limits_{i=1}^n\frac{\lambda^2C_i^2}{2}}\quad,let\ \lambda=\frac{t}{\sum\limits_{i=1}^nC_i^2}\
&=e^{-\frac{t^2}{2\sum\limits_{i=1}^n C_i^2}}
\end{aligned}$
这里用到的 Hoeffding Lemma 为: 若 $EX=\eta, a\le X\le b$, 则 $\forall \lambda >0, E[e^{\lambda X}]\le e^{\lambda\eta+\frac{\lambda^2(b-a)^2}{2}}$
- 从 U 随机取多少样本才能保证以概率 $\ge 1-\eta$, 得到 $\ge 1$ 样本 $\in V$
设抽取 m 个样本为 S
$Pr(S\cap V\not= \varnothing)=1-(1-\tau)^m\ge1-\eta$
$\Rightarrow m\ge\frac{\log 1/\eta}{\log 1/(1-\eta)}\approx\frac{1}{\eta}\log\frac{1}{\eta}$
-
$E[|S\cap V|]=\tau|S|$, 给定某一个参数 $\delta \in (0,1)$, 求 $Pr(||S\cap V|-\tau|S||<\delta\tau|S|)\ge_____$
|S| 个相互独立随机变量 $X_1,X_2,\cdots,X_{|S|}$, $\forall i, x_i=\left{\begin{array}{ll}0 & ,\notin V \ 1 & ,\in V\end{array}\right.$, 则 $E\left[\sum\limits_{i=1}^{|S|}X_i\right]=\tau|S|$
此时可以使用 Chernoff Bounds: $\forall x_i=\left{\begin{array}{ll}0 & ,1-\tau \ 1 & ,\tau \end{array}\right.$,
则 $Pr(||S\cap V|-\tau|S||<\delta\tau|S|)=Pr\left(\left||S\cap V|-\sum\limits_{i=1}^{|S|}X_i\right|<\delta\tau|S|\right)\le1-2\exp(-2(1\cdot\delta^2\tau^2|S|^2))=1-2\exp(-2(\delta^2\tau^2|S|^2))$