测度集中

对于伯努利的大数定理，其收敛的具体速率有：

• 切比雪夫不等式给出：$< \dfrac{p(1-p)}{n \varepsilon^2} \le \dfrac{1}{4n \varepsilon^2}$
• CLT 给出 Gaussian-like $\exp\left(-\Omega(\varepsilon^2 n)\right)$

对于 $X_1, \dots, X_n \in \left\lbrace 0, 1 \right\rbrace$ 为独立随机试验（independent trials, 泊松试验, Poisson trials），它们不一定同分布，并令

$$S_n = \sum_{i=1}^{n} X_i$$

为泊松二项随机变量（Poisson binomial random vairable）

下面讨论其偏差集中的尾界（Deviation/concentration/tail bounds）：

$$\Pr(|S_n - \mathbb{E}[S_n] | \ge \mathord{?}) \le \mathord{?}$$

切尔诺夫-霍夫丁界（Chernoff-Hoeffding Bound）

切尔诺夫界

令 $X_1, \dots, X_n \in \left\lbrace 0, 1 \right\rbrace$ 是独立试验，有

$$X = \sum_{i=1}^{n} X_i\quad \mu = \mathbb{E}[X]$$

对任意 $\delta > 0$ 有

$$\boxed{\Pr(X \ge (1+\delta)\mu) \le \left(\dfrac{\e^\delta}{(1+\delta)^{1+\delta}}\right)^\mu}$$

证明

$$\begin{aligned} \Pr(X \ge (1+\delta)\mu) &= \Pr(\e^{tX} \ge \e^{t(1+\delta)\mu}) \\ &\le \e^{-t(1+\delta)\mu} \mathbb{E}[e^{tX}] \qquad\text{(Markov 不等式)} \end{aligned}$$

随机变量 $X$ 的 MGF 为

$$M_X(t) = \mathbb{E}[\e^{t X}] = \sum_{k \ge 0} \dfrac{t^{k}\mathbb{E}[X^{k}]}{k!}$$

若 $X_1, \dots, X_n \in \left\lbrace 0, 1 \right\rbrace$ 是独立的，且 $X = \sum\limits_{i=1}^n X_i$ 与 $\mu = \mathbb{E}[X]$，则有

$$M_X(t) = \mathbb{E}[\e^{tX}] \le \e^{(\e^t - 1)\mu}$$

因为

$$\begin{aligned} \mathbb{E}[\e^{tX}] &= \mathbb{E}\left[ \prod_{i=1}^{n}\e^{tX_i} \right] \\ &= \prod_{i=1}^{n}\mathbb{E}[\e^{tX_i}] \\ &= \prod_{i=1}^{n}\left(\e^t p_i + (1-p_i)\right)\qquad (p_i = \mathbb{E}[X_i])\\ &\le \prod_{i=1}^{n}\e^{p_i(\e^t - 1)} \\ &= \e^{(\e^t - 1)\mu} \end{aligned}$$

继续上面的步骤有

$$\begin{aligned} \Pr(X \ge (1+\delta)\mu) &= \Pr(\e^{tX} \ge \e^{t(1+\delta)\mu}) \\ &\le \e^{-t(1+\delta)\mu} \mathbb{E}[e^{tX}] \qquad\text{(Markov 不等式)}\\ &\le \e^{-t(1+\delta)\mu} \e^{(\e^t - 1)\mu} \\ &= \e^{\mu(\e^t - 1 - t(1+\delta))} \\ &= \left( \dfrac{\e^{\delta}}{(1+\delta)^{1+\delta}} \right)^\mu\qquad(t = \ln(1+\delta)) \end{aligned}$$

对任意 $0 < \delta < 1$ 有

$$\boxed{\Pr(X \le (1-\delta)\mu) \le \left(\dfrac{\e^{-\delta}}{(1-\delta)^{1-\delta}}\right)^\mu}$$

证明

类似地，有

$$\begin{aligned} \Pr(X \le (1-\delta)\mu) &= \Pr(\e^{tX} \ge \e^{t(1-\delta)\mu})\qquad(t < 0)\\ &\le \e^{-t(1-\delta)\mu} \mathbb{E}[e^{tX}] \\ &\le \e^{-t(1-\delta)\mu} \e^{(\e^t - 1)\mu} \\ &= \e^{\mu(\e^t - 1 - t(1-\delta))} \\ &= \left( \dfrac{\e^{-\delta}}{(1-\delta)^{1-\delta}} \right)^\mu\qquad(t = \ln(1-\delta)) \end{aligned}$$

