计数

$\tbinom{n}{k}=\frac{n}{k}\tbinom{n-1}{k-1}$

$\sum\limits_{k=0}^n k\tbinom{n}{k}=n2^{n-1}$

$\sum\limits_{k=0}^m \tbinom{n+k}{n}=\tbinom{n+m+1}{n+1}$

卡特兰数 $C_n=\tbinom{2n}{n}-\tbinom{2n}{n-1}$ 若干实际意义，不必多说

容斥原理：不必多说

若序列长度 $>st$ ，则要么存在长为 $s+1$ 的上升子序列，要么存在长为 $t+1$ 的下降子序列

生成函数

对于数列 $\{a_n\}$ 可以定义其生成函数为 $A(x)=\sum\limits_{n=0}^{\infty}a_nx^n$ 。

性质：任意 $\frac{P(x)}{Q(x)}$ 都能写成 $\sum \frac{c_i}{(1-\alpha_ix)^{k_i}}+R(x)$ ，其中 $P(x),Q(x),R(x)$ 都是项数有限的多项式。

我们考察斐波那契数列的生成函数。因为 $F(x)=1+xF(x)+x^2F(x)$ ，所以可以解出 $F(x)=\frac{1}{1-x-x^2}$ 。

令 $1-x-x^2=(1-\alpha)(1-\beta)$ ，其中 $\alpha,\beta=(1\pm\sqrt{5})/2$ ，我们可以解出 $F(x)=\frac{1}{\sqrt{5}}(\frac{\alpha}{1-\alpha x}-\frac{\beta}{1-\beta x})$ ，于是 $f_n=\frac{1}{\sqrt{5}}(\alpha^{n+1}-\beta^{n+1})$ 。

我们考察划分数的生成函数。发现 $A(x)=\prod\limits_{k=1}^{\infty}\frac{1}{1-x^k}$ 。（OIer：我记得有个东西叫五边形数）

两个重要的生成函数： $e^x$ 是数列 $\frac{1}{0!},\frac{1}{1!},\frac{1}{2!}\dots$ 的生成函数。 $\ln (\frac{1}{1-x})$ 是 $0,1,\frac{1}{2},\frac{1}{3},\dots$ 的生成函数。

指数生成函数

$\tilde{A}(x)=\sum\limits_{n=0}^{\infty}\frac{1}{n!}a_nx^n$ 。

例：考察长度为 $n$ 的排列的 EGF，有 $S(x)=\frac{1}{1-x}$ 。考察长度为 $n$ 的轮换的 EGF，有 $C(x)=\ln (\frac{1}{1-x})$ 。

发现 $S(x)=e^{C(x)}$ ，它的组合意义是枚举排列的轮换个数。（OIer：求 $n$ 个点的无向连通图个数）

一些例子

考察卡特兰数的生成函数。有 $C(x)=xC^2(x)+1$ 。

可以解出 $C(x)=\frac{1-\sqrt{1-4x}}{2x}$ 。

广义的二项式定理： $(1+x)^{\alpha}=\sum\limits_{n=0}^{\infty}\frac{\alpha^{\underline{n}}}{n!}x^n$ 。

我们可以计算 $(1-4x)^{1/2}=\sum\limits_{n=0}^{\infty}\frac{(1/2)^{\underline{n}}}{n!}(-4x)^n=-\sum\limits_{n=0}^{\infty}\frac{1* 3*\dots*(2n-3) }{n!}(2x)^n=-2\sum\limits_{n=0}^{\infty}\frac{(2n-2)!}{(n-1)!n!}x^n$ 。所以进一步能算出 $[x^n]C(x)=\frac{(2n)!}{(n+1)!n!}=\frac{1}{n+1}\tbinom{2n}{n}$ 。

考察 $n$ 个点的有标号有根树个数。考虑其 EGF,有 $\tilde{T}(x)=xe^{\tilde{T}(x)}$ 。

Burnside & Polya

我们先回顾一下群作用 $G×X\to X$ 的一些记号：

$orbit(x)=Gx=\{g\circ x|g\in G\}$ 。

$Stab_G(x)=\{g|g\circ x=x\}$

$x^{g}=\{x|g\circ x=x\}$

$X/G=\{Gx|x\in X\}$ （也就是轨道个数）

burnside 引理： $|X/G|=\frac{1}{|G|}\sum\limits_{g\in G}|x^g|$ 。

怎么证明呢？有 $|X/G|=\sum\limits_{x\in X}\frac{1}{|Gx|}=\sum\limits_{x\in X}\frac{Stab(x)}{|G|}=\frac{1}{|G|}\sum\limits_{x,g}[g\circ x=x]=\frac{1}{|G|}\sum\limits_{g\in G}|x^g|$ 。

