$ \gdef\d{\mathrm{d}} \gdef\e{\mathrm{e}} \gdef\i{\mathrm{i}} \gdef\a{\mathbf{a}} \gdef\b{\mathbf{b}} \gdef\c{\mathbf{c}} \gdef\p{\mathbf{p}} \gdef\q{\mathbf{q}} \gdef\u{\mathbf{u}} \gdef\v{\mathbf{v}} \gdef\w{\mathbf{w}} \gdef\x{\mathbf{x}} \gdef\y{\mathbf{y}} \gdef\z{\mathbf{z}} \gdef\l{\left} \gdef\r{\right} \gdef\eps{\varepsilon} \gdef\Var{\mathrm{Var}} \gdef\diag{\mathrm{diag}} \gdef\rank{\mathrm{rank}} \gdef\span{\mathrm{span}} \gdef\nullity{\mathrm{nullity}} $

尾部估计 Tail bounds

马尔可夫不等式 Markov’s inequality

设 $X \ge 0$ 为非负随机变量，对任意 $c > 0$，

$$ \Pr(X > cE[X]) < \frac{1}{c}. $$

Proof

\[ E[X] > \Pr(X > cE[X]) \cdot cE[X]. \]

另一种形式为：

$$ \Pr(X > c) < \frac{E[X]}{c}. $$

切比雪夫不等式 Chebyshev’s inequality

$$ \Pr(|X - E[X]| > c \sigma(X)) < \frac{1}{c^2}. $$

Proof

对 $|X - E[X]|$ 使用 Markov 不等式，得到

\[ \Pr(|X - E[X]| > c \sigma(X)) = \Pr((X - E[X])^2 > c^2 \sigma^2(X)) < \frac{1}{c^2}. \]

使用 Chebyshev 不等式时，需要计算 $E[X]$ 和 $\sigma^2(X) = E[X^2] - E[X]^2$。$E[X^k]$ 称为 k 阶矩 the k-th moment。

要证明一个东西的级别，一个通用的想法是，用 Union Bound 证下界，用 Chebyshev’s Inequality 证上界。

设随机变量 $X = \sum_{i = 1}^{n} X_i$，其中 $X_i$ 分别有 $\frac{1}{2}$ 的概率为 $0$ 和 $1$。

计算得 $E[X] = \frac{n}{2}$，$\sigma^2(X) = \sum \sigma^2(X_i) = \frac{n}{4}$。使用 Chebyshev 不等式，

$$ \Pr(|X - \mu| \ge 10 \cdot \sigma) \le \frac{1}{100}. $$

如果使用 Markov 不等式，则会得到较差的结果，因为标准差和均值不在同一个数量级。

概率估计的几何解释

考虑 $f(x) = 1 \ (x \ge c)$，则 $\Pr(X \ge c) = E[f(X)]$。考虑构造函数 $g(x) \ge f(x)$，则

$$ \Pr(X \ge c) = E[f(X)] \le E[g(X)]. $$

如果 $g(x)$ 的期望方便计算，就容易得到一个对于 $\Pr(X \ge a)$ 的估计。

当 $g(x) = \frac{x}{c}$ 时，则得到 Markov 不等式：

$$ \Pr(X \ge c) \le E[g(X)] = \frac{E[X]}{c}. $$

类似地，$g(x) = \frac{(x - \mu)^2}{c^2}$ 在 $|x - \mu| \ge c$ 时 $\ge 1$，由此得到 Chebyshev 不等式：

$$ \Pr(|X - \mu| \ge c) \le E[g(X)] = \frac{E[(X - \mu)^2]}{c^2} = \frac{\sigma^2(X)}{c^2}. $$

现在考虑使用指数函数来更加激进地进行估计。

切诺夫界 Chernoff bound

由于 $f(x)$ 在 $x \ge a$ 时为 $1$，所以指数上 $x$ 的系数必须为正数。考虑让界尽量紧，令 $g(x) = \e^{t(x - a)}$，其中 $t \in [0, +\infty)$ 为待定系数。得到：

$$ \Pr(X \ge a) \le E[g(X)] = \frac{E[\e^{tX}]}{\e^{ta}}. $$

另一种解释是使用 Markov 不等式：

$$ \Pr(X \ge a) = \Pr(\e^{tX} \ge \e^{ta}) \le \frac{E[\e^{tX}]}{\e^{ta}}. $$

当 $t = 0$ 时，得到 $\Pr(X \ge a) \le 1$ 没有用。当 $t \to +\infty$ 时，$x \ge a$ 的部分增长太快会使得估计不好。我们要找到合适的 $t$ 使得 $E[g(X)]$ 最小。

对于 Chernoff bound，取 $t < 0$ 可以得到对 $\Pr(X \le a)$ 的估计。

独立 Bernoulli 随机变量之和的 Chernoff bound

设随机变量 $X = \sum_{i = 1}^{n} X_i$，其中 $\Pr(X_i = 1) = b_i$，$\Pr(X_i = 0) = 1 - b_i$，则

$$ \Pr(X \ge (1 + \delta) \mu) \le \exp(-\frac{\delta^2}{2 + \delta} \mu), \quad \delta > 0. $$$$ \Pr(X \le (1 - \delta) \mu) \le \exp(-\frac{\delta^2}{2} \mu), \quad 0 < \delta < 1. $$

Proof

设 $a = (1 + \delta) \mu$。由 Markov 不等式：

\[ \Pr(X \ge (1 + \delta) \mu) \le \frac{E[\e^{tX}]}{\e^{t(1 + \delta) \mu}}. \]

根据 $1 + x \le \e^x$，

\[ \begin{aligned} E[\e^{tX}] &= \prod \e^{t X_i} \\ &= \prod (1 - b_i + b_i \e^t) \\ &\le \prod \exp(b_i (\e^t - 1)) \\ &= \exp ((\e^t - 1) \sum b_i) \\ &= \exp ((\e^t - 1) \mu). \end{aligned} \]

故需要最小化 $(\e^t - 1) \mu - t (1 + \delta) \mu$，得到 $t_0 = \ln (1 + \delta)$。

由 $\ln(1 + x) \ge \frac{2x}{2 + x}$ 得到

\[ \delta - \ln(1 + \delta)(1 + \delta) \le -\frac{\delta^2}{2 + \delta}, \]

所以

\[ \Pr(X \ge (1 + \delta) \mu) \le \exp(-\frac{\delta^2}{2 + \delta} \mu). \]

类似可以证明

\[ \Pr(X \le (1 - \delta)\mu) \le \exp(-\frac{\delta^2}{2} \mu). \]

Corollary 1

对于 $0 < \delta \le 1$：

\[ \Pr(X \ge (1 + \delta) \mu) \le \exp(-\frac{1}{3} \delta^2 \mu). \]

对于 $\delta > 1$（此时 $\frac{\delta^2}{2+\delta} \ge \frac{\delta}{3}$，因为 $\delta \ge 1 \implies 2+\delta \le 3\delta$）：

\[ \Pr(X \ge (1 + \delta) \mu) \le \exp(-\frac{1}{3} \delta \mu). \]

或者，可以直接使用 Chernoff 界原始形式中更紧的界：

\[ \Pr(X \ge (1 + \delta) \mu) \le \exp(-\frac{\delta^2}{2 + \delta} \mu). \]

对于下界情况，当 $0 < \delta < 1$ 时：

\[ \Pr(X \le (1 - \delta) \mu) \le \exp(-\frac{1}{2} \delta^2 \mu). \]

上述的公式也适用于 $X \sim \mathrm{Poisson}(\mu)$ 的 Poisson 分布。

霍夫丁不等式 Hoeffding’s inequality

设 $X = \sum_{i = 1}^{n} X_i$，其中 $X_i \in [a_i, b_i]$ 是有界随机变量，则对任意 $t \ge 0$，

$$ \Pr(|X - E[X]| \ge t) \le 2\exp\l(-\frac{2t^2}{\sum (b_i - a_i)^2}\r). $$

此不等式包含了两种情况：$X - E[X] \ge t$ 和 $X - E[X] \le -t$（即 $E[X] - X \ge t$）。 由于 Chernoff 方法可以分别应用于这两个单边情况，因此可以直接得到如下的单边霍夫丁不等式，此时右侧的因子 $2$ 被移除：

$$ \Pr(X - E[X] \ge t) \le \exp\l(-\frac{2t^2}{\sum (b_i - a_i)^2}\r). $$$$ \Pr(X - E[X] \le -t) \le \exp\l(-\frac{2t^2}{\sum (b_i - a_i)^2}\r). $$

本质是对独立有界随机变量之和使用 Chernoff bound。

常见概率分布及其矩量母函数 MGF

离散分布 Discrete distributions

伯努利分布 Bernoulli distribution

参数 $p \in [0, 1]$ 为成功的概率。

$$ \Pr(X = 1) = p, \quad \Pr(X = 0) = 1 - p, \quad M_X(t) = p \e^t + (1 - p). $$

MGF 定义域 $t \in \R$。伯努利分布的期望为 $p$，方差为 $p(1 - p)$。

二项分布 Binomial distribution

参数 $n \in \N$ 为实验次数，$p \in [0, 1]$ 为单次成功的概率。

$$ \Pr(X = k) = \binom{n}{k} p^k (1 - p)^{n - k}, \quad M_X(t) = (p \e^t + (1 - p))^n. $$

MGF 定义域 $t \in \R$。二项分布的期望为 $np$，方差为 $np(1 - p)$。

几何分布 Geometric distribution

参数 $p \in (0, 1]$ 为单次成功的概率。

若 $k$ 为第一次成功前的失败次数，则对于所有 $k \in \N$，

$$ \Pr(X = k) = (1 - p)^k p, \quad M_X(t) = \frac{p}{1 - (1 - p) \e^t}. $$

若 $k$ 为第一次成功时的实验次数，则对于所有 $k \in \N^+$，

$$ \Pr(X = k) = (1 - p)^{k - 1} p, \quad M_X(t) = \frac{p \e^t}{1 - (1 - p) \e^t}. $$

MGF 定义域 $t < -\ln(1 - p)$。几何分布的期望为 $\frac{1}{p} - 1$ 或 $\frac{1}{p}$，方差为 $\frac{1 - p}{p^2}$。

泊松分布 Poisson distribution

参数 $\lambda \in [0, +\infty)$ 为期望。

对于所有 $k \in \N$，

$$ \Pr(X = k) = \frac{\lambda^k}{k!} \e^{-\lambda}, \quad M_X(t) = \e^{\lambda(\e^t - 1)}. $$

MGF 定义域 $t \in \R$。泊松分布的期望为 $\lambda$，方差为 $\lambda$。

负二项分布 Negative binomial distribution

参数 $r \in \N$ 为成功次数，$p \in (0, 1]$ 为单次成功的概率。

对于所有 $k \in \N$，

$$ \Pr(X = k) = \binom{k + r - 1}{k} p^r (1 - p)^k, \quad M_X(t) = \l(\frac{p}{1 - (1 - p) \e^t}\r)^r. $$

MGF 定义域 $t < -\ln(1 - p)$。负二项分布的期望为 $\frac{r(1 - p)}{p}$，方差为 $\frac{r(1 - p)}{p^2}$。

连续分布 Continuous distributions

均匀分布 Uniform distribution

参数 $a, b \in \R$ 为区间端点。

$$ f(x) = \begin{cases} \frac{1}{b - a}, & x \in [a, b], \\ 0, & \text{otherwise}. \end{cases} $$$$ M_X(t) = \frac{1}{b - a} \int_a^b \e^{tx} \d x = \frac{\e^{bt} - \e^{at}}{(b - a)t}. $$

MGF 定义域 $t \in \R$。均匀分布的期望为 $\frac{a + b}{2}$，方差为 $\frac{(b - a)^2}{12}$。

指数分布 Exponential distribution

参数 $\lambda \in (0, +\infty)$ 为速率参数。

$$ f(x) = \lambda \e^{-\lambda x} \text{ for } x \ge 0, \quad M_X(t) = \int_0^{+\infty} \lambda \e^{-(\lambda - t) x} \d x = \frac{\lambda}{\lambda - t}. $$

MGF 定义域 $t < \lambda$。指数分布的期望为 $\frac{1}{\lambda}$，方差为 $\frac{1}{\lambda^2}$。

卡方分布 Chi-squared distribution

参数 $k \in (0, +\infty)$ 为自由度。

$$ f(x) = \frac{1}{2^{\frac{k}{2}} \Gamma(\frac{k}{2})} x^{\frac{k}{2} - 1} \e^{-\frac{x}{2}}, \quad M_X(t) = \l(\frac{1}{1 - 2t}\r)^{\frac{k}{2}}. $$

MGF 定义域 $t < \frac{1}{2}$。卡方分布的期望为 $k$，方差为 $2k$。

Gamma 分布 Gamma distribution

参数 $\alpha \in (0, +\infty)$ 为形状参数，$\beta \in (0, +\infty)$ 为速率参数。

$$ f(x) = \frac{\beta^\alpha x^{\alpha - 1} \e^{-\beta x}}{\Gamma(\alpha)}, \quad M_X(t) = \l(\frac{\beta}{\beta - t}\r)^\alpha. $$

MGF 定义域 $t < \beta$。Gamma 分布的期望为 $\frac{\alpha}{\beta}$，方差为 $\frac{\alpha}{\beta^2}$。

注：指数分布是 Gamma 分布在 $\alpha = 1$ 时的特例，卡方分布是 Gamma 分布在 $\alpha = \frac{k}{2}$ 且 $\beta = \frac{1}{2}$ 时的特例。

高斯分布 Gaussian distribution

参数 $\mu \in \R$ 为期望，$\sigma^2 \in (0, +\infty)$ 为方差。

$$ f(x) = \frac{1}{\sqrt{2\pi \sigma^2}} \exp\l(-\frac{(x - \mu)^2}{2\sigma^2}\r), \quad M_X(t) = \exp\l(\mu t + \frac{\sigma^2 t^2}{2}\r). $$

MGF 定义域 $t \in \R$。高斯分布的期望为 $\mu$，方差为 $\sigma^2$。

拉普拉斯分布 Laplace distribution

参数 $\mu \in \R$ 为期望，$b \in (0, +\infty)$ 为尺度参数。

$$ f(x) = \frac{1}{2b} \exp\l(-\frac{|x - \mu|}{b}\r), \quad M_X(t) = \frac{\e^{\mu t}}{1 - b^2 t^2}. $$

MGF 定义域 $|t| < \frac{1}{b}$。拉普拉斯分布的期望为 $\mu$，方差为 $2b^2$。

集中不等式 concentration inequalities

大概只是 Chernoff bound 的另一种解释。

由 Markov 不等式，

$$ \Pr(|X - \mu| \ge a) = \Pr(|X - \mu|^k \ge a^k) \le \frac{E[|X - \mu|^k]}{a^k}, $$

可知 集中性来源于高阶矩的有界性。

矩量母函数 moment generating function：$M_X(t) = E[\e^{tX}]$。

则 Chernoff bound 可以被表示为：

$$ \Pr(X \ge a) \le \frac{M_X(t)}{\e^{ta}}. $$

Proof

\[ \begin{aligned} \Pr(X \ge a) &= \int_a^{+\infty} f(x) \d x \\ &\le \int_a^{+\infty} \frac{\e^{tx}}{\e^{ta}} f(x) \d x \\ &\le \frac{1}{\e^{ta}} \int_{-\infty}^{+\infty} \e^{tx} f(x) \d x. \end{aligned} \]

与此前提到的概率估计的几何解释并无不同。

高维几何 high dimensional geometry

高维球体 high dimensional ball

对于 $d$ 维单位球体，其表面积 $A(d)$ 和体积 $V(d)$ 分别为

$$ A(d) = \frac{2\pi^{\frac{d}{2}}}{\Gamma(\frac{d}{2})}, \quad V(d) = \frac{2\pi^{\frac{d}{2}}}{d \cdot \Gamma(\frac{d}{2})}. $$

注意表面积的定义为边界的 $d - 1$ 维超体积，例如 $d = 2$ 时表面积为周长。

其中 $\Gamma(x) = (x - 1) \Gamma(x - 1)$，$\Gamma(1) = 1$，$\Gamma(\frac{1}{2}) = \sqrt{\pi}$。也可以得到对于整数 $x$，$\Gamma(x) = (x - 1)!$。

上面的公式也说明 $\lim_{d \to +\infty} V(d) = 0$。

注意到体积和表面积恰好差 $d$ 倍。

高维球壳 high dimensional shell

记 $A$ 表示球，则球壳表示为 $A \setminus (1 - \varepsilon)A$​。

考虑体积 $V((1 - \varepsilon)A) = (1 - \varepsilon)^d V(A)$，以及不等式 $1 - \varepsilon \le \e^{-\varepsilon}$，得到

$$ \frac{V((1 - \varepsilon)A)}{V(A)} = (1 - \varepsilon)^d \le \e^{-\varepsilon d}. $$

对于高维球体，体积大量集中在球壳 Volume lies close to the shell。

高维球体赤道面 high dimensional equator

对 $c \ge 1$ 和 $d \ge 3$，至少 $1 - \frac{2}{c} \e^{-\frac{c^2}{2}}$ 的体积满足 $|x_1| \le \frac{c}{\sqrt{d - 1}}$​。

Proof

考虑赤道以上的上界：

\[ \begin{aligned} & \int_{\frac{c}{\sqrt{d - 1}}}^{1} (1 - x^2)^{\frac{d - 1}{2}} V(d - 1) \d x \\ \le& \int_{\frac{c}{\sqrt{d - 1}}}^{1} \frac{x \sqrt{d - 1}}{c} \e^{-\frac{d - 1}{2} x^2} V(d - 1) \d x \\ =& V(d - 1) \frac{\sqrt{d - 1}}{c} \int_{\frac{c}{\sqrt{d - 1}}}^{+\infty} x \e^{-\frac{d - 1}{2} x^2} \d x \\ =& \frac{V(d - 1)}{c \sqrt{d - 1}} \e^{-\frac{c^2}{2}}. \end{aligned} \]

赤道附近区域的下界，使用高度为 $\frac{1}{\sqrt{d - 1}}$ 的圆柱来估计：

\[ \left(1 - \frac{1}{d - 1}\right)^{\frac{d - 1}{2}} \frac{V(d - 1)}{\sqrt{d - 1}} \ge \frac{V(d - 1)}{\sqrt{\e(d - 1)}} \ge \frac{V(d - 1)}{2 \sqrt{d - 1}}. \]

两式子相除即可得到不等式。

对于高维球体，体积大量集中在赤道面 Volume lies close to the equator。

考虑 $d$ 维球体中的 $n$ 个随机向量 $\x_1, \ldots, \x_n$，有 $1 - \mathcal O(\frac{1}{n})$ 的概率：

1. $\|\x_i\|_2 \ge 1 - \frac{2 \ln n}{d}$，对于所有 $i$，因为体积集中在球壳。
2. $|\x_i \cdot \x_j| \le \frac{\sqrt{6 \ln n}}{\sqrt{d - 1}}$，对于所有 $i \neq j$，因为体积集中在赤道。

Proof

前者取 $\varepsilon = \frac{2\ln n}{d}$，得

\[ \Pr(|\x_i|_2 < 1 - \frac{2 \ln n}{d}) \le \e^{-(\frac{2 \ln n}{d}) d} = \mathcal O(n^{-2}). \]

后者取 $c = \sqrt{6 \ln n}$，得

\[ \Pr(|\x_i \cdot \x_j| > \frac{c}{\sqrt{d - 1}}) \le \mathcal O(\e^{-\frac{6 \ln n}{2}}) = \mathcal O(n^{-3}). \]

最后外面套一层 union bound 即可。

对于高位球体，其中的随机向量几乎垂直 Random vectors are almost orthogonal。

球面高斯分布 Spherical Gaussian

在高维空间中，沿着任何一条直线的方向，我们希望这个分布依旧是高斯分布。并且对于正交的各个轴之间，我们希望它们是独立的。于是得到 $d$ 维球面高斯分布：

$$ f(\x) = \frac{1}{(2 \pi)^{\frac{d}{2}} \sigma^d} \exp\l(-\frac{\|\x\|_2^2}{2\sigma^2}\r). $$

球面高斯分布的每个分量都是独立的高斯分布，并且方差为 $\sigma^2$。

高斯环面定理 Gaussian annulus theorem (GAT)

对于 $d$ 维球面高斯 $x_i \sim N(0, 1)$，对任意 $\beta \le \sqrt{d}$，至多有 $3\e^{-c\beta^2}$ 的概率质量不在 $\sqrt{d} - \beta \le \|\x\|_2 \le \sqrt{d} + \beta$ 的范围内，其中 $c > 0$​ 为某个固定常数（由于是常数所以我们一般不关心），书上的证明给出的 $c = \frac{1}{96}$。

先重申 霍夫丁不等式 Hoeffding’s inequality：对于有界独立随机变量 $Z_1, \ldots, Z_n$，其中 $Z_i \in [a, b]$ 且 $-\infty < a \le b < +\infty$，则对于所有 $t \ge 0$，

$$ \Pr\l( \frac{1}{n} \sum_{i = 1}^{n} (Z_i - E[Z_i]) \ge t \r) \le \exp \l(-\frac{2nt^2}{(b - a)^2}\r), $$$$ \Pr\l(\frac{1}{n} \sum_{i = 1}^{n} (Z_i - E[Z_i]) \le -t\r) \le \exp\l(-\frac{2nt^2}{(b - a)^2}\r). $$

如果随机变量无界，但对所有 $\lambda$ 都存在有界的 MGF，即

$$ E[\e^{\lambda(X_i - \mu_i)}] \le \e^{\lambda^2 \sigma^2/2}. $$

我们定义满足上述条件的分布为 亚高斯分布 Sub-Gaussian。则根据 Subgaussian tail bound，对于任意 $t > 0$，有

$$ \Pr(|X - E[X]| \ge t) \le 2 \exp\l(-\frac{t^2}{2\sigma^2}\r). $$

对 $n$ 个同分布的 Sub-Gaussian 随机变量求和，则

$$ \Pr(|S - E[S]| \ge t) \le 2 \exp\l(-\frac{t^2}{2n\sigma^2}\r). $$

上述公式来源于高斯分布的尾部估计，而亚高斯分布比高斯分布的集中性更强，即根据定义，亚高斯分布的 MGF 比高斯分布的 MGF 更小。

但是 $\sum_{i = 1}^{n} X_i^2$ 是卡方分布而不是亚高斯分布，因为其 MGF 是无界的。这时我们可以使用另一个工具 亚指数分布 Sub-exponential：对于参数 $\nu$ 和 $b$，满足对于任意 $|\lambda| < \frac{1}{b}$，

$$ E[\e^{\lambda (X - \mu)}] \le \e^{\lambda^2 \nu^2/2}. $$

这本质上是一个稍弱于亚高斯分布的定义，即只在 $|\lambda|$ 较小时满足对应条件。那么类似低，对于任意 $t > 0$，有

$$ \Pr(|S - E[S]| \ge t) \le 2 \exp\l(-\min\l\{\frac{t^2}{2n \nu^2}, \frac{t}{2b}\r\}\r). $$

$\min$ 是由于分为 $|\lambda| < \frac{1}{b}$ 和 $|\lambda| \ge \frac{1}{b}$ 两种情况讨论。

那么回到 GAT，自由度为 $d$ 的卡方分布 $S$（即 $d$ 个独立高斯随机变量平方和）是参数为 $\nu = 2\sqrt{d}$ 和 $b = 4$ 的亚指数分布，所以

$$ \Pr(|S - d| \ge t) \le 2 \exp\l(-\min\l\{\frac{t^2}{8d}, \frac{t}{8}\r\}\r). $$

那么对于任意 $\beta \le \sqrt{d}$，有

$$ \Pr(\l|\|\x\|_2 - \sqrt{d}\r| \ge \beta) \le 2 \exp\l(-\min\l\{\frac{(2\sqrt{d}\beta)^2}{8d}, \frac{2\sqrt{d}\beta}{8}\r\}\r) \le 2 \e^{-\beta^2/2}. $$

书上的证明得到更紧的常数 $c = \frac{1}{96}$。我们这里只关心结论的数量级，所以不展开。作业中也给出了直接使用 Chernoff bound 的证明。

低秩近似 Low Rank Approximation

主要内容：数据压缩，将高维空间的点映射到低维空间，同时尽量保持结构特征。

下面的范数若不特殊说明，则都为欧几里得范数。

随机投影与 JL 引理 random projection and JL Lemma

随机投影在大部分情况下已经能够获得比较好的结果。

构造投影 $f: \R^d \to \R^k$。在 $\R^d$ 中随机采样 $k$ 个 Gaussian $\u_i \sim N(0, I_d)$。对于任意 $\v \in \R^d$，$f(\v) = (\u_i \cdot \v)_{i = 1}^{k}$ 是 $\v$ 在 $\R^d$ 中的投影向量。

随机投影定理 random projection theorem

存在 $c > 0$ 使得对 $\varepsilon \in (0, 1)$，

$$ \Pr(\big| \|f(\v)\| - \sqrt{k}\|\v\| \big| \ge \eps \sqrt{k} \|\v\|) \le 3 \e^{-ck\eps^2}. $$

其随机性来源于 $\u_i$。注意到 投影的缩放倍数只和目标维数 $k$ 有关。

Proof

由线性性，不妨设 $\|\v\| = 1$。

\[ \Var(\u_i \cdot \v) = \Var\l(\sum_{j = 1}^{d} u_{ij} v_j\r) = \sum_{j = 1}^{d} v_j^2 \Var(u_{ij}) = 1. \]

高斯分布的线性组合仍是高斯分布，因此投影结果的每一维 $f(\v)_i \sim N(0, 1)$ 且独立。根据 GAT，

\[ \begin{aligned} & \Pr(\big| |f(\v)| - \sqrt{k}|\v| \big| \ge \eps \sqrt{k} |\v|) \\ =\ & \Pr(\sqrt{k} - \eps \sqrt{k} \le |f(\v)| \le \sqrt{k} + \eps \sqrt{k}) \\ \le\ & 3 \e^{-c(\eps \sqrt{k})^2}. \end{aligned} \]

JL 引理 Johnson-Lindenstrauss Lemma

对于 $\R^d$ 中的 $n$ 个点，设 $k \ge \frac{3}{c\eps^2} \ln n$，则有至少 $1 - \frac{3}{2n}$ 的概率，对于所有 $(i, j)$，

$$ (1 - \eps) \sqrt{k} \|\v_i - \v_j\| \le \|f(\v_i) - f(\v_j)\| \le (1 + \eps) \sqrt{k} \|\v_i - \v_j\|. $$

Proof

对 $\v_i - \v_j$ 使用随机投影定理，则 $3\e^{-ck\eps^2} \le \frac{3}{n^3} \Longrightarrow k \ge \frac{3}{c\eps^2} \ln n$。由布尔不等式，所有 $(i, j)$ 都满足的概率至少为 $1 - {n \choose 2} \frac{3}{n^3} \ge 1 - \frac{3}{2n}$.

随机投影定理说明随机投影保长度。根据保长度，考虑两个向量的差，得到 JL 引理，即随机投影保距离。

奇异值分解 singular value decomposition (SVD)

在欧几里得范数下，SVD 分解是 理论最优 的低秩近似。

右奇异向量 right singular vectors

考虑 $n$ 个二维点，组成 $n \times 2$ 的矩阵 $A$。要找到一维线性子空间 $\span\{\v\}$ 使得拟合最好，即最小化误差的平方和。由勾股定理，其等价于最大化投影长度的平方和。而 $\|\v\| = 1$，所以向量 $\u$ 的投影长度恰好为 $\u^T \v$，即投影长度的平方和等于 $\|A \v\|^2$。

对于任意 $n \times m$ 的矩阵 $A$，最好的拟合直线（过原点）为

$$ \v_1 = \arg \max_{\|\v\| = 1} \|A \v\|, $$

其中 $\v_1 \in \R^m$ 称为第一个 右奇异向量。对应的第一个 奇异值 singular value 为

$$ \sigma_1 = \max_{\|\v\| = 1} \|A \v\|. $$

将子空间增大，找到第二个单位向量 $\v_2$ 使得在 $\v_1$ 的基础上，张成的子空间对应的投影长度平方和最小，不难发现 $\v_2$ 需要与 $\v_1$ 垂直，即

$$ \v_2 = \arg \max_{\|\v\| = 1, \v \perp \v_1} \|A \v\|, $$

对应第二个奇异值

$$ \sigma_2 = \max_{\|\v\| = 1, \v \perp \v_1} \|A \v\|. $$

以此类推，可以得到 $r$ 个奇异值以及对应的右奇异向量，其中 $r$ 为矩阵 $A$​ 的秩。

左奇异向量 left singular vectors

将 $A \v_i$ 单位化，定义 左奇异向量

$$ \u_i = \frac{1}{\sigma_i(A)} A \v_i. $$

那么

$$ \sum_{i = 1}^{r} \sigma_i \u_i \v_i^T \v_j = \sigma_j \u_j = A \v_j \Longrightarrow A = \sum_{i = 1}^{r} \sigma_i \u_i \v_i^T = U \Sigma V^T. $$

称为 $A$ 的 奇异值分解 singular value decomposition。其中 $U$ 和 $V$ 分别为 $\u_i$ 和 $\v_i$ 列向量组成的矩阵，$\Sigma$ 为对角矩阵且 $\Sigma_{ii} = \sigma_i$。

另一种推导方式：因为 $\v_i$ 是标准正交基 orthonormal basis，所以

$$ AV = U \Sigma \Longrightarrow A = U \Sigma V^{-1} = U \Sigma V^T. $$

此外，可以证明 $\u_i$ 是 $A^T$ 的右奇异向量，对应的奇异值仍为 $\sigma_i$。这与 $\v$ 是对称的。

Proof

假设 $i < j$ 且 $\u_i^T \u_j = \delta > 0$。考虑 $\v_i' = \frac{\v_i + \eps \v_j}{\|\v_i + \eps \v_j\|}$，则

\[ A \v_i’ = \frac{\sigma_i \u_i + \eps \sigma_j \u_j}{\sqrt{1 + \eps^2}}, \]

\[ |A \v_i’| > \u_i^T \l( \frac{\sigma_i \u_i + \eps \sigma_j \u_j}{\sqrt{1 + \eps^2}} \r) > (\sigma_i + \eps \sigma_j \delta) \l(1 - \frac{\eps^2}{2}\r) > \sigma_i. \]

与 $\v_i$​ 的最优性相矛盾。

故 $\u_i$ 两两垂直，因此 $U^T A = \Sigma V$，即 $A^T U = V \Sigma$，可知 $\|\u_i^T A\| = \sigma_i$。

从中可以感受到奇异值的对称性：

$$ A \v_i = \sigma_i \u_i, \quad A^T \u_i = \sigma_i \v_i. $$

SVD 的最优性

上文中贪心地每次取结果最大的向量是否能得到最优的结果？考虑对 $k=2$ 的情况进行证明，然后进行归纳。相当于上述方式选出的结果是否满足

$$ \sigma_1^2 + \sigma_2^2 = \arg \max_{\|\v_1\| = \|\v_2\| = 1, \v_1 \perp \v_2} \|A \v_1\|^2 + \|A \v_2\|^2. $$

Proof

假设子空间 $W$ 比 $V$ 更优，则可以选出 $(\w_1, \w_2)$ 满足 $\w_2 \perp \v_1$，但

• 若 $\w_1 \neq \v_1$，则 $\|A \w_1\|^2 \le \sigma_1^2$，因为 $\v_1$ 是全局最优。
• 若 $\w_2 \neq \v_2$，则 $\|A \w_2\|^2 \le \sigma_2^2$，因为 $\v_2$ 是与 $\v_1$​ 垂直中的最优。

因此

\[ |A \w_1|^2 + |A \w_2|^2 \le \sigma_1^2 + \sigma_2^2, \]

矛盾。

低秩矩阵近似 low rank matrix approximation

由勾股定理，$A$ 的每个向量在各个 $\v_i$ 上的正交投影的长度平方和等于该向量的长度平方，因此

$$ \sum_{j = 1}^{n} \|\a_j\|^2 = \sum_{j = 1}^{n} \sum_{i = 1}^{r} (\a_j \cdot \v_i)^2 = \sum_{i = 1}^{r} \|A \v_i\|^2 = \sum_{i = 1}^{r} \sigma_i^2(A). $$

定义 $A$ 的 Frobenius 模长为

$$ \|A\|_F = \sqrt{\sum_{ij} a_{ij}^2}, $$

则

$$ \sum_{i = 1}^{n} \sigma_i^2(A) = \|A\|_F^2. $$

正交矩阵保持 Frobenius 范数，即对于正交矩阵 $U$，有

$$ \|U A\|_F = \|A\|_F. $$

低秩矩阵近似 即给定 $A$，最小化 $A - B$ 在给定范数下的模长，满足 $\rank(B) \le k$。

设 $A_k = \sum_{i = 1}^{k} \sigma_i \u_i \v_i^T$。对于任意 $B$ 满足 $\rank(B) \le k$，

$$ \|A - A_k\|_F \le \|A - B\|_F. $$

也就是说，最优的 $B^*$ 满足

$$ \|A - B^*\|_F^2 = \sum_{i = k + 1}^{r} \sigma_i^2. $$

Proof

正交矩阵保持 Frobenius 范数，所以

\[ |A - B|_F = |U^T(A - B)V|_F = |\Sigma - U^T B V|_F. \]

设 $C = U^T B V$，则 $\rank(C) \le \rank(B) = k$。所以

\[ |A - B|_F = |\Sigma - C|_F. \]

因为 $\Sigma$ 是对角矩阵，所以最优的 $C^* = \diag(\sigma_1, \ldots, \sigma_k, 0, \ldots, 0)$，即

\[ B^* = U C^* V^T = U_k \Sigma_k V_k^T = A_k. \]

定义矩阵的 L2-范数 L2-norm

$$ \|A\|_2 = \max_{\|\v\| \le 1} \|A \v\|, $$

也称矩阵 $A$ 的 谱范数 spectral norm。显然最大值在 $\v$ 是单位向量时取到，因此矩阵 $A$ 的 L2-范数等于 $\sigma_1(A)$。同时

$$ \|A - A_k\|_2 = \sigma_{k + 1}. $$

Proof

考虑任意 $\v = \sum_{j = 1}^{r} c_j \v_j$，则

\[ |(A - A_k) \v| = \l| \sum_{i = k + 1}^{r} \sigma_i \u_i \v_i^T \sum_{j = 1}^{r} c_j \v_j \r| = \l| \sum_{i = k + 1}^{r} c_i \sigma_i \u_i \r| = \sqrt{\sum_{i = k + 1}^{r} c_i^2 \sigma_i^2}. \]

而 $\sum_{i = 1}^{r} c_i^2 = 1$，最大值不超过 $\sigma_{k + 1}^2$。

我们还可以证明（注意区分 L2-范数和 Frobenius 范数），对于任意 $B$ 满足 $\rank(B) \le k$，

$$ \|A - A_k\|_2 \le \|A - B\|_2. $$

这样可以将问题看作最优化子空间，而非最优化矩阵。

Proof

如果 $\rank(A) \le k$ 那么显然，否则 $\nullity(B) \ge n - k$，那么存在单位向量

\[ \z \in \mathrm{Null}(B) \cap \span{\v_{1 \sim k + 1}}. \]

于是

\[ |A - B|_2^2 \ge |(A - B) \z|^2 = |A \z|^2. \]

而 $\z$ 和所有 $\v_{k+2 \sim r}$ 垂直，所以

\[ |A \z|^2 = \l|\sum_{i = 1}^{r} \sigma_i \u_i \v_i^T \z \r|^2 = \sum_{i = 1}^{k + 1} \sigma_i^2 (\v_i^T \z)^2 \ge \sigma_{k + 1}^2 \sum_{i = 1}^{k + 1} (\v_i^T \z)^2 = \sigma_{k + 1}^2. \]

所以

\[ |A - B|2^2 \ge \sigma{k + 1}^2 = |A - A_k|_2^2. \]

幂迭代法 power method

用来求解 SVD 分解中的最大特征值。

设

$$ B = A^T A = \l( \sum_{i = 1}^{d} \sigma_i \v_i \u_i^T \r) \l( \sum_{j = 1}^{d} \sigma_j \u_j \v_j^T \r) = \sum_{i = 1}^{d} \sigma_i^2 \v_i \v_i^T, $$

则

$$ B^k = \sum_{i = 1}^{d} \sigma_i^{2k} \v_i \v_i^T. $$

指数上的 $2k$ 放大了 $\sigma_1$ 和其他 $\sigma_i < \sigma_1$ 的差异，使 $\sigma_1$ 成为主导项。

设 $\x = \sum_{i = 1}^{d} c_i \v_i$，则

$$ B^k \x = \sum_{i = 1}^{d} \sigma_i^{2k} c_i \v_i. $$

设 $V$ 是由 $\sigma_i > (1 - \eps) \sigma_1$ 的 $\v_i$ 张成的空间，单位向量 $\x \in \R^d$ 满足 $|\x^T \v_1| \ge \delta$，$k = \frac{\ln(1 / \eps \delta)}{2 \eps}$，则

$$ \w = \frac{B^k \x}{\|B^k \x\|} $$

在垂直于 $V$ 的方向上至多有 $\eps$ 的分量。

Proof

由条件，$c_1 \ge \delta$。设 $V = \span\{\v_{1 \sim m}\}$，则

\[ |B^k \x|^2 = \sum_{i = 1}^{d} \sigma_i^{4k} c_i^2 \ge \sigma_1^{4k} \delta^2. \]

垂直于 $V$ 的方向上的分量长度的平方为

\[ \sum_{i = m + 1}^{d} \sigma_i^{4k} c_i^2 \le (1 - \eps)^{4k} \sigma_1^{4k}. \]

于是

\[ \frac{(1 - \eps)^{2k} \sigma_1^{2k}}{\delta \sigma_1^{2k}} \le \frac{\e^{-2k\eps}}{\delta} = \eps. \]

如果 $\x$ 是随机向量，我们还需要计算 $|\x^T \v_1| \ge \delta$ 的概率。

随机 $\y \in N(0, 1)^{d}$，正规化得到 $\x = \frac{\y}{\|\y\|}$。设 $\v$ 是任意单位长度向量，则

$$ \Pr( |\x^T \v| < \frac{1}{20 \sqrt{d}}) \le \frac{1}{10} + 3 \e^{-d/96}. $$

Proof

由 GAT，代入 $\beta = \sqrt{d}$，

\[ \Pr(|\y| > 2 \sqrt{d}) < 3\e^{-d/96}. \]

$|\y^T \v| \sim N(0, 1)$，概率密度函数 $p(x) \le \frac{1}{\sqrt{2 \pi}} < 0.5$，所以

\[ \Pr(|\y^T \v| < \frac{1}{10}) \le \frac{1}{10}. \]

对两者使用 union bound。

若有多个最大的特征值，则 power method 会求出这些特征值对应的特征向量张成的空间中的任意特征向量。

要求次大的特征值，将 $\sigma_1 \u_1 \v_1^T$ 从 $A$ 中减去即可。以此类推，可以求出所有特征值。

SVD 分解的应用 SVD applications

主成分分析 principal component analysis

用很少的维度拟合高维空间，保留主要信息。

对于 $n \times d$ 的矩阵 $A$，表示 $n$ 个数据点，每个数据点有 $d$ 个特征。找到 $A \approx U_k \Sigma_k V_k^T$，其中 $U_k \Sigma_k$ 是 $n \times k$ 的矩阵，表示每个数据在特征维度上的分量；$V_k^T$ 是 $k \times d$ 的矩阵，表示每个特征在原维度上的分量。

$U_k \Sigma_k = A V_k$，$V_k$ 是 $d \times k$ 的矩阵，表示每个原维度在特征维度上的分量。

网页排名 page rank

权威页面有权重 $v_j$，枢纽页面有权重 $u_i$，矩阵 $A_{ij}$ 描述从枢纽页面 $j$ 到权威页面 $i$ 是否存在链接。那么合理的权重分配应该满足

$$ \v \propto A \u, \quad \u \propto A^T \v. $$

从随机向量 $\v$ 出发开始迭代

$$ \v \gets \frac{A \u}{\|A \u\|}, \quad \u \gets \frac{A^T \v}{\|A^T \v\|}. $$

这本质是在做幂迭代法，可以直接用 SVD 分解来求解。

社区检测 community detection

将点集划分为 $k$ 个部分，每个部分在空间上密集分布（在高维空间意义上）或内部的连边较为密集（在图论意义上）。

考虑一定的随机性产生的图 $G$，其中若 $i$ 和 $j$ 实际在同一个社区，则有 $p$ 的概率 $(i, j) \in G$，否则有 $q$ 的概率 $(i, j) \in G$。令矩阵 $A$ 为 $G$ 的邻接矩阵，则考虑 $k = 2$ 的情况，

$$ E[A] = \begin{bmatrix} p \mathbf{1} \mathbf{1}^T & q \mathbf{1} \mathbf{1}^T \\ q \mathbf{1} \mathbf{1}^T & p \mathbf{1} \mathbf{1}^T \end{bmatrix} = \frac{p + q}{2} \mathbf{1} \mathbf{1}^T + \frac{p - q}{2} \begin{bmatrix} \mathbf{1} \\ \mathbf{-1} \end{bmatrix} \begin{bmatrix} \mathbf{1}^T & \mathbf{-1}^T \end{bmatrix}. $$

$E[A]$ 有显然的第一大特征值 $\lambda_1 = \frac{p + q}{2} n$，特征向量 $\v_1 = \mathbf{1}$；第二大特征值 $\lambda_2 = \frac{p - q}{2} n$，特征向量 $\v_2 = \begin{bmatrix}\mathbf{1} \\ \mathbf{-1}\end{bmatrix}$。

使用 SVD 分解求出第二大特征值所对应的特征向量，即可根据正负性将点集划分为两个社区。

马尔可夫链 Markov chain

定义 $S = \{1, 2, \ldots, m\}$ 为 状态空间。

记 $\p(t) = (p_1(t), p_2(t), \ldots, p_m(t)) \in [0, 1]^m$ 表示 $t$ 时刻的 概率分布，满足 $\sum_{i = 1}^{m} p_i(t) = 1$。

状态之间的转移由 转移概率矩阵 $P$ 描述：

$$ P = [P_{ij}]_{i,j=1}^{m} \in [0, 1]^{m \times m}, \quad \sum_{j = 1}^{m} P_{ij} = 1 \text{ for every $i$}. $$

马尔可夫链 即满足「无记忆性」的随机过程，即 下一状态的概率分布只能由当前状态决定，而与时间序列中之前的事件无关。形式化地，

$$ \Pr(X_{t + 1} = i_{t + 1} \mid X_t = i_t, \ldots, X_0 = i_0) = \Pr(X_{t + 1} = i_{t + 1} \mid X_t = i_t) = P_{i_t i_{t + 1}}. $$

概率分布之间的转移关系为

$$ \p(t) P = \p(t + 1). $$

二维随机游走 2D random walk

定义一些记号：

• $T_i = \inf\{n \ge 1 : X_n = i\}$，$(\inf \varnothing = +\infty)$ 表示首次 返回时间 first return time。
• $f_i = \Pr_i(T_i < \infty)$ 表示 返回概率 return probability。其中 $\Pr_i$ 的下标 $i$ 表示初始状态为从 $i$ 出发。
• $N_i = \sum_{n = 0}^{+\infty} \mathbf{1}_{\{X_n = i\}} = 1 + \sum_{n = 1}^{+\infty} \mathbf{1}_{\{X_n = i\}}$ 表示 到达次数 number of visits。

如果 $f_i = 1$，则称状态 $i$ 是 常反 recurrent 的，否则称状态 $i$ 是 非常返 transient 的。

一个比较基本的引理：

$$ E_i[N_i] = \frac{1}{1 - f_i}. $$

Proof

由 Markovian

\[ N_i = 1 + \mathbf{1}_{{T_i < \infty}} N_i^*, \]

\[ E_i[N_i] = 1 + \Pr_i(T_i < \infty) E_i[N_i] = 1 + f_i E_i[N_i]. \]

故可以得出 $i$ 是常反的当且仅当 $\sum_{n = 0}^{+\infty} \Pr_i(X_n = i) = E_i[N_i] = +\infty$。

$(0, 0)$ 在二维随机游走中的常反性

考虑简单的一维随机游走情况，

$$ \Pr[X_{2n} = 0] = \frac{{2n \choose n}}{2^{2n}} = {2n \choose n} 4^{-n}. $$

由 Stirling 近似，${2m \choose m} \sim \frac{4^m}{\sqrt{\pi m}}$（更一般地有 ${n \choose pn} \sim \frac{2^{n H(p)}}{\sqrt{2 \pi n p(1 - p)}}$，其中 $H(p) = -p \log p - (1 - p) \log (1 - p)$ 是二项分布的熵）。所以

$$ \Pr[X_{2n} = 0] = \frac{4^n}{\sqrt{\pi n}} 4^{-n} (1 + \mathcal O(n^{-1})) = \frac{1}{\sqrt{\pi m}} (1 + \mathcal O(n^{-1})). $$

对于二维的情况，一个经典的 OI 套路是将坐标系旋转 45 度，将每一步看作在 $x$ 轴和 $y$ 轴均走一步，这样两维就独立了。因此

$$ p_{2n} = \Pr[X_{2n} = 0]^2 = \frac{1}{\pi n} (1 + \mathcal O(n^{-1})). $$$$ E_{(0, 0)}[N_{(0, 0)}] = \sum_{n = 0}^{+\infty} p_n = 1 + \sum_{n = 1}^{+\infty} p_{2n} \ge 1 + \frac{1}{\pi} \sum_{n = 1}^{+\infty} \frac{1}{n} = +\infty. $$

因此 $f_{(0, 0)} = 1$。故对于任意状态都有 $f = 1$。

对于 $\geq 3$ 维随机游走，有结论 $f < 1$。即 A drunk man will find his way home, but a drunk bird may get lost forever。

回到马尔可夫链。注意到当 $t \to +\infty$ 时的行为往往是重要的，定义下面的概率分布为 平稳分布：

$$ \a(t) = \frac{1}{t} (\p(0) + \p(1) + \cdots + \p(t - 1)). $$

我们接下来将讨论 $\a(t)$ 的收敛性。

我们称一个马尔可夫链是 连通 的，当且仅当对于任意状态 $i$ 和 $j$，从 $i$ 走若干步移动到 $j$ 的概率都不为 $0$。

对于连通的马尔可夫链所对应的转移概率矩阵 $P$，大小为 $n \times (n + 1)$ 的矩阵 $A = [P - I, \mathbf{1}]$ 为 $P$ 减去 $I$ 后再在右侧添加一列 $1$ 得到，$A$ 的秩为 $n$。

Proof

矩阵 $P - I$ 的每一行和为 $0$，所以 $(1, 1, \ldots, 1, 0)$ 在线性变换 $L_A$​ 的零空间中。

假设存在另一个与其垂直的向量 $\v = (\x, \alpha)$ 在零空间中，则

\[ (P - I) \x + \alpha \mathbf{1} = \mathbf{0} \Longrightarrow \forall i, x_i = \sum_{j} p_{ij} x_j + \alpha. \]

由垂直，$\x^T \mathbf{1} = 0$，则同时存在 $x_i > 0$ 和 $x_j > 0$，也就是 $x_i$ 不全都相等。

由连通性，存在相邻的状态 $(i, j)$ 满足 $x_i > x_j$ 且 $x_i \ge$ 所有邻居，则 $x_i > \sum_j p_{ij} x_j$，推出 $\alpha > 0$。

由连通性，存在相邻的状态 $(i, j)$ 满足 $x_i < x_j$ 且 $x_i \le$ 所有邻居，则 $x_i < \sum_j p_{ij} x_j$，推出 $\alpha < 0$。

得到矛盾。故 $L_A$ 的零空间秩为 $1$，$A$ 的秩为 $n$​。

接下来可以证明，对于任意连通的马尔可夫链，存在 唯一的 概率分布向量 $\mathbf{\pi}$ 满足 $\mathbf\pi P = \mathbf\pi$。进一步地，对于任意初始概率分布，$\lim_{t \to +\infty} \a(t)$ 存在且等于 $\mathbf \pi$。称 $\mathbf\pi$ 为 平稳分布。

我也不知道书上为什么要用 $\mathbf\pi$ 作为变量名。

Proof

令 $\b(t) = \a(t) P - \a(t)$，则

\[ \begin{aligned} \b(t) &= \a(t) P - \a(t) \\ &= \frac{1}{t} [\p(0) P + \cdots + \p(t - 1) P] - \frac{1}{t} [\p(0) + \cdots + \p(t - 1)] \\ &= \frac{1}{t} [\p(1) + \cdots + \p(t)] - \frac{1}{t} [\p(0) + \cdots + \p(t - 1)] \\ &= \frac{1}{t} (\p(t) - \p(0)). \end{aligned} \]

所以当 $t \to +\infty$ 时，$|\b(t)| \le \frac{2}{t} \to 0$。

记矩阵 $B$ 为前文提到的矩阵 $A$ 删去第一列。

由之前的引理，考虑 $L_A$ 的零空间 $(1, \ldots, 1, 0)$，第一列可以由其他列线性组合得到，所以 $B$ 是可逆的。

考虑 $A = [P - I, \mathbf{1}] = [\c_1, \c_2, \ldots, \c_n, \mathbf{1}]$，则

\[ \b(t)_i = \a(t)(P - I)_i = \a(t) \c_i, \]

\[ \a(t) B = [\a(t) \c_2, \ldots, \a(t) \c_n, \a(t) \mathbf{1}] = [\b(t)_{2 \ldots n}, 1]. \]

所以当 $t \to +\infty$ 时，$\a(t) = B^{-1}[0, \ldots, 0, 1]$ 是唯一的。

总结：马尔可夫链在有限连通图上有唯一的平稳分布。

Detailed balance equality (DBE)

若 $\sum_x \pi_x = 1$ 且对于所有 $x, y$ 都有 $\pi_x p_{xy} = \pi_y p_{yx}$，则 $\mathbf\pi$ 是平稳分布，满足 $\mathbf\pi P = \mathbf\pi$。

Proof

$\pi_x p_{xy} = \pi_y p_{yx}$，两侧都对 $y$ 求和得到 $\pi_x = \sum_y \pi_y p_{yx}$。

上述定理的逆命题不成立。即平稳分布不一定满足 DBE，但满足 DBE 的一定是平稳分布。若存在满足 DBE 的平稳分布，则称该链是 时间可逆 time reversible 的。

MCMC algorithms

全称为 Markov chain Monte Carlo，大致思想为构造马尔可夫链并在其中随机游走来对给定的概率分布进行随机采样，这样就可以使用蒙特卡洛方法对期望进行估计。

Example: 磁偶极子 magnetic dipoles

考虑 $x \in \{-1, 1\}^n$ 表示 $n = |V|$ 个方向朝下或朝上的磁偶极子，状态 $x$ 出现的概率为

\[ \pi_\beta^h(x) = \frac{1}{Z(\beta, h)} \exp\l[ \beta \sum_{(i, j) \in E} x_i x_j + h \sum_{i \in V} x_i \r], \]

其中 $Z(\beta, h)$ 为 $\exp(\cdots)$ 关于所有状态 $x$ 之和，以保证概率总和为 $1$。

对上述式子的解释，$\beta$ 一项为磁偶极子之间的相互作用产生的能量，$h$ 一项为关于外部磁场的势能，状态出现的概率与能量指数相关。

上面的解释并不重要，只是举个例子。我也不是学物理的，不知道这样的解释是否严谨。

对于上述例子，如何计算总磁矩的期望大小，即

$$ f(x) = \frac{1}{n} \sum_{i \in V} x_i, \quad \mu := E_{\pi_\beta^h}[f(x)]. $$

当 $n$ 很大时，总状态数为 $2^n$，直接计算 $Z$ 是不可取的。

考虑构造一个马尔可夫链 $P$，使其平稳分布 $\a(t)$ 收敛于 $\pi_\beta^h$，这样就可以用 $\a(t)$ 来对 $x$ 进行采样，从而估计 $f(x)$ 的期望。

算法 1: Metropolis Hastings algorithm

给定目标概率 $\p$，取常数 $r > 1$，构造无向连通图 $G$ 以及矩阵 $P$ 如下：

$$ P_{ij} = \frac{1}{r} \min\l(1, \frac{p_j}{p_i}\r) \text{ if } (i, j) \in E_G, \quad P_{ii} = 1 - \sum_{j \neq i} P_{ij}. $$

显然 $P$ 的每一行和为 $1$，且 $\p$ 满足细致平衡条件：

$$ p_i P_{ij} = \frac{p_i}{r} \min\l(1, \frac{p_j}{p_i}\r) = \frac{1}{r} \min(p_i, p_j) = \frac{p_j}{r} \min\l(1, \frac{p_i}{p_j}\r) = p_j P_{ji}. $$

所以 $\p$ 是平稳分布。而 $P_{ij}$ 只和 $p_i$ 与 $p_j$ 的比值有关，与 $Z$ 有关的项会消去，可以比较简单地对给定的 $i, j$ 求出 $P_{ij}$。

如果 $G$ 是完全图，那么 MHA 还不如直接采样，因为每次转移仍要遍历所有状态。

然而当 $n$ 很大时，对下一个时刻的状态进行采样的复杂度仍然是 $\mathcal O(2^n)$，与状态数同阶。

算法 2: Gibbs sampling

如果状态具有特殊的结构，例如 $d$ 维超立方体 $\x = (x_1, \ldots, x_d)$，则可以考虑随机一维 $i$ 进行转移而不是每一维都转移。

$$ P_{\x \y} = \frac{1}{d} \Pr(y_1 | x_2, \ldots, x_d). $$

系数 $\frac{1}{d}$ 来源于随机选取 $d$ 维中的一维。不难验证

$$ \sum_{i = 1}^{d} \sum_{y_i} \Pr(y_i | x_1, \ldots, x_{i - 1}, x_{i + 1}, \ldots, x_d) = d, $$

以及

$$ P_{\x \y} = \frac{1}{d} \frac{\Pr(y_1 | x_{2 \sim d}) \Pr(x_{2 \sim d})}{\Pr(x_{2 \sim d})} = \frac{1}{d} \frac{p_\y}{\Pr(x_{2 \sim d})}. $$

同理

$$ P_{\y \x} = \frac{1}{d} \frac{p_\x}{\Pr(y_{2 \sim d})} = \frac{1}{d} \frac{p_\x}{\Pr(x_{2 \sim d})}. $$

所以 $\p$ 是平稳分布。

这两种方法也并非能够高效地采样任意分布。

考虑最小点覆盖问题，定义 $H(\sigma) = |\sigma|$ 如果 $\sigma$ 覆盖了所有边，否则 $H(\sigma) = +\infty$。给定常数 $\beta$，定义

\[ \pi_\beta(\sigma) = \frac{\e^{-\beta H(\sigma)}}{Z} \]

为正规化后得到的分布，则

\[ \lim_{\beta \to +\infty} \pi_\beta(\sigma) = \begin{cases} \frac{1}{|C_{\min}|} & \sigma \in C_{\min}, \\ 0 & \text{otherwise}. \end{cases} \]

其中 $C_{\min}$ 是最小点覆盖方法的集合。在这个分布上跑 MCMC 的效果会很差，因为最小点覆盖是 NPC。

混合时间 mixing time

给定 $\eps > 0$，定义一个马尔可夫链的 $\eps$-混合时间 $\eps$-mixing time 为最小的整数 $t$ 满足对于任意初始概率分布 $\p$，都有 $\|a(t) - \mathbf\pi\|_1 \le \eps$。

混合时间衡量了一个 MC 收敛到平稳分布的速度。

对于两个概率分布 $\p$ 和 $\q$，总有

$$ \|\p - \q\|_1 = 2 \sum_{i} (p_i - q_i)^+ = 2 \sum_{i} (q_i - p_i)^+, $$

其中 $x^+$ 表示 $\max(0, x)$。画个图算面积即可证明。

直觉上，图的连通性越强，混合时间就应该越小。对于一个割集 $S$ 和 $\overline{S}$，考虑衡量 $S$ 与 $\overline{S}$ 之间的连通度。设 $\pi(S) = \sum_{x \in S} \pi_x$，$Q(S) = \sum_{(x, y) \in (S, \overline{S})} \pi_x p_{xy}$。则对于非空真子集 $S$，定义 归一化传导率 normalized conductance 为

$$ \Phi(S) = \frac{Q(S)}{\min(\pi(S), \pi(\overline{S}))}. $$

对于可逆 MC，由 DBE 可以知道 $Q(S) = Q(\overline{S})$。因此 $\Phi(S) = \Phi(\overline{S})$。不妨设 $\Phi(S) \le \Phi(\overline{S})$，那么 $\Phi(S) = \frac{Q(S)}{\pi(S)}$，可以理解为「表面积」除以「体积」。

$\Phi(S)$ 表示对于平稳分布在 $S$ 内的部分，有多大的概率下一步从 $S$ 走到 $\overline{S}$。那么我们至少需要访问所有状态，因此混合时间有下界

$$ \sum_{i = 1}^{+\infty} i (1 - \Phi(S))^{i - 1} \Phi(S) = \frac{1}{\Phi(S)}. $$

定义该 MC 的归一化传导率为

$$ \Phi = \min_{0 < \pi(S) \le 0.5} \Phi(S). $$

则 $\eps$-混合时间有上界

$$ \mathcal O\l( \frac{\ln(1 / \pi_{\min})}{\Phi^2 \eps^3} \r). $$

Proof

TL;DR

可以由此算出特殊图的混合时间：

• $n$ 个点的环：砍一半，$\Phi = \Theta(\frac{1}{n})$，混合时间 $\mathcal O(\eps^{-3} n^2 \log n)$。
• $n \times n$ 的网格图：砍一半，$\Phi = \Omega(\frac{1}{n})$，混合时间 $\mathcal O(\eps^{-3} n^2 \log n)$。
• $n^d$ 的网格图：可以证明 $\Phi = \Omega(\frac{1}{dn})$。
• $n$ 个点的团：砍一半，$\Phi = \frac{1}{2}$。
• $m$ 条边的连通图：$\pi_x = \frac{d_x}{2m}$，所以 $\pi_x p_{xy} = \frac{1}{2m}$。于是 $\Phi = \Omega(\frac{1}{m})$，混合时间 $\mathcal O(\eps^{-3} m^2 \log n)$。

---