对任意 $\delta > 0$ 有

$$\Pr(X \ge (1 + \delta) \mu) \le \left( \dfrac{\e^{\delta}}{(1+\delta)^{1+\delta}} \right)^\mu \le \begin{cases} \e^{- \frac{\mu \delta^2}{3}} & \text{if } 0 < \delta \le 1 \\ 2^{-(1+\delta)\mu} & \text{if } (1 + \delta) \ge 2\e \end{cases}$$

对任意 $0 < \delta < 1$ 有

$$\Pr(X \le (1 - \delta) \mu) \le \left( \dfrac{\e^{-\delta}}{(1-\delta)^{1-\delta}} \right)^\mu \le \e^{- \frac{\mu \delta^2}{2}}$$

Balls into Bins

将 $m$ 个球 u.a.r. 扔进 $n$ 个桶，随机变量 $X_i$ 表示第 $i$ 个桶中的球数，有 $(X_1, X_2, \dots, X_n) \sim$ 参数为 $m, \bigl(\overbrace{\tfrac{1}{n}, \dots, \tfrac{1}{n}}^n\Bigr)$ 的多项式分布。

占用问题（Occupancy problem）：最大负载（load）$\max\limits_{1\le i\le n}X_i$ w.h.p.

$$\max_{1\le i\le n}X_i = \begin{cases} O\left( \dfrac{\log n}{\log \log n} \right) &\text{if }m = n\\ O\left(\dfrac{m}{n}\right) &\text{if }m \ge n \ln n \end{cases}$$

边缘分布有 $X_i \sim \operatorname{Bin}(m, \frac{1}{n})$ 与 $\mu = \mathbb{E}[X_i] = \dfrac{m}{n}$。

当 $m = n$ 时，有 $\mu = 1$，有

$$\begin{aligned} \Pr(X_i \ge L)&= \Pr(X_i \ge L \mu)\\ &\le \dfrac{\e^L}{\e L^L}\\ &\le \dfrac{1}{n^2} \end{aligned}$$

对于 $L = \dfrac{\e \ln n}{\ln \ln n}$ 成立。因为切尔诺夫界 $\Pr(X_i \ge (1+\delta)\mu) \le \left( \dfrac{\e^{\delta}}{(1+\delta)^{1+\delta}} \right)^\mu$。

并集界（Union bound）给出

$$\begin{aligned} \Pr\left(\max_{1\le i\le n}X_i \ge L\right) &\le \sum_{i=n}^{n} \Pr(X_i \ge L)\\ &\le \dfrac{1}{n} \end{aligned}$$

因此 $\max\limits_{1\le i\le n}X_i = O\left( \dfrac{\log n}{\log \log n} \right)$ w.h.p.

当 $m \ge n \ln n$ 时，有 $\mu \ge \ln n$，有

$$\begin{aligned} \Pr\left( X_i \ge \dfrac{2\e m}{n} \right) &= \Pr(X_i \ge 2\e \mu)\\ &\le 2^{-2 \e \mu}\\ &\le 2^{-2 \e \ln n}\\ &\le \dfrac{1}{n^2} \end{aligned}$$

因为 $L \ge 2 \e \mu$ 时有 $\Pr(X_i \ge L) \le 2^{-L}$（切尔诺夫界）。

同样使用并集界可以得到 $\max\limits_{1\le i\le n}X_i = O\left(\dfrac{m}{n}\right)$ w.h.p.

霍夫丁界

切尔诺夫不等式（Chernoff's Inequality）

令 $X_1, \dots, X_n \in \left\lbrace 0, 1 \right\rbrace$ 为独立随机变量，且 $S_n = \displaystyle \sum_{i=1}^{n}X_i$，则对任意 $t > 0$ 有

$$\Pr\left(\left\lvert S_n - \mathbb{E}[S_n] \right\rvert \ge t\right) \le 2 \exp\left(-\dfrac{2t^2}{n}\right)$$

霍夫丁不等式（Hoeffding's Inequality）

令 $X_1, \dots, X_n$ 是独立随机变量，$S_n = \displaystyle \sum_{i=1}^{n} X_i$，且 $X_i \in [a_i, b_i]$，则对任意 $t > 0$ 有

$$\Pr\left(\left\lvert S_n - \mathbb{E}[S_n] \right\rvert \ge t\right) \le 2 \exp\left(-\dfrac{2t^2}{\sum_{i=1}^{n}(b_i - a_i)^2}\right)$$