polya 计数：在 burnside 的基础上做进一步拓展。设 $F=\{f:X\to C\}$ ，如果已经有群作用 $G×X\to X$ ，然后定义 $G×F\to F$ 满足 $g×f=f\circ g$ ，其中我们把 $g$ 看做 $X\to X$ 的置换。那么 $|F/G|=\frac{1}{|G|}\sum\limits_{g}|F^g|=\frac{1}{|G|}\sum\limits_{g}|C|^{c(g)}$ ，其中 $c(g)$ 表示 $g$ 的轮换个数。

例：考虑 $n$ 个点的项链，每个点能染成 $C$ 种颜色之一，求染色方案数，其中认为旋转后相同的方案是相同的。

不难算出就是 $\frac{1}{n}\sum\limits_{g\in Z_n}C^{\gcd(g,n)}$ 。可以进一步化成 $\frac{1}{n}\sum\limits_{d|n}\varphi(\frac{n}{d})C^d$ 。

进一步的我们可以做以下拓展：我们之前用 $|C|$ 个颜色对小球染色。现在比方说我们用了 $3$ 种颜色，假设我想对所有 $i+j+k=n$ 算出第一种颜色用 $i$ 次，第二种用 $j$ 次，第三种用 $k$ 次的方案数，怎么求？

我们设 $c_i(g)$ 是 $g$ 长度为 $i$ 的轮换个数。

那么只需提取 $\frac{1}{|G|}\sum\limits_{g}Z_1^{c_1(g)}Z_2^{c_2(g)}\dots$ 的相应系数即可，其中 $Z_i=x^i+y^i+z^i$ 。

然后我们再看一些例子。求 $G$ 的共轭类个数？考虑群作用 $G×G\to G$ 满足 $g\circ x=gxg^{-1}$ ，那么共轭类个数就是这个作用的轨道个数，由 burnside，有 $\frac{1}{|G|}\sum\limits_{g}C_G(g)$ 。

概率

我们研究概率空间 $(\Omega,P)$ 。其中 $\Omega$ 是样本空间， $P$ 是 $\Omega\to \R$ 的函数满足：

$\forall w\in \Omega,P(w)\geq 0$ 以及 $\sum\limits_{w\in \Omega}P(w)=1$ 。

我们称一个事件是 $\Omega$ 的子集，即 $A\subseteq \Omega$ 。令 $P(A)=\sum\limits_{w\in A}P(w)$ 。也记作 $Pr[A]$ 。

令 $Pr[B|A]=\frac{Pr[A\cap B]}{Pr[A]}$ 表示条件概率。

有贝叶斯定理： $Pr[B|A]=\frac{Pr[B]}{Pr[A]}Pr[A|B]$ 。

定义事件 $A,B$ 独立： $Pr[A\cap B]=Pr[A]Pr[B]$ 。

定义随机变量： $X:\Omega\to S$ ，设 $P(x)=Pr[X=x]=\sum\limits_{X(w)=x}P(w)$ ，这被称为概率函数。

一些常见分布

定义分布：对随机变量 $X$ ，设 $P_X(x)=Pr[X=x]$ 。

联合分布：对随机变量 $X,Y$ ，设 $P_{XY}(x,y)=Pr[X=x\land Y=y]$ 。

条件分布 ： $P_{Y|X}(y|x)=Pr[Y=y|X=x]$ 。

显然 $P_{Y|X}(y|x)=\frac{P_{XY}(x,y)}{P_X(x)}$ 。

现在我们定义一些常见的分布。

伯努利分布 $Bern(p)$ 形如 $\begin{cases}1-p&x=0\\p&x=1\end{cases}$

二项式分布 $Binom(n,p)$ 形如 $\tbinom{n}{x}p^x(1-p)^{n-x}$

几何分布 $Geom(p)$ 形如 $p(1-p)^{x-1}$

负二项分布 $NB(r,p)$ 形如 $\tbinom{x+r-1}{x}p^r(1-p)^x$

（组合意义是以 $p$ 概率抽 $1$ ，若干次后抽出 $r$ 个 $1$ ）

泊松分布 $Poisson(\lambda)$ 形如 $\frac{e^{-\lambda}\lambda^x}{x!}$ 。

（可以看做 $n\to\infty$ 时的 $Binom(n,\frac{\lambda}{n})$ ）

期望，方差

我们定义 $E[X]=\sum\limits_{x}P_X(x)x=\sum\limits_{w}P(w)X(w)$

例题：设 $X\sim Geom(p)$ ，求 $E[X]$ 。根据实际意义，我们有 $E[X]=E[X-1|X>1]$ 。而 $E[X-1|X>1]=\sum\limits_{x=2}^{\infty}(x-1)Pr[X=x|X>1]=\sum\limits_{x=2}^{\infty}(x-1)\frac{Pr[X=x]}{1-p}=\sum\limits_{x=0}^{\infty}\frac{(x-1)P_x(x)}{1-p}=\frac{E[X]-1}{1-p}$ ，于是 $E[X]=\frac{1}{p}$ 。

定义 $Var[X]=E[X^2]-E[X]^2=E[(X-E[X])^2]$ 。定义 $Cov[X,Y]=E[XY]-E[X]E[Y]=E[(X-E[X])(Y-E[Y])]$ 。

对于两个独立随机变量 $X,Y$ ，我们有 $E[XY]=E[X]E[Y]$ 。

有 $Var[X+Y]=E[(X-E[X]+Y-E[Y])^2]=Var[X]+Var[Y]+2Cov[X,Y]=Var[x]+Var[y]$ 。

概率生成函数(PGF)

$G_X(z)=\sum\limits_{x}P_X(x)z^x=E[z^X]$ 。

若 $X,Y$ 是独立分布，那么 $G_{X+Y}(z)=G_X(z)G_Y(z)$

你发现 $G_X$ 有一些良好性质，比如 $G'X(1)=E[x],G''X(1)+G'_X(1)=E[X^2]$ 。

例：考察掷硬币，第一次连续两次正面朝上的概率。考虑其 PGF，有 $G(z)=p^2z^2+(1-p)zG(z)+(1-p)pz^2G(z)$ 。

我们考察 $G_X(e^z)=E[e^{zX}]$ 。其 $n$ 阶导代入 $z=0$ 可得 $E[X^n]$ 。

熵

考虑随机变量 $X$ 遵从概率分布 $P_x$ ，我们设 $H[X]=\sum\limits_{x}P_X(x)\log \frac{1}{P_x(x)}$ 。也可以看做是 $E[\log \frac{1}{P_X(X)}]$

比如说设 $X\sim Bern(\frac{1}{2})$ ，我们有 $H(X)=1\log 2$ 。

令 $|X|=\{x|P_X(x)>0\}$ ，不难证明 $0\le H(X)\le \log |X|$

联合熵 对随机变量 $X,Y$ ，设 $H[X,Y]=\sum\limits_{x,y}P_{XY}(x,y)\log \frac{1}{P_{XY}(x,y)}$

条件熵 对随机变量 $X,Y$ ， $H[Y|X]=\sum\limits_{x}H[Y|X=x]\cdot Pr[X=x]$ 。

我们推一下式子： $H[Y|X]=\sum\limits_{x}\sum\limits_{y}P_{Y|X}(y|x)\log \frac{1}{P_{Y|X}(y|x)}P_x(X)=\sum\limits_{x,y}P_{xy}(x,y)\log\frac{1}{P_{Y|X}(y,x)}=E[\log\frac{1}{P_{Y|X}(Y|X)}]$

我们有 $H[X,Y]=H[X]+H[Y|X]$ ，因为 $E[\log\frac{1}{P_{XY}(X,Y)}]=E[\log\frac{1}{P_X(X)}]+E[\log\frac{1}{P_{Y|X}(Y|X)}]$

互信息

我们有 $H[X|Y]\le H[X]$ 。

证明：

因为 $H[X]-H[X|Y]=\sum\limits_{x}P_x(x)\log\frac{1}{P_x(x)}-\sum\limits_{x,y}P_{X|Y}(x|y)\log\frac{1}{P_{X|Y}(x|y)}=\sum\limits_{x,y}P_{XY}(x,y)\log \frac{P_{XY}(x|y)}{P_X(x)}=\sum\limits_{x,y}P_{XY}(x,y)\log\frac{P_{XY}(x,y)}{P_X(x)P_Y(y)}$

到这里，可以看成有两个长为 $|X|\cdot |Y|$ 的序列 $a,b$ ，上述和式为 $\sum\limits_{i}a_i\log\frac{a_i}{b_i}$ ， $\sum a$ 和 $\sum b$ 都是固定的，求这个式子下界。经过系列数学推导，可以得到它大于等于 $(\sum a)\log\frac{\sum a}{\sum b}$ ，回到之前问题，即有 $H[X]\geq H[X|Y]$ 了。

定义互信息为 $I(X;Y)=H[X]-H[X|Y]=H[Y]-H[Y|X]$ 。

data-processing 不等式： $I(X;Y)\geq I(X;Z)$ ，其中 $P_Y=P_XP_{Y|X},P_Z=P_YP_{Z|Y}$

KL散度

$D(P||Q)=\sum\limits_{x}P(x)\log \frac{P(x)}{Q(x)}$ 可以看做 $P$ 偏离 $Q$ 的程度

(注意 $P,Q$ 是两个概率分布)

我们有 $D(P||Q)\geq 0$ ，因为设 $D(P||Q)=E_{x\sim Q}[\frac{P(x)}{Q(x)}\log \frac{P(x)}{Q(x)}]=E_{x\sim Q}[f(\frac{P(x)}{Q(x)})]\geq f(E_{x\sim Q}[\frac{P(x)}{Q(x)}])=f(1)=0$ ，其中 $f(x)=x\log x$

我们有 $D(P||Unif(\Omega))=\log |\Omega|-H(P)$ 这很好证明

现在考虑 $P_{XY},Q_{XY}$ 。

我们证明 $D(P_{XY}||Q_{XY})=D(P_X||Q_X)+D(P_{Y|X}||Q_{Y|X}|P_X)$

因为 $E_{X,Y\sim P_{XY}}[\log \frac{P_{XY}(X,Y)}{Q_{XY}(X,Y)}]=E_{X,Y\sim P_{XY}}[\log \frac{P_X(X)}{Q_X(X)}+\log \frac{P_{Y|X}(Y|X)}{Q_{Y|X}(Y|X)}]$

同理我们有 $D(P_{X_1X_2\dots X_n}||Q_{X_1X_2\dots X_n})=\sum\limits_{i=1}^n D(P_{X_i|X_1\dots X_{i-1}}||Q_{X_i|X_1\dots X_{i-1}}|P_{X_1X_2\dots X_{i-1}})$

集中不等式

马尔科夫不等式 (Markov Bound)

对于在 $[0,+\infty)$ 上的随机变量 $X$

$P[X\geq \alpha E[X]]\le \frac{1}{\alpha}$

证明：首先有 $\int_0^{\infty}P_1[X\geq x]\,dx=E[X]$ 。

这是因为 $\int_0^{\infty}P_1[X\geq x]\,dx=\int_0^{\infty}\sum\limits_{w}P(w)[X(w)\geq x]\,dx=\sum\limits_{w}P(w)\int_0^{\infty}[X(w)\geq x]\,dx=\sum\limits_{w}P(w)X(w)=E[X]$ 。

切比雪夫不等式 (Chebyshev’s Bound/Inequality)

对随机变量 $X$ ，设 $Var(X)=\Delta^2$ 。

$Pr[|X-E[X]|\geq \alpha\Delta]\le \frac{1}{\alpha^2}$ 。

我们可以由马尔科夫不等式推出来： $Pr[|X-E[X]|\geq \alpha\Delta]=Pr[(X-E[X])^2\geq \alpha^2\Delta^2]$ 。而 $\Delta^2=E[(X-E[X])^2]$ ，那就有 $Pr[(X-E[X])^2\geq \alpha^2\Delta^2]\le \frac{1}{\alpha^2}$

切尔诺夫不等式 (Chernoff Bound)

对随机变量 $X$ ， $Pr(X\geq a)=Pr(e^{tX}\geq e^{ta})\le \frac{E[e^{tX}]}{e^{t\alpha}}$ ，其中 $t$ 是任意一个 $>0$ 的实数。

例子：设 $X_1,\dots,X_n\sim Bern(p)$ 且互相独立，估计 $Pr[\sum\limits_{i}X_i\geq qn]$ ，其中 $q>p$ 。

利用 chernoff bound ，它小于等于 $\frac{E[e^{t\sum X_i}]}{e^{tqn}}=(\frac{pe^t+(1-p)}{e^{tq}})^n$

现在我们希望寻找 $\frac{pe^t+(1-p)}{e^{tq}}$ 的最小值，把它对 $t$ 求导并找零点，发现零点满足 $e^t=\frac{q(1-p)}{p(1-q)}$ ，代入上面式子即可得到一个很好的界： $(\frac{1-p}{1-q})^{1-q}(\frac{p}{q})^q$ 的 $n$ 次方。

但同时我们发现 $(\frac{1-p}{1-q})^{1-q}(\frac{p}{q})^q$ 有些眼熟，它等于 $\exp(q\log \frac{p}{q}+(1-q)\log \frac{1-p}{1-q})=exp(-d(q||p))$ 。于是最后的结果是 $exp(-d(q||p)n)$ 。

更进一步，之前的作业我们证明过 $d(q||p)\le 2(p-q)^2$ ，于是它小于等于 $exp(-2(p-q)^2n)$ 。

斯特林公式

对 $n!$ 的估计。我们有 $n!$ 约为 $\sqrt{2\pi n}(\frac{n}{e})^n$ 。还有另一个更严谨的式子： $\ln n!=n\ln n-n+\frac{\ln n}{2}+\frac{1}{12n}+O(\frac{1}{n^3})$

Sanov Bound

对于 $X_1,X_2,\dots,X_n\sim Bern(p)$ ，有 $Pr[\sum\limits X_i=qn]\in [\frac{1}{n+1}exp(-nd(q||p)),exp(-nd(q||p))]$ 。

$\frac{1}{(n+1)^{L+1}}exp(nH(Q))\le \binom{n}{s_1,s_2,\dots s_L}\le exp(nH(Q))$ ，其中 $Q$ 满足 $Pr[Q=i]=\frac{s_i}{n}$ 。

离散傅里叶变换

Discrete Fourier Transform，简称 DFT。

它是针对 $G\to \mathbb{C}$ 的函数（向量？）做变换的技术，其中 $G$ 是某个有限阿贝尔群。我们知道它是和 $\Z_{n_1}×\Z_{n_2}×\dots \Z_{n_k}$ 同构的。

对于 $a\in \Z_{n_1}×\Z_{n_2}×\dots \Z_{n_k}$ ，设 $X_a:G\to \mathbb{C}$ 满足 $X_a(x)=w_{n_1}^{a_1x_1}w_{n_2}^{a_2x_2}\dots w_{n_k}^{a_kx_k}$ ，其中 $w_d=e^{\frac{2\pi i}{d}}$ 。

首先发现 $X_a$ 有良好性质：我们设 $X_a\cdot X_b$ 表示点值诸位相乘，那么 $X_aX_b=X_{a+b}$ ， $X_a/X_b=X_{a-b}$ 。其次，你发现单个 $X_a$ 其实构成了同态。

注意到 $\sum\limits_{x}X_a(x)=\sum\limits_{(x_1,x_2,\dots,x_k)\in G}\prod\limits_{j}w_{n_j}^{a_jx_j}=\prod\limits_{j}\sum\limits_{x_j\in \Z_{n_j}}w_{n_j}^{a_jx_j}=\prod\limits_{j}n_j\cdot [a_j= 0]=|G|\cdot [a=0]$ 。

于是 $X_a$ 的全体可以看成一组正交基，因为 $\lang X_a,X_b\rang=\sum\limits_{x}X_{a-b}(x)=|G|\cdot [a=b]$

设某个 $G\to \mathbb{C}$ 的函数能写成 $f=\sum\limits_{b\in G}\hat{f}(b)X_b$ ，我们怎么求出 $\hat{f}(b)$ 呢？它都是正交基了，只需考察 $\lang f,X_b\rang=\sum\limits_{a}\lang \hat{f}(a)X_a,X_b\rang=\lang \hat{f}(b)X_b,X_b\rang=|G|\cdot \hat{f}(b)$ ，这样就求出 $\hat{f}(b)$ 了！我们称 $\hat{f}$ 是傅里叶系数。由 $\hat{f}$ 反过来求 $f$ 就很容易了。其实还能证明： $f(x)=\lang \hat{f},X_{-x}\rang$

现在考察两个函数 $f,g$ 做卷积，也就是 $(f*g)(x)=\sum\limits_{y}f(y)g(x-y)$

考察 $\widehat{f*g}(a)$ ，我们有 $\widehat{f*g}(a)=\frac{1}{n}\lang f*g,X_a\rang=\frac{1}{n}\sum\limits_{y+z=x}f(y)g(z)\overline{X_a}(x)=\frac{1}{n}\sum\limits_{y}\sum\limits_{z}f(y)g(z)\overline{X_a}(y)\overline{X_a}(z)=\frac{1}{n}(\sum\limits_{y}f(y)\overline{X_a}(y))(\sum\limits_{z}g(z)\overline{X_a}(z))=n\cdot \hat{f}(a)\cdot \hat{g}(a)$

于是函数做卷积可以转化成：傅里叶变换后将点值相乘

我们来举一个傅里叶变换产生效果的例子：

设 $P_X,P_Y$ 都是 $G\to \R$ 的分布且二者独立，设 $X,Y\sim P_X,P_Y$ ，求 $X+Y$ 遵从什么分布。那其实就是对两个密度函数做卷积： $P_{X+Y}=P_X*P_Y$

同理，设独立同分布的变量 $X_1,X_2,\dots,X_t\sim P_X$ ，那么 $\widehat{P_{X_1+X_2+\dots+X_t}}=n^{t-1}(\hat{P}_X)^t$

通信

我们先定义一些类似 $H[X]$ 的东西。

$H(X)=E[\log \frac{1}{P(X)}],H_{min}(X)=\log \frac{1}{\max\limits_{x} P(x)},H_{max}(X)=\log |X|,H_2(X)=\log (\frac{1}{\sum\limits_{x}P^2(x)})$

无损压缩 (lossless compression) 考虑对于一个随机变量 $X\sim P$ 做以下过程：通过编码过程 $E$ (Compressor) 得到一个 01 字符串，再通过解码过程 $D$ （Decompressor）得到 $\hat{X}$ 。

假如我们希望 $D,E$ 这两个函数满足 $D(E(x))=x$ ，并且 $\mathbb{E}[len(E(X))]$ 最小。那显然，设 $X$ 的 support 是 $\{x_1,x_2,\dots\}$
且满足 $P(x_i)\geq P(x_{i+1})$ ，那么 $E(x_1)=\varnothing,E(x_2)=0,E(x_3)=1,E(x_4)=00,\dots$ 就是最优的。为了方便，我们在每个串前面接上一个 ‘1’ ，这样 $E(x_i)$ 就成了二进制数且 $E(x_i)=i$ 。

记 $L(X)=len(E(X))$ 。可以证明 $\mathbb{E}[L(X)]\le H[X]$ ，这是因为 $P(x_i)\le \frac{1}{i}$ ，所以 $\mathbb{E}[L(X)]=\sum\limits_{i}P(x_i)[\log_2 i]\le \sum\limits_{i}P(x_i)\log_2 i\le \sum\limits_{i}P(X_i)\log \frac{1}{P(X_i)}=H[X]$

其实有 $H[X]-H[L]\le \mathbb{E}[L(X)]\le H[X]$ ，其中 $L$ 是随机变量满足 $L=L(X)$

接下来我们先介绍 唯一可译码 (Uniquely Decodable Code) ，就是说任何编码消息序列，只有一种方式能将其分割成原始的码字序列。

比如说摩尔斯编码就不是唯一可译码。

现在介绍前缀码 (prefix code) 的概念： $f:A\to \{0,1\}^{*}$ 满足对任意 $x\neq y$ ， $f(x)$ 不是 $f(y)$ 的前缀。

前缀码的好处：我们其实通过 $f$ 拓展到 $f^{*}:A^{*}\to \{0,1\}^{*}$ ，让 $f(a_1a_2\dots a_n)=f(a_1)f(a_2)\dots f(a_n)$ 即可。

如果有一个给定的函数 $L:A\to \N$ ，那么存在一个前缀码 $f$ 使得 $|f(x_i)|=L(x_i)$ 的充要条件是 $\sum\limits_{i}2^{-L(x_i)}\le 1$ 。

最好的前缀码：哈夫曼编码（huffman code）。无需多言。

在哈夫曼编码下，我们有 $H[X]\le \mathbb{E}[L(X)]\le H[X]+1$ 。

我们来证一下 $\mathbb{E}[L(X)]\le H[X]+1$ ，这是因为我们能找另一个前缀码满足 $L(x)=\left\lceil{\log_2 \frac{1}{P(x)}}\right\rceil$ ，我们容易它满足 $\sum 2^{-L(x)}\le 1$ 且 $\mathbb{E}[L(X)]\le H[X]+1$ ，于是哈夫曼编码也满足 $\mathbb{E}[L(X)]\le H[X]+1$ 。

哈夫曼编码 $\subseteq$ 前缀码 $\subseteq$ 唯一可译码 $\subseteq$ 无损压缩

接下来介绍 几乎无损压缩 (Almost loseless compression) 。

就是说压缩的函数不一定是单射，但是 $Pr[D(E(X))=X]\geq 1-small$ ，也就是说解码得到的结果大概率正确。

我们有结论；任意 $\delta>0$ ，存在编码方案使得 $L\le n(\delta+H(x))$ ，且 $\lim\limits_{n\to\infty}Pr[D(E(X))\neq X]=0$ 。

另一个结论：若 $L<n(H(X)-\delta)$ ，那么错误概率趋于 $1$ 。

信道编码

(Channel Encoding)

考虑以下过程：小 A 想将字符串 $W\in \{0,1\}^n$ 传给小 B 。会先做 encode 得到 $X$ ，传输过程中会经过一个 channel 得到 $Y$ ，可以抽象成 $P_{Y|X}$ 。（也就是说传输过程有噪声）小 B 再将 $Y$ 解码得到 $\hat{W}$ 。

（channel = kernel = conditional probability）

例：考虑 Binary Erase Channel ，有 $P_{Y|X}(b|b)=1-\epsilon,P_{Y|X}(\bot|b)=\epsilon$ 。

此时设 $W=w_1w_2\dots$ ，如果编码成 $w_1w_1w_1w_2w_2w_2\dots$ 则此时 $Pr[\widehat{w_i}=w_i]\geq 1-\epsilon^3$

接下来对于 Channel 我们定义 Capcieity ： $\max\limits_{P_X,(X,Y)\sim P_XP_{Y|X}}I(X,Y)$

现在考虑将 $W\in \{0,1\}^n$ 编码成 $X\in \{0,1\}^L$ ，通过 $(P_{Y|X})^L$ 得到 $Y\in \{0,1\}^L$ ，解码得到 $\widehat{W}$ 的过程。

可以证明 $I(X;Y)\le L\cdot C$ 且 $I(W;\widehat{W})\le I(X;Y)$

设 $\epsilon=\max\limits_{w}Pr[\widehat{W}\neq W|W=w]$ ，有 $n\le \frac{L\cdot C+h(\epsilon)}{1-\epsilon}$

另一个话题

考虑 $[L,d,p]-Code$ ，即选择 $Code\subseteq Z_p^L$ ，使得 $\forall c,c'\in Code$ ， $c\neq c'\Rightarrow Hamming(c,c')\geq d$

。。。？ohno，后面的内容我掉线了

马尔科夫链

考虑系列随机变量 $X_0,X_1,X_2,X_3$ ，其中 $X_i$ 只和 $X_{i-1}$ 相关

也就是说它们的联合分布形如 $P_{X_0}P_{X_1|X_0}P_{X_2|X_1}\dots$ ，这被称为马尔科夫链

时齐(time-homogeneous)：我们很关心 $P=P_{X_1|X_0}=P_{X_2|X_1}=\dots$ 的情况，后面我们就只讨论这种情况了（这暗含着 $X_0,X_1,X_2\dots$ 对应的空间相同，我们记为 $\Omega$ ， $P$ 其实就是 $\Omega×\Omega\to [0,1]$ 的函数）

所以 $P$ 其实也可以看成一个矩阵，我们称为 stochastic matrix。这个矩阵每个元素非负，且每行的 sum 等于 $1$ 。

假如 $X_t\sim \mu$ ，那么 $X_{t+1}\sim \mu P$ 。

上述过程可以自然的看做在一个图上做随机游走。（Random walk on cycle）

关于 $P$ 可以定义 稳态分布 （stationary distribution）。即满足 $\pi P=\pi$ 的分布

定义 不可约 (irreducible)：一个马尔科夫链被认为不可约，当且仅当它对应的图是强联通的。更严谨的，定义 $xRy$ 当且仅当 $\exists{t}$ 使得 $P^t(x,y)>0$ ，那么 $\forall x,y\in \Omega\quad xRy$

可以证明有限且不可约的马尔科夫链存在稳态分布。这个构造是 $\pi(x)=\frac{1}{E[\tau_x^{+}]}$ 。

现在对马尔科夫链定义 Hiting time $\tau_x=\min\{t\geq 0,X_t=x\}$ ，当然如果不存在 $X_t=x$ 则记为 $+\infty$ 。定义 Return Time $\tau_x^{+}$ 表示 $\min\{t>0,X_t=x\}$ 。

定理：对于有限且不可约的马尔科夫链， $\forall x,y\in \Omega$ 都有 $E_x[\tau_y]<\infty$ 且 $E_x[\tau_x^{+}]<\infty$ ，感性理解就是从一个点出发第一次游走到某个点的期望时间有限，游走回起点的期望时间有限。

注意这里的记号： $Pr_x$ 表示从 $x$ 出发做游走时 $X_0X_1X_2\dots$ 的分布，也就是说 $Pr[X_0=y]=\delta_{x,y}$ 。同理也就有 $E_x$ 。

定理：有限且不可约的马尔科夫链，不仅有稳态分布，而且这个稳态分布是唯一的！

证明：这等价于说明 $\pi(P-I)=0$ 的解空间维数为 $1$ ，因为 $P-I$ 是方阵，其实也就是证 $(P-I)\pi=0$ 的解空间为 $1$ 。

接下来定义和谐（Harmonic）

函数 $h$ 在 $x$ 上是和谐的，当且仅当 $h(x)=\sum\limits_{y}P(x,y)h(y)$ ，也就是 $h(x)=(Ph)(x)$ ，也就是 $E_x[h(X_1)]=h(x)$ 。定义 $h$ 是和谐的，当且仅当它在每个点都和谐，也就是 $h=Ph$ 。

定理：和谐函数一定是常数函数。这样我们就证明了 $(P-I)\pi=0$ 的解空间确为 $1$ 。

接下来定义 非周期性 (aperiodic) ，我们首先定义 $x$ 上的周期： $\gcd(\{t|P^t(x,x)>0\})$ 。然后说这个马尔科夫链是非周期的，当且仅当每个点的周期都是 $1$ 。

定义收敛 (convergence)： $\lim\limits_{t\to+\infty}\mu P^t=\pi$ ，其中 $\pi$ 是那个稳态分布。

定理：有限+不可约+非周期性 $\Rightarrow$ 收敛

总结一下：

有限 $\Rightarrow$ 存在稳态分布

有限+不可约 $\Rightarrow$ 存在唯一稳态分布

有限+不可约+非周期性 $\Rightarrow$ 收敛

定义混合时间

$t_{mix}(\epsilon)=\min\{t:d(t)\le \epsilon\}$

其中 $d(t)=\sup\limits_{\mu}\Delta_{\pi}(\mu P^t,\pi)$ 。

图论

考虑无向图的拉普拉斯矩阵 $L=D-A$ ，其中 $A$ 是邻接矩阵， $D$ 是度矩阵。

矩阵树定理：设 $L_{-1}$ 是 $L$ 去掉第一行第一列得到的矩阵，则生成树个数为 $det(L_{-1})$ 。

欧拉定理：联通平面图满足 $d-e+f=2$ ，其中 $d,e,f$ 表示点数，边数，面数

定理：图上随机游走对应的马尔科夫核是 $D^{-1}A$

对于向量 $f$ ，我们有 $(Lf)(u)=\sum\limits_{(u,v)\in E}(f(u)-f(v))$

于是 $f^TLf=\sum\limits_{i}f(i)\sum\limits_{j\sim i}(f(i)-f(j))=\sum\limits_{(i,j)\in E}(f(i)-f(j))^2$ ，这说明 $L$ 是半正定的。

然后我们可以研究 $L$ 的特征值。设 $\lambda_1\le \lambda_2\le \dots$

定理：联通块数量等于 $\lambda=0$ 的特征值个数。

我们可以通过 $\lambda_2$ 来“感受”图的连通性强弱，这是一套比较复杂的理论。

然后可以再考察 $A$ 的特征值，首先对于正则图， $A$ 和 $L$ 的特征值能互相转化。然后设 $\mu_1\geq \mu_2\geq \dots\mu_n$

定理： $d_{arg}\le \mu_1\le d_{max}$

定理： $\mu_1=\mu_2\Leftrightarrow$ 图不联通 $\mu_1+\mu_n=0$ $\Leftrightarrow$ 图是二分图

概率方法

对于向量 $v_1,v_2,\dots,v_n\in \{-1,1\}^L$ ，怎么证明 $\exists a_1,a_2,\dots,a_n\in \{-1,1\}$ 使得 $|\sum a_iv_i|\geq \sqrt{nl}$ ？

只需考虑纯随机 $a_i$ ，然后考察 $E(|\sum a_iv_i|^2)$ ，这恰为 $nl$ 。

看来概率方法很有用

第二矩方法 (2nd Moment Method)

$Pr[|X-E(X)|\geq \lambda \sqrt{Var(X)}]\le \lambda^{-2}$

例子：证明 $\frac{2^{2n}}{\tbinom{2n}{n}}=O(\sqrt{n})$ 。

这是因为考虑 $X_1,X_2,\dots,X_n\sim Bern(\frac{1}{2})$ ，则 $\frac{\tbinom{2n}{n}}{2^{2n}}=Pr[\sum X_i=n]$ 。

同时因为 $Var[\sum X_i=n]=\frac{n}{2}$ ，所以 $Pr[|\sum X_i-n|\geq \alpha]\le \frac{n}{2\alpha^2}$ ，那 $Pr[|\sum X_i-n|\geq \sqrt{n}]\le \frac{1}{2}$ 。

则 $Pr[\sum X_i=n]\geq \frac{1}{2\sqrt{n}+1}Pr[|\sum X_i-n|\le \sqrt{n}]\geq \frac{1}{2(2\sqrt{n}+1)}$

另一个例子：设 $v(x)$ 是 $x$ 的不同质因子个数，证明：对于任意 $n$ ，在 $x\in \{1,2,\dots,n\}$ 中使得 $|v(x)-\ln \ln n|>\lambda \sqrt{\ln \ln n}$ 的 $x$ 个数是 $O(\lambda^{-2})$

为了证明这个事情，我们设 $X\sim Unif(\{1,2,\dots,n\})$ ，同时设 $X_p=[p|X]$ 。

那么 $v(X)=\sum\limits_{p}X_p$

同时显然地， $v(X)-10<\sum\limits_{p< n^{1/10}}\le v(X)$

有 $E[\sum\limits_{p< n^{1/10}}X_p]=\sum\limits_{p<n^{-10}}\frac{1}{p}-O(\frac{1}{n})=\ln \ln n+O(1)$ 。

$Var[\sum\limits_{p< n^{1/10}}X_p]$ 经过一些分析，亦为 $\ln \ln n+O(1)$ 。

阈值函数 (Threshold Function)

考虑随机图 $G(n,m)$ 。对于任意针对图的谓词 $P$ (且 $P$ 满足单调性)我们希望找到阈值函数 $m^{*}$ ：若函数 $m$ 满足 $m(n)>(1+\epsilon)m^{*}(n)$ ，则 $\lim\limits_{n\to +\infty}\Pr\limits_{G\sim (n,m(n))}[G\in P]=1$ ；若 $m(n)<(1-\epsilon)m^{*}(n)$ ，则 $\lim\limits_{n\to +\infty}\Pr\limits_{G\sim (n,m(n))}[G\in P]=0$ 。

比如说 $P$ 表示连通性的话，有 $m^*(n)=\frac{1}{2}n\ln n$

Lovasz Local Lemma

考虑若干事件 $A_1,A_2,\dots,A_n$

我们希望判断它们是否都不发生，即 $Pr[\lnot A_1,\dots,\lnot A_n]>0$ 。

如果能构造一个图（Dependency graph） $G=(V,E)$ ，其中一个顶点代表一个事件， $E$ 满足： $A_i$ 和 $\{A_j\}_{(i,j)\notin E}$ 独立

那么设 $p=\max \Pr[A_i],d$ 是 $G$ 的最大度数。

定理： $e\cdot p\cdot d<1\Rightarrow Pr[\lnot A_1,\dots,\lnot A_n]>0$

例：考虑在 d-regular 图上做边染色，我们想知道是否存在一个方案，使得不存在一个三元环颜色相同。

那不希望发生的事件都形如 $A_{uvw}$ 表示 $u,v,w$ 这个三元环同色

发现两个事件相关当且仅当有公共边，所以 max degree $\le 3(d-1)$

同时 $p=\frac{1}{c^2}$ ，其中 $c$ 是颜色个数。所以说只要 $\frac{e}{c^2}\cdot 3(d-1)<1$ ，也即 $c>\sqrt{3e(d-1)}$ ，就存在这么一组解了