$$\newcommand{\bbR}{\mathbb{R}} \newcommand{\calG}{\mathcal{G}}$$

$$\newcommand{\rmd}{\,\mathrm{d}}$$

随机高斯向量的单位模引理与正交性定理

预备定理

Markov 不等式

$X$为非负随机变量, $\varepsilon>0$，$\mu = E(X), \sigma^2 = V(X)$, 则

$$P(|X-\mu|\geq \varepsilon)\leq \frac{\sigma^2}{\varepsilon^2}$$

$\mathbf{Proof}:$

\begin{aligned} \sigma^2 &= \int_{-\infty}^{\infty}(x-\mu)^2p(x)\rmd x\\ &\geq \int_{|x-\mu|\geq \varepsilon}(x-\mu)^2p(x)\rmd x\\ &\geq \varepsilon^2 \int_{|x-\mu|\geq \varepsilon}p(x)\rmd x\\ &=\varepsilon^2 P(|x-\mu|\geq\varepsilon) \end{aligned}

即

$$P(|x-\mu|\geq \varepsilon)\leq \frac{\sigma^2}{\varepsilon^2}$$

Cramér-Chernoff方法

$\forall \lambda > 0$, 有

$$|x-\mu|\geq \varepsilon\Longleftrightarrow e^{\lambda |x-\mu|}\geq e^{\lambda \varepsilon}$$

因此有

$$P(|x-\mu|\geq \varepsilon)=P(e^{\lambda |x-\mu|}\geq e^{\lambda \varepsilon})\leq e^{-\lambda a}\mathbb{E}(e^{\lambda |x-\mu|})\Longleftrightarrow P(|x-\mu|\geq \varepsilon)\leq \min_{\lambda>0}e^{-\lambda a}\mathbb{E}(e^{\lambda |x-\mu|})$$

从而可以求解最优的概率$P_{max}$以及对应的$\lambda_0$, 这个上界称为Chernoff Bound

Key Concept

随机高斯向量定义为

\calG=\left\{u\in \bbR^n\Big | u\sim \mathcal{N}(0,\frac{1}{n}I_n)\right\}

单位模引理

\forall u\in \calG,\forall \varepsilon \in (0,1), P(|\|u\|^2-1|\geq \varepsilon)\leq 2\exp(-\frac{\varepsilon^2 n}{8})

$\mathbf{Proof}:$
由Cramér-Chernoff方法

$$P(|\|u\|^2-1|\geq \varepsilon )\leq \min_{\lambda>0}e^{-\lambda\varepsilon}E(e^{\lambda|\|u\|^2-1|})$$

当$\|u\|^2\geq 1$时：

$$P(\|u\|^2-1\geq \varepsilon )=P(\|u\|^2\geq 1+\varepsilon)\leq\min_{\lambda>0}e^{-\lambda(\varepsilon +1)}\mathbb{E}(e^{\lambda\|u\|^2})$$

\begin{aligned} \mathbb{E}(e^{\lambda\|u\|^2})&=\mathbb{E} (e^{\lambda \sum u_i ^2})\\ &=\prod_{i=1}^n \mathbb{E}(e^{\lambda u_i^2})\\ &=\prod_{i=1}^n \int_{-\infty}^{\infty}\frac{\sqrt{n}}{\sqrt{2\pi}}\exp (-\frac{nu_i^2}{2})\exp (\lambda u_i^2)\rmd u_i\\ &=\prod_{i=1}^n \int_{-\infty}^{\infty}\frac{1}{\sqrt{2\pi}}\exp\left(-\frac{n-2\lambda}{n}\frac{v_i^2}{2}\right)\rmd v_i\\ &=\left(\sqrt{\frac{n}{n-2\lambda}}\right)^n \end{aligned}

即

$$P(\|u\|-1\geq \varepsilon)\leq \min_{\lambda>0}e^{-\lambda(\varepsilon+1)}\left(\frac{n}{n-2\lambda}\right)^\frac{n}{2}$$

取$f(\lambda)=e^{-\lambda(\varepsilon+1)}\left(\frac{n}{n-2\lambda}\right)^\frac{n}{2}$

\frac{\rmd f(\lambda)}{\rmd \lambda}=e^{-\lambda(\varepsilon+1)}\left[-(\varepsilon +1)\left(\frac{n}{n-2\lambda}\right)^{\frac{n}{2}}+\frac{n}{2}\left(\frac{n}{n-2\lambda}\right)^{\frac{n}{2}-1}\frac{2n}{(n-2\lambda)^2}\right]=0

根$\lambda_0 = \dfrac{n\varepsilon}{2(\varepsilon +1)}$

故

$$P(\|u\|-1\geq \varepsilon)\leq f(\lambda_0)=e^{-\frac{n\varepsilon }{2}}(1+\varepsilon)^{\frac{n}{2}}=e^{\frac{n}{2}(\ln (1+\varepsilon)-\varepsilon )}$$

当$\|u\|^2<1$时

$$P(1-\|u\|^2\leq \varepsilon)\leq \min_{\lambda>0}e^{-\lambda\varepsilon}\mathbb{E}(e^{\lambda (1-\|u\|^2)})=\min_{\lambda>0}e^{-\lambda (\varepsilon-1)}E(e^{-\lambda \|u\|^2})$$

\begin{aligned} \mathbb{E}(-\lambda \|u\|^2)&= \mathbb{E}(e^{-\lambda \sum u_i^2})\\ &=\prod_{i=1}^n \mathbb{E}(e^{-\lambda u_i^2})\\ &=\prod_{i=1}^n \int_{-\infty}^{\infty}\frac{\sqrt{n}}{\sqrt{2\pi}}\exp(-\frac{nu_i^2}{2})\exp(-\lambda u_i^2)\rmd u_i\\ &=\prod_{i=1}^n\int_{-\infty}^{\infty}\frac{1}{\sqrt{2\pi}}\exp (-\frac{n+2\lambda}{n}\frac{v_i^2}{2})\rmd v_i\\ &=\left(\frac{n}{n+2\lambda}\right)^\frac{n}{2} \end{aligned}

即

$$P(1-\|u\|^2\leq \varepsilon)\leq \min_{\lambda>0}e^{-\lambda (\varepsilon-1)}\left(\frac{n}{n+2\lambda}\right)^{\frac{n}{2}}$$

取$\lambda_0 = \dfrac{\varepsilon n}{2(1-\varepsilon)}$

$$P(1-\|u\|^2\leq \varepsilon)\leq e^{\frac{\varepsilon n}{2}}(1-\varepsilon)^\frac{n}{2}=e^{\frac{n}{2}(\varepsilon+\ln (1-\varepsilon))}$$

即

$$\begin{cases} P(\|u\|^2-1\geq \varepsilon)\leq e^{\frac{n}{2}(\ln (1+\varepsilon)-\varepsilon )}\\ P(1-\|u\|^2\leq \varepsilon)\leq e^{\frac{n}{2}(\varepsilon+\ln (1-\varepsilon))} \end{cases}$$

考虑

$$\ln \frac{1+\varepsilon}{1-\varepsilon}>2\varepsilon$$

$$\ln (1+\varepsilon)-\varepsilon < -\frac{\varepsilon^2}{C}$$

$$C>\max_{\varepsilon\in(0,1)}\left(\frac{\varepsilon^2}{\varepsilon-\ln(1+\varepsilon)}\right)=\frac{1}{1-\ln2}\simeq 3.26$$

通常取$C=4$，则

$$\begin{cases} P(\|u\|^2-1\geq \varepsilon)\leq e^{-\frac{n\varepsilon^2}{8}}\\ P(1-\|u\|^2\leq \varepsilon)\leq e^{-\frac{n\varepsilon^2}{8}} \end{cases}$$

$$P(|\|u\|^2-1|\geq \varepsilon )\leq 2e^{-\frac{n\varepsilon^2}{8}}$$

正交性引理

\forall u,v\in \calG, \forall \varepsilon \in(0,1), P(|\left|\geq \varepsilon)\leq 4\exp(-\frac{\varepsilon^2n}{8})

$\mathbf{Proof:}$
$u,v\in\mathcal{G}$, 则 $\dfrac{u+v}{\sqrt{2}},\dfrac{u-v}{\sqrt{2}}\in \mathcal{G}$

一方面

$$\begin{aligned} P(|\left<u,v\right>|\geq \varepsilon)&\leq P\left(\left\|\frac{u+v}{\sqrt{2}}\right\|^2-1\geq\varepsilon\right)+P\left(1-\left\|\frac{u-v}{\sqrt{2}}\right\|^2\geq \varepsilon\right)\\ &\leq 4\exp(-\frac{\varepsilon^2 n}{8}) \end{aligned}$$

另一方面

$$\begin{aligned} P(-\left<u,v\right>\geq \varepsilon)&\leq P\left(1-\left\|\frac{u+v}{\sqrt{2}}\right\|^2\geq \varepsilon\right)+P\left(\left\|\frac{u-v}{\sqrt{2}}\right\|^2-1\geq \varepsilon\right)\\ &\leq 4\exp(-\frac{\varepsilon^2n}{8}) \end{aligned}$$

综上

$$P(|\left<u,v\right>|\geq \varepsilon)\leq 4\exp(-\frac{\varepsilon^2n}{8})$$

Chernoff Bound

Moment generating function 矩生成函数
随机变量$X$的矩生成函数定义为

$$M_X(t)=\mathbb{E}(e^{tX})=\int_0^1 e^{tx}\mathrm{d}F(x)$$

Hoeffding lemma
对于随机变量$X$, $a\leq X\leq b$, $\mathbb{E}[X]=0, \forall x, |f(x)|<\infty$, 则

$$\mathbb{E}(e^{\lambda(X-\mu)})\leq\exp\left(\frac{\lambda(b-a)^2}{8}\right)$$