霍夫丁引理（Hoeffding's Lemma）*

霍夫丁引理（Hoeffding's Lemma）

若 $X \in [a, b]$ a.s. 且 $\mathbb{E}[X] = 0$，则

$$M_X(\lambda) = \mathbb{E}[\e^{\lambda X}] \le \e^{\lambda^2(b-a)^2/8}$$

证明

因为 $\e^{\lambda x}$ 是凸函数，有

$$\e^{\lambda x} \le \dfrac{b-x}{b-a}\e^{\lambda a} + \dfrac{x-a}{b-a}\e^{\lambda b}$$

对任意 $x \in [a, b]$ 成立。

于是

$$\begin{aligned} \mathbb{E}\left[ \e^{\lambda X} \right] &\le \dfrac{b - \mathbb{E}[X]}{b - a}\e^{\lambda a} + \dfrac{\mathbb{E}[X] - a}{b - a}\e^{\lambda b}\\ &= \dfrac{b}{b-a}\e^{\lambda a} - \dfrac{a}{b-a}\e^{\lambda b}\\ \end{aligned}$$

令 $L(h) = \dfrac{ha}{b-a} + \ln\left( 1 + \dfrac{a - \e^h a}{b-a} \right)$，则有

$$\begin{aligned} \e^{L(\lambda(b-a))} &= \exp \left(a \lambda + \ln \dfrac{b - a \e^{\lambda(b-a)}}{b-a} \right) \\ &= \e^{a \lambda} \left( \dfrac{b - a\e^{\lambda(b-a)}}{b-a} \right) \\ &= \dfrac{b}{b-a}\e^{\lambda a} - \dfrac{a}{b-a}\e^{\lambda b} \end{aligned}$$

即 $\mathbb{E}\left[ \e^{\lambda X} \right] \le \e^{L(\lambda(b-a))}$。

而泰勒公式有

$$\begin{aligned} L(h) &= L(0) + L'(0)h + \dfrac{L''(\xi)}{2}h^2\quad (0 < \xi < h)\\ &= \dfrac{L''(\xi)}{2} h^2\\ &= \dfrac{|a| b \e^{\xi}}{(b + |a| \e^{\xi})^2} \cdot \dfrac{1}{2}h^2\\ &\le \dfrac{|a| b \e^{\xi}}{(2 \sqrt{b |a| \e^{\xi}})^2} \cdot \dfrac{1}{2}h^2\\ &= \dfrac{1}{8}h^2 \end{aligned}$$

从而 $\mathbb{E}\left[ \e^{\lambda X} \right] \le \e^{L(\lambda(b-a))} \le \e^{\lambda^2(b-a)^2/8}$。

霍夫丁界证明

令 $Y_i = X_i - \mathbb{E}[X_i]$ 与 $Y = S_n - \mathbb{E}[S_n] = \sum_{i=1}^{n}Y_i$，于是 $\mathbb{E}[Y] = \mathbb{E}[Y_i] = 0$。

则

$$\begin{aligned} \Pr(S_n - \mathbb{E}[S_n] \ge t) &= \Pr(Y \ge t)\\ &\le \Pr(\e^{\lambda Y} \ge \e^{\lambda t})&(\lambda > 0)\\ &\le \e^{-\lambda t}\mathbb{E}[\e^{\lambda Y}]&\text{(Markov 不等式)}\\ &= \e^{-\lambda t}\mathbb{E}\left[\prod_{i=1}^{n}\e^{\lambda Y_i}\right]\\ &= \e^{-\lambda t}\prod_{i=1}^{n}\mathbb{E}[\e^{\lambda Y_i}]\\ &\le \exp\left(-\lambda t + \frac{\lambda^2}{8}\sum_{i=1}^{n}(b_i - a_i)^2\right) &\text{(Hoeffding 引理)}\\ &= \exp\left(- \dfrac{2t^2}{\sum_{i=1}^{n}(b_i - a_i)^2}\right)&\left(\lambda = \dfrac{4t}{\sum_{i=1}^{n}(b_i - a_i)^2}\right) \end{aligned}$$

亚高斯尾（Sub-Gaussian Tail）

若 $X_1, \dots, X_n \in \left\lbrace 0, 1 \right\rbrace$ 是独立泊松试验，同时 $S_n = \displaystyle \sum_{i=1}^{n} X_i$，则对任意 $t > 0$ 有切尔诺夫-霍夫丁界

$$\Pr\left(\left\lvert \dfrac{S_n - \mathbb{E}[S_n]}{\sqrt{n} / 2} \right\rvert \ge t\right) \le 2 \exp\left(-\dfrac{t^2}{2}\right)$$

注意到 $\sigma(S_n) = \sqrt{\displaystyle \sum_{i=1}^{n}\operatorname{Var} [X_i]} \le \dfrac{\sqrt{n}}{2}$（伯努利随机方差至多为 $\dfrac{1}{4}$），于是标准化的 $S_n$ 最差程度上有「亚高斯尾」（Sub-Gaussian Tail）$\e^{-\Omega(t^2)}$。

对于一般的独立的 $X_i \in [a_i, b_i]$，令 $S_n = \displaystyle \sum_{i=1}^{n}X_i$，则对任意 $t > 0$ 有

$$\Pr\left(\left\lvert \dfrac{S_n - \mathbb{E}[S_n]}{\sum_{i=1}^{n}(b_i - a_i)^2 / 4} \right\rvert \ge t\right) \le 2 \exp\left(-\dfrac{t^2}{2}\right)$$

而 $Z \in [a, b]$ 可得 $\left\lvert Z - \dfrac{a+b}{2} \right\rvert \le \dfrac{b-a}{2}$。于是有

$$\begin{aligned} \operatorname{Var} [Z] &= \operatorname{Var} \left[Z - \dfrac{a+b}{2}\right]\\ &\le \mathbb{E}\left[\left(Z - \dfrac{a+b}{2}\right)^2\right]\\ &\le \dfrac{(b-a)^2}{4} \end{aligned}$$

最后一个不等号是因为，对于任意 $Z \in [a, b]$，有

$$\begin{aligned} \mathbb{E}\left[\left( Z - \dfrac{a+b}{2}\right)^2 \right] &\le \dfrac{1}{2}\left(a - \dfrac{a+b}{2}\right)^2 + \dfrac{1}{2}\left(b - \dfrac{a+b}{2}\right)^2\\ &= \dfrac{(b-a)^2}{4} \end{aligned}$$

于是同样的有标准化的 $S_n$ 最差程度上有「亚高斯尾」$\e^{-\Omega(t^2)}$。

控制公平投票

前提假设不完全提及了。在一个社会中有 $n$ 个独立随机选民。令 $S_n = X_1 + \dots + X_n$ 是 $n$ 个 i.i.d. 的参数为 $\dfrac{1}{2}$ 的伯努利随机变量的和，则有

$$\begin{aligned} \Pr\left( \left\lvert S_n - (n - S_n) \right\rvert \ge t \right) &= \Pr\left( \left\lvert 2S_n - n \right\rvert \ge t \right)\\ &= \Pr\left( \left\lvert S_n - \dfrac{n}{2} \right\rvert \ge \dfrac{t}{2} \right)\\ &= \Pr\left( \left\lvert S_n - \mathbb{E}[S_n] \right\rvert \ge \dfrac{t}{2} \right) \\ &\le 2\exp\left( - \dfrac{t^2}{2n} \right) \\ &\le \delta \end{aligned}$$

于是只需令 $t \ge \sqrt{2 n \ln(2 / \delta)}$ 即可以 $1 - \delta$ 的确定性操纵一个公平的投票。

双侧误差减小（Error Reduction two-sided case）

前提假设跟上面一样不认真写了，毕竟前面都有：

• 决定性问题 $f\colon \left\lbrace 0, 1 \right\rbrace^{*} \to \left\lbrace 0, 1 \right\rbrace$；
• 蒙特卡洛随机算法 $\mathscr{A}$ 有双侧误差 $\forall x \in \left\lbrace 0, 1 \right\rbrace^{*},\, \Pr(\mathscr{A}(x) = f(x)) \ge \dfrac{1}{2} + p$；
• $\mathscr{A}^n$ 为独立运行 $\mathscr{A}$ 算法 $n$ 次，返回 $n$ 次结果的多数。

令 $S_n = X_1, \dots, X_n$，其中 $X_i$ 是第 $i$ 次运行 $\mathscr{A}$ 正确与否的指示随机变量，则有

$$\begin{aligned} \Pr(\mathscr{A}^n(x) \ne f(x)) &= \Pr\left( S_n \le \dfrac{n}{2} \right) \\ &= \Pr\left( S_n \le \mathbb{E}[S_n] - pn \right) \\ &\le \exp(- 2p^2 n)\\ &\le \delta \end{aligned}$$

于是 $n \ge \dfrac{1}{2p^2} \ln \dfrac{1}{\delta}$ 时，可以有 $1 - \delta$ 的确定性输出正确的结果。

中位数技巧（Median Trick）

• 计算性问题（Computation problem）$f\colon \left\lbrace 0, 1 \right\rbrace^{*} \to\R$；
• 随机近似算法 $\mathscr{A}\colon \left\lbrace 0, 1 \right\rbrace^{*},\, \Pr\left( \mathscr{A}(x) \in (1 \pm \epsilon)f(x) \right) \ge \dfrac{1}{2} + p$；
• $\mathscr{A}^n$ 为独立运行 $\mathscr{A}$ 算法 $n$ 次，返回 $n$ 次结果的中位数。

令 $X_i$ 是第 $i$ 次运行 $\mathscr{A}$ 的输出在 $f(x)$ 的 $\epsilon$ 邻域的指示随机变量，则 $\mathbb{E}[X_i] \ge \dfrac{1}{2} + p$。

则有 $\mathscr{A}^n(x) \in (1\pm \epsilon) f(x)$ 若 $S_n=X_1, \dots, X_n > \dfrac{n}{2}$。

于是

$$\begin{aligned} \Pr(\mathscr{A}(x) \notin (1 \pm \epsilon)f(x)) &\le \Pr(S_n \le \dfrac{n}{2})\\ &\le \Pr(S_n \le \mathbb{E}[S_n] - np)\\ &\le \exp(- 2p^2 n)\\ &\le \delta \end{aligned}$$

于是可令 $n \ge \dfrac{1}{2p^2}\ln \dfrac{1}{\delta}$ 时，可以有 $1 - \delta$ 的确定性输出正确的结果。

$k$ 阶矩界

假设 $X$ 期望为 $0$，切尔诺夫界实际上是

$$\Pr[|X| \ge \delta] \le \min_{t \ge 0} \mathbb{E}\left[ \e^{t |X|} \right] \e^{-t \delta}$$

对于 $k$ 阶矩有

$$\Pr[|X| \ge \delta] \le \mathbb{E}\left[ |X|^{k} \right] \delta^{-k}$$

The Method of Bounded Differences (有界差分方法)

McDiarmid 不等式

McDiarmid 不等式

令 $X_1, \dots, X_n$ 是独立随机变量，且 $X_i \in \mathscr{X}_i$，若 $f\colon \mathscr{X}_1, \dots, \mathscr{X}_n \to\R$ 满足「有界差分性质」（bounded differences property）

$$\forall i,\, \sup_{x_i \in \mathscr{X}_i, x_{j}' \in \mathscr{X}_{j}} \left\lvert f(x_1, \dots, x_n) - f(x_1, \dots, x_{j-1}, x_{j}', x_{j+1}, \dots, x_n) \right\rvert \le c_{j}$$

则对任意 $t > 0$ 有

$$\Pr\left(\left\lvert f(X_1, \dots, X_n) - \mathbb{E}[f(X_1, \dots, X_n)] \right\rvert \ge t \right) \le 2 \exp\left(-\dfrac{2t^2}{\sum_{i=1}^{n}c_{i}^2}\right)$$

霍夫丁不等式：$f$ 为 $[a_i, b_i]$ 有界变量的和。

任意满足利普希茨条件（Lipschitz）的函数近似是一个乘积测度上的常函数（瞎翻译，原文看下面）。

Hoeffding's inequality: $f$ is sum of $[a_i, b_i]$-bounded variables

Every Lipschitz function is approximately a constant function in product measures.

模式匹配

相关内容可参考前面的笔记。

$s = (s_1, \dots, s_n) \in Q^n$ 为均匀随机字符串，有 $n$ 个从字母表 $Q$ 中独立随机选择的字符，其中 $|Q| = q$。

对于模式 $\pi \in \Q^{k}$，令 $X$ 是 $s$ 中 $\pi$ 出现的次数，线性性质有

$$\mathbb{E}[X] = \sum_{i=1}^{n-k+1} = \mathbb{E}[I_i] = (n-k+1)q^{-k}$$

其中 $I_i$ 是从 $i$ 开始的子串是否匹配 $\pi$。

McDiarmid 不等式有

$$\begin{aligned} \Pr\left( \left\lvert X - \mathbb{E}[X] \right\rvert > t\right) \le 2\exp\left(-\dfrac{2t^2}{nk^2}\right) \end{aligned}$$

空桶

$m$ 球扔进 $n$ 桶，令 $Y$ 为空桶的数目，有

$$Y = \sum_{i=1}^{n} I_i$$

其中 $I_i$ 是第 $i$ 个桶是否为空的指示随机变量。

期望的线性性质有

$$\mathbb{E}[Y] = n\left(1 - \dfrac{1}{n}\right)^m$$

那么偏差 $\Pr\left( |Y - \mathbb{E}[Y]| \ge t \right)$ 的上界应该为多少呢？

令 $X_i \in [n]$ 表示获得第 $i$ 个球的桶的编号。则有

$$Y = n - |\{X_1, \dots, X_m\}|$$

有 $1$ 有界差分（$1$-bounded differences）。

于是运用 McDiarmid 不等式有

$$\Pr\left( |Y - \mathbb{E}[Y]| \ge t \right) \le 2\exp\left(-\dfrac{2t^2}{m}\right)$$

Doob 序列

$n$ 元函数 $f\colon\R^n \to\R$ 上随机变量 $X_1, \dots, X_n$ 的 Doob 序列（Doob sequence）$Y_0, Y_1, \dots, Y_n$ 定义为

$$\left\lbrace\begin{aligned} Y_0 &= \mathbb{E}[f(X_1, \dots, X_n)]\\ Y_i &= \mathbb{E}[f(X_1, \dots, X_n) \mid X_1, \dots, X_i] \end{aligned}\right.$$

也就是说有从 $Y_0 = \mathbb{E}[f(X_1, \dots, X_n)]$ 无信息，到 $Y_n = f(X_1, \dots, X_n)$，给出了全信息。

鞅性质（Martingale Property）

$$\mathbb{E}[Y_i \mid X_1, \dots, X_{i-1}] = Y_{i-1}$$

证明

$$\begin{aligned} \mathbb{E}[Y_i \mid X_1, \dots, X_{i-1}] &= \mathbb{E}\left[\mathbb{E}[f(X_1, \dots, X_n) \mid X_1, \dots, X_i] \mid X_1, \dots, X_{i-1}\right]\\ &= \mathbb{E}[f(X_1, \dots, X_n) \mid X_1, \dots, X_{i-1}]\\ &= Y_{i-1} \end{aligned}$$

第二个等号是因为 $\mathbb{E}[\mathbb{E}[Z \mid Y, X] \mid X] = \mathbb{E}[Z \mid X]$，证明如下：

$$\begin{aligned} \mathbb{E}[\mathbb{E}[Z \mid Y, X] \mid X] &= \sum_e e \cdot \Pr(\mathbb{E}[Z \mid Y, X] = e \mid X)\\ &= \sum_e e \cdot \Pr(Z = e \mid X)\\ &= \mathbb{E}[Z \mid X] \end{aligned}$$

鞅

亏损加仓投注赌博策略也称为「鞅」（Martingale）策略。

定义

鞅

鞅是一个随机过程，其条件期望是给定过去所有信息的期望。

令 $\left\lbrace X_n \colon n \ge 0 \right\rbrace$ 是一个随机过程，若 $\left\lbrace Y_n\colon n \ge 0 \right\rbrace$ 对任意 $n$ 有「鞅性质」（martingale property）：

$$\boxed{\mathbb{E}[Y_{n+1} \mid X_0, X_1, \dots, X_n] = Y_n}$$

且 $\mathbb{E}[|Y_n|] < \infty$，则称序列 $\left\lbrace Y_n\colon n \ge 0 \right\rbrace$ 是一个鞅（martingale）。

根据定义，$Y_n$ 是 $X_0, X_1, \dots, X_n$ 的函数。

鞅是一个公平的过程，因为在任意时刻 $n$，$Y_n$ 的期望等于 $Y_{n-1}$ 的期望。另有：

• 上鞅（super-martingale）：$\mathbb{E}[Y_{n+1} \mid X_1, \dots, X_n] \le Y_n$
• 下鞅（sub-martingale）：$\mathbb{E}[Y_{n+1} \mid X_1, \dots, X_n] \ge Y_n$

$\left\lbrace X_n\colon n \ge 0 \right\rbrace$ 定义在概率空间 $(\Omega, \Sigma, \Pr)$ 上，有：

• $(X_0, X_1, \dots, X_n)$ 定义了一个子 $\sigma$-代数 $\Sigma_n \subseteq \Sigma$；
  • 也是最小的使得 $(X_0, \dots, X_n)$ 是 $\Sigma_n$ 可测的 $\sigma$-代数。
• $\left\lbrace \Sigma_n\colon n\ge 0 \right\rbrace$ 是 $\Sigma$ 的一个过滤（filtration），即 $\Sigma_0 \subseteq \Sigma_1 \subseteq \dots \subseteq \Sigma$；
• 鞅性质可表示为 $\mathbb{E}[Y_{n+1} \mid \Sigma_n] = Y_n$。

随着 $n$ 的增大，$\Sigma_n$ 表示越来越多的已知信息。$\Sigma_n$ 包含了从 $t = 0$ 到 $t = n$ 的所有信息。

例子

• Doob 鞅
• 公平赌博游戏
• 公平一维随机游走（unbiased 1D random walk）
• 棣莫弗鞅
• Polya 的瓮：瓮有不同颜色的弹珠，每轮均匀随机选择一个弹珠，然后换成 $k$ 个相同颜色的弹珠。

研究

• 鞅的测度集中（尾不等式）：在什么情况下有 $\Pr(|Yn - Y_0| \ge t) \le \mathord{?}$。
• 可选停止定理（OST, optional stopping theorem original sound track）：在什么情况下对于一个停止时 $\tau$ 有 $\mathbb{E}[Y_{\tau}] = \mathbb{E}[Y_0]$。

鞅尾不等式

吾妻不等式（Azuma's inequality）

若序列 $\left\lbrace Y_n\colon n \ge 0 \right\rbrace$ 是对某个序列 $\left\lbrace X_n\colon n \ge 0 \right\rbrace$ 的一个鞅，且对任意 $n \ge 1$ 有

$$|Y_n - Y_{n-1}| \le c_n$$

则对任意 $n \ge 1$ 与 $t > 0$ 有

$$\boxed{\Pr\left( |Y_n - Y_0| \ge t \right) \le 2 \exp\left(-\dfrac{2t^2}{\sum_{i=1}^{n}c_i^2}\right)}$$

该不等式以日本数学家「吾妻一兴」（Azuma Kazuoki）命名。

证明

差分 $D_i = Y_i - Y_{i-1}$ 与和 $S_n = \displaystyle \sum_{i=1}^{n}D_i = Y_n - Y_0$，则目标是证明

$$\Pr\left( |S_n| \ge t \right) \le 2 \exp\left( - \dfrac{2t^2}{\sum_{i=1}^{n}c_i^2} \right)$$

$\left\lbrace Y_n\colon n \ge 0 \right\rbrace$ 是鞅 w.r.t. $\left\lbrace X_n\colon n \ge 0 \right\rbrace$，则有

$$\begin{aligned} \mathbb{E}[D_n \mid X_0, \dots, X_{n-1}] &= \mathbb{E}[Y_n - Y_{n-1} \mid X_0, \dots, X_{n-1}]\\ &= \mathbb{E}[Y_n \mid X_0, \dots, X_{n-1}] - \mathbb{E}[Y_{n-1} \mid X_0, \dots, X_{n-1}]\\ &= Y_{n-1} - Y_{n-1}\\ &= 0 \end{aligned}$$

由于 $D_i$ 是有界的，则

$$\begin{aligned} D_n = Y_n - Y_{n-1}\in [-a_n, b_n] \end{aligned}$$

其中 $b_n - a_n = c_n$。

霍夫丁引理有，因为 $\mathbb{E}[D_n \mid X_0, \dots, X_{n-1}] = 0$ 与 $D_n \in [-a_n, b_n]$ 对于 $b_n - a_n = c_n$，则有

$$\mathbb{E}[\e^{\lambda D_n} \mid X_0, \dots, X_{n-1}] \le \e^{\lambda^2c_n^2/8}$$

而

$$\begin{aligned} \textcolor{ff0099}{\mathbb{E}[\e^{\lambda S_n}]} &= \mathbb{E}[\mathbb{E}[e^{\lambda S_n} \mid X_0, \dots, X_{n-1}]]\\ &= \mathbb{E}[\mathbb{E}[\e^{\lambda(S_{n-1}+D_n)} \mid X_0, \dots, X_{n-1}]]\\ &= \mathbb{E}[\e^{\lambda S_{n-1}}\mathbb{E}[\e^{\lambda D_n} \mid X_0, \dots, X_{n-1}]]\\ &\le \mathbb{E}[\e^{\lambda S_{n-1}}\e^{\lambda^2c_n^2/8}]\\ &= \e^{\lambda^2 c_n^2 / 8} \textcolor{ff0099}{\mathbb{E}[\e^{\lambda S_{n-1}}]} \end{aligned}$$

从而得

$$\mathbb{E}[\e^{\lambda S_n}] \le \exp\left( \dfrac{\lambda^2}{8}\sum_{i=1}^{n}c_i^2 \right)$$

上尾

$$\begin{aligned} \Pr(Y_n - Y_0 \ge t) &= \Pr(S_n \ge t)\\ &\le \Pr(\e^{\lambda S_n} \ge \e^{\lambda t})\\ &\le \e^{-\lambda t} \mathbb{E}[\e^{\lambda S_n}] &\text{(Markov 不等式)}\\ &\le \exp\left( -\lambda t + \dfrac{\lambda^2}{8}\sum_{i=1}^{n}c_i^2 \right)\\ &= \exp\left( -\dfrac{2t^2}{\sum_{i=1}^{n}c_i^2} \right) &\left(\lambda = \dfrac{4t}{\sum_{i=1}^{n}c_i^2}\right) \end{aligned}$$

下尾（类似，不过 $\lambda < 0$）

$$\begin{aligned} \Pr(Y_n - Y_0 \le -t) &= \Pr(S_n \le -t)\\ &\le \Pr(\e^{-\lambda S_n} \ge \e^{-\lambda t})\\ &\le \e^{\lambda t} \mathbb{E}[\e^{-\lambda S_n}] &\text{(Markov 不等式)}\\ &\le \exp\left( \lambda t + \dfrac{\lambda^2}{8}\sum_{i=1}^{n}c_i^2 \right)\\ &= \exp\left( -\dfrac{2t^2}{\sum_{i=1}^{n}c_i^2} \right) &\left(\lambda = -\dfrac{4t}{\sum_{i=1}^{n}c_i^2}\right) \end{aligned}$$

Doob 序列与吾妻不等式可得到 McDiarmid 不等式：

若随机向量 $\mathbf{X} = (X_1, \dots, X_n)$ 的函数 $f(\mathbf{X})$ 满足平均情况差分有界性质（average-case bounded differences property）：

$$\left\lvert \mathbb{E}\left[ f(\mathbf{X}) \mid X_1, \dots, X_i \right] - \mathbb{E}\left[ f(\mathbf{X} \mid X_1, \dots, X_{i-1}) \right] \right\rvert \le c_i$$

则有对任意 $t > 0$ 有

$$\Pr\left( \left\lvert f(\mathbf{X}) - \mathbb{E}[f(\mathbf{X})] \right\rvert \ge t \right) \le 2 \exp\left(-\dfrac{2t^2}{\sum_{i=1}^{n}c_i^2}\right)$$

若 $X_i \in \mathscr{X}_i$ 相互独立，且 $f\colon \mathscr{X}_1, \dots, \mathscr{X}_n \to\R$ 满足有界差分性质，那么 $f(\mathbf{X})$ 满足平均情况差分有界性质，从而有 McDiarmid 不等式。

随机图

图参数（graph parameter）$f(G)$ 可以是：上色数、团数等。

边 exposure 鞅是

$$Y_i = \mathbb{E}[f(G) \mid X_1, \dots, X_i],\quad 1 \le i \le \dbinom{n}{2}$$

其中 $X_1, \dots, X_{\binom{n}{2}}$ 是以 $p$ 为参数的 i.i.d. 伯努利随机变量，使得 $X_i$ 是第 $i$ 条边是否在图中的指示随机变量。

点 exposure 鞅是

$$Y_i = \mathbb{E}[f(G) \mid X_1, \dots, X_i],\quad 1 \le i \le n$$

其中 $X_i = G[\left\lbrace 1, \dots, i \right\rbrace]$ 是 $G$ 的一个从开始 $i$ 个顶点诱导出来的子图。

上色数（chromatic number）$\chi(G)$ 是最小的颜色数去涂色 $G$ 的顶点，使得相邻的顶点颜色不同。

任意顶点都可以指定一个新的颜色，即 $|Y_i - Y_{i-1}| \le 1$，于是吾妻不等式有

$$\Pr\left( \left\lvert \chi(G) - \mathbb{E}[\chi(G)] \right\rvert \ge \sqrt{c n} \right) \le 2 \e^{-2c}$$