Online Gradient Descent

回忆我们对 online learning 的假设。那么我们针对这个问题的 online gradient descent / online projected gradient descent (OPGD) 算法可以直接得到
x_{s+1} = x_s - \eta_s \nabla l_t(x_s)
我们可以用和 GD 相似的方法分析出一个相似的 bound。课程这里用分析 "连续版本" 的方法来得到这个 bound。

大致地讲，其引入如下 settings:

• 对于 s = 0, 1, \dots, T，$\mathscr{T}s = \sum{i=0}^{s-1} \eta_i. 也就是说把两轮之间看作有一段\eta_i的时间。这样以 1 的速度匀速移动过去就走了\eta_i$ 的距离.
• $y_0 = x_0$
• $\frac{\text{d} y_t}{\text{d} t} = -g_t$，其中 $g_t = \nabla l_{s_t}(x_{s_t})$，$s_t$ 是这个时间所属的轮数。

形象来讲，把一步步 gradient descent 变成了每次在两个点之间做匀速直线运动。这样分析（具体略去）可以得到 regret bound
\sum_{s=0}^{T-1} \frac{\phi(x_s) - \phi(x_{s+1})}{\eta_s} + \frac{\eta_s \Vert \nabla l_s (x_s) \Vert^2}{2}
\le diam(V) \cdot L \cdot \sqrt{T}
假设 l 是 L-Lipschitz. 用在最开始的那个猜数问题，这个界比 FTL 要糟糕很多。

Strongly Convex Function

如果 l_s 满足 \mu-strongly convex，这个性质即对于函数 f，对任意 x, y
f(y) \ge f(x) + \nabla f(x)^T (y-x) + \frac{\mu}{2} \Vert y -x \Vert^2
选择合适的 \mu_s = \frac{1}{(s+1) \mu} 那么这个 bound 可以进一步优化为
\sum_{s=0}^{T-1} l_s(x_s) - l_s(x^*) \le \frac{L^2}{2 \mu} H_T
用在猜数上和 FTL 的 bound 一样好。

Lec 8

Learning with Expert Advice

在这个问题中，我们可以将 [n] 中的每个元素当成一个 expert 并且在每一轮，player 需要选择一个 expert 来 follow。然后 adversary 展示每个专家的 loss。因此每一轮：

• The player picks some x_t \in [n] ;
• The adversary picks some l_t: [n] \rightarrow \mathbb{R} ;
• $l_t$ is revealed and the player pays the cost $l_t(x_t)$.

那么 regret 函数就是 \sum_{t=0}^{T-1} l_t(x_t) - l_t(x^*). 显然 V = [n] 并不是个凸集，因此不能直接用之前的方法。我们可以用一个随机化的方法：

• The player pciks some distribution x_t \in \Delta_{n-1} where \Delta_{n-1} ={x \in [0, 1]^n: \sum_{i=1}^n x_i = 1}. 这个记号以后会经常出现，名字叫 probability simplex.
• The adversary picks some l_t: [n] \rightarrow \mathbb{R} ;
• The player plays A_t \sim x_t ;
• $l_t$ is revealed and the player pays the cost $l_t(A_t)$.

那么对于一个固定的 expert j \in [n]，期望 regret 为
\mathbf{E}[\sum_{t=1}^T l_t(A_t) - l_t(j)] = \sum_{t=1}^T \langle l_t, x_t - e_j \rangle
那么这一问题就 reduce 了一个 \Delta_{n-1} 上个在线凸优化问题。我们可以设定初始分布为 x_1 = (\frac{1}{n}, \frac{1}{n}, \dots, \frac{1}{n}). 然后后面用 OPGD. 这样期望 regret bound 就可以得到
\frac{diam(\Delta_{n-1})}{2 \eta} + \frac{\eta T n}{2} = \Theta(\sqrt{nT})

Online Stochastic Gradient Descent

比较 learning with expert advice 问题与 multi-armed bandits 问题，主要有两处不同：

• 每个 round 结束后，multi-armed bandits 只能看到 l_t(A_t) 而不是整个 l_t 向量。
• adversary 从一个固定的分布中选择每轮的 l_t。

我们放松第二点，允许它像 learning with expert advice 一样任意选 l_t. 这称作 adversarial multi-armed bandit problem.

由于我们只知道一个位置的 l_t(A_t)，我们需要用这个信息估计一个 \hat{l_t}. 首先我们要满足无偏性，也就是说 \mathbf{E}[\hat{l_t}] = l_t. 然后将这个估计的 \hat{l_t} 放入 OGD 算法. 一个自然的选择是
\forall i \in [n],\ \hat{l_t} = \frac{1_{A_t = i}}{x_t(i)} l_t(i)
那么显然有 \mathbf{E}[\hat{l_t}] = l_t. 那么
\begin{split}
\mathbf{E}\bigg[ \sum_{r=1}^T \langle l_t, x_t - e_j \rangle \bigg]&\le \frac{1}{2\eta} + \frac{\eta}{2} \sum_{t=1}^T \mathbf{E} [\Vert \hat{l_t} \Vert^2]
\end{split}
注意
\mathbf{E} [\Vert \hat{l_t} \Vert^2] = \mathbf{E} [\mathbf{E} [\Vert \hat{l_t} \Vert^2]\ \vert\ \mathscr{F}_{t-1}] = \mathbf{E} \bigg[\sum_{i=1}^n x_t(i) (\frac{l_t(i)}{x_i(t)})^2 \bigg] \le \mathbf{E} \bigg[\frac{1}{x_t(i)}\bigg]
由于 x_t(i) 可能很趋近于 0，因此我们需要一个下界。我们修改算法，每次更新的时候给定一个下界
\tilde{x_t} = (1 - \alpha) x_t + \alpha \cdot \mathbf{u}
其中 \mathbf{u} = (\frac{1}{n}, \frac{1}{n}, \dots, \frac{1}{n}). 那么 bound 改进为
\begin{split}
\mathbf{E}\bigg[ \sum_{r=1}^T \langle l_t, x_t - e_j \rangle \bigg]&\le \frac{1}{2\eta} + \frac{\eta}{2} \sum_{t=1}^T \mathbf{E} [\Vert \hat{l_t} \Vert^2] + \alpha \cdot T \
&\le \frac{1}{2 \eta} + \frac{\eta n^2 T}{2 \alpha} + \alpha \cdot T \le 3 \cdot 4^{-1/3} \cdot (nT)^{2/3}
\end{split}
这个 bound 对 T 是 T^{\frac{2}{3}}. 最好的 bound 是 \sqrt{T} (使用 OSMD).

Online Shortest Paths

将每个路径看成一个 expert: path 的数量太多了.

由于我们的策略是考虑 expert 上的分布，我们也可以考虑 u 到 v 之间的 probability flow（概率流，有点像网络流）

那么我们只要指定一个初始概率流，根据 OSGD 调整它就可以了。每轮的 loss 是 \sum_{e \in E} p(e) \cdot w_t(e).

Lec 9

这一章讲 Mirror Descent. 由于不在考试范围内先不整理. 做作业时候看过了一遍.

Lec 10

Basics of Markov Chains

Definition 1 (Markov Chain) 一列随机变量 X_0, X_1, \dots 是 Markov Chain，如果对于任意的 t 以及任意的 a_0, a_1, \dots, a_{t+1},
\mathbf{Pr}[X_{t+1} = a_{t+1} \vert X_0 = a_0, X_1 = a_1, \dots, X_t = a_t] = \mathbf{Pr}[X_{t+1} = a_{t+1} \vert X_t = a_t]
也就是说 t+1 时的状态只取决于 t 时的状态。

记 \Omega 为状态集，即 X_t 能取到的所有可能的值。这里我们只考虑 \Omega = [n]，并且假设转移是 time-homogeneous 的，也就是任何时间的转移矩阵都是一样的。那么我们可以用一个转移矩阵（transition matrix）P = (p_{ij})_{i, j \in [n]} 来表示。

同样一个 Markov chain 还可以看作在图上随机游走。在任意时间 t \ge 0，我们用 \mu_t \in \Delta_{n-1} 表示 X_t 的分布，即
\mu_t(i) := \mathbf{Pr}[X_t = i]
我们有 \mu_{t+1}^T = \mu_{t}^T P. 那么有下面的结论

Proposition 2 \mu_{t}^T = \mu_{0}^T P^t.

Definition 3 (Stationary Distribution) 一个分布 \pi 是 P 的一个 stationary distribution 如果它是转移的不动点
\pi^T P = \pi^T
我们对以下问题感兴趣：

• 每一个 Markov Chain 都有 stationary distrubution 吗？
• 是否唯一？
• 是否收敛到这个 stationary distrubution？
• 收敛速率？

Fundamental Theorem of Markov Chains

Theorem 4 (Perron-Frobenius Theorem) 每一个非负矩阵 A 都有一个非负实特征向量 x，对应特征值 \lambda = \rho (A) = \max {|\lambda_i|}.

证明这里从略。

那么由于 Markov Chain 的转移矩阵 P 是一个 stochastic matrix，则有
P \cdot \mathbf{1} = \mathbf{1}
而 P^T 和 P 特征值相同，因此 \rho(P^T)=1. 根据上面的定理，存在对应非负实特征向量 \pi 使得
P^T \pi = \pi
因此 \frac{\pi}{\Vert \pi \Vert} 就是所要的 stationary distribution.

接下来考虑收敛性和惟一性。考虑如下 Markov Chain
P = \left[ \begin{matrix}
1-p&p \
q&1-q
\end{matrix} \right]
很简单可以验证
\pi = (\frac{q}{p+q}, \frac{p}{p+q})^T
接下来我们可以来 check 其是否收敛。
\begin{split}
\Delta_t &:= |\mu_t(1) - \pi(1)| = |1-p-q| \cdot \Delta_{t-1}
\end{split}
因此可以看出除了 p=q=0 或 p=q=1，其它情况都是收敛的。

当 p=q=0 时，这个图退化成两个点，不连通。因此我们可以引出第一个限制：

Definition 5 (Irreducibility) A finite Markov Chain is irreducible if its transition graph is strongly connected.

如果 P 的转移图不强连通，我们称 P reducible.

当 p=q=1 时，可以看出图是一个二元环，此时其会在这两个点之间左右横跳。因此我们引入第二个限制：

Definition 6 (Aperiodicity) A Markov Chain is aperiodic if for any state v，it holds that
\gcd{|c|\ \vert\ c \in C_v} = 1
也即每个点上的环的长度的最大公约数为 1，这样才能避免 "周期性"。

结合这两个条件就有

Theorem 7 (Fundamental theorem of Markov chains) If a finite Markov chain P \in \mathbb{R}^{n \times n} is irreducible and aperiodic, then it has a unique stationary distribution \pi \in \mathbb{R}^n. Moreover, for any distribution \mu \in \mathbb{R}^n,
\lim_{t \rightarrow \infty} \mu^T P^t = \pi^T

Coupling

Definition 11 (Total Variation Distance) The total variation distance between two distribution \mu and \nu on a countable state space \Omega is given by
D_{TV}(\mu, \nu) = \frac{1}{2} \sum_{x \in \Omega}|\mu(x) - \nu(x)|
Lemma 12
D_{TV}(\mu, \nu) = \max_{A \subseteq \Omega} |\mu(A) - \nu(A)|
这里 \mu(A) := \sum_{x \in A} \mu(x).

两个分布的 coupling 只是他们的一个联合分布。

Definition 13 (Coupling) 令 \mu 和 \nu 为相同空间 \Omega 上的两个分布。令 \omega 是 \Omega \times \Omega 上的一个分布。如果 (X, Y) \sim \omega 能推出 X \sim \mu 以及 Y \sim \nu，那么 \omega 称作 \mu 和 \nu 的一个 coupling。

Lemma 14 (Coupling Lemma)
\mathbf{Pr}_{(X, Y) \sim \omega} [X \neq Y] \ge D_{TV} (\mu, \nu)
And there exists a coupling $\omega^$ such that
\mathbf{Pr}_{(X, Y) \sim \omega^_} [X \neq Y] = D_{TV} (\mu, \nu)
Proof: 略

考虑我们的 coupling lemma，我们只要能构造一个 coupling \omega_t 使得
\mathbf{Pr}_{(X_t, Y_t) \sim \omega_t} [X_t \neq Y_t] \le \varepsilon
那么就有 $\tau{mix}(\varepsilon)\le t. 在实践上，我们可以假设X_t和Y_t来自任意的初始分布（也就是任给两个初始分布\mu_0 = X_0，\nu_0 = Y_0。那么当然对\pi$ 也是成立的。）.

Example 1 (Random walk on hypercube) 每次选一个位置 i \in [n]，有一半的概率将这个位翻转。分析这个过程的 mixing time.

先要验证这个 graph 是 irreducible 且 aperiodic 的。

我们先把问题等价成每次选一个位置 i ，然后选一个 b \in {0, 1}，将这个位设成 b. 第一个 coupling 就是让两个人行为完全一样，这样假设每个位都是不同的，但是假设一个位相同了，它们后面就永远相同了。这是一个 coupon collector，因此 mixing time 为
\tau_{mix}(\varepsilon) \le n \log \frac{n}{\varepsilon}
观察到其实我们一次能改变两位. 所以我们可以优化我们的 coupling 策略如下：

• 如果当前我们操作的位相同，那么表现一样；
• 如果当前操作的位不同，选择两个不同的位将它们改到相同；
• 剩一个，只要表现相同即可。

这能减少一半的时间：
\tau_{mix} \le \frac{1}{2} n \log n + O(n)
Example 2 (Shuffling Cards) 有一叠 n 张卡片，考虑如下洗牌规则：随机抽一张将它放到顶上。问 mixing time？

coupling：两叠卡片每次选相同的卡（花色和点数都一样），这样洗好的时间其实也是 n 张牌的 coupon collector. 因此
\tau_{mix} (\varepsilon) \le n \log \frac{n}{\varepsilon}

Lec 12

Reversible Chains

一个 Markov chain 是 (time) reversible 的如果存在一个分布 \pi 满足
\forall i, j \in [n],\ \pi(i) P(i, j) = \pi(j) P(j, i)
这个条件也叫做 细致平衡条件（Detailed Balance Condition）. 直观理解：transition graph 是 "无向图".

Proposition 1 如果 P 对分布 \pi reversible，那么 \pi 是 P 的一个 stationary distribution.

Proof:
\pi^T P(j) = \sum_{i\in [n]} \pi(i) P(i, j) = \sum_{i\in [n]} \pi(j) P(j, i) = \pi(j)
reversible chain 这一名字来源于如果 X_0, X_1, \dots, X_t 是 reversible 的，那么分布 (X_0, X_1, \dots, X_t) 和分布 (X_t, X_{t-1}, \dots, X_1, X_0) 是完全相同的分布。

由于 reversible chain 的矩阵是 symmetric 的（in some sense），这带来了很多好的性质。

Metropolis Algorithm

给定一个分布 \pi，怎样构造一个 Markov chain 收敛到 \pi？很容易我们可以令 P = \mathbf{1} \pi^T. 但如果我们只允许 P 的一个给定的 entries 集合非 0 呢？这一问题等价于在给定的图 G 上赋予转移概率，使得 \pi 是它的 stationary distribution.

令 \Delta 为图中除了自环以外的最大度数。 对于每个 i \in [n]，令邻居集合（不包含自己） {j_1, j_2, \dots, j_d}

• "uniformly" 随机选择一个 k \in [\Delta + 1].
• 如果 1 \le k \le d，那么有 \min{\frac{\pi(j_k)}{\pi(i)}, 1} 的概率移动到 j_k；
• 否则如果 d+1 \le k \le \Delta+1，do nothing.

最后产生的 transition matrix 就是
P(i, j) = \begin{cases}
0& i \not\sim j \
\frac{1}{\Delta+1} \min{\frac{\pi(j)}{\pi(i)}, 1}&i \neq j, i \sim j \
1 - \sum_{k \neq i} p_{ik}&i = j
\end{cases}
这样构造出来的 P 是 reversible 的：
\pi(i) P(i, j) = \pi(i) \frac{1}{\Delta+1} \min{\frac{\pi(j)}{\pi(i)}, 1} = \frac{1}{\Delta+1} \min{\pi(i), \pi(j)} = P(j, i) \pi(j)

Sample Proper Coloring

考虑对于 q \ge \Delta，对 G = (V, E) 进行 q 染色的方案数计数是 #P-hard 的。我们考虑近似算法。有如下结论：an approximate counting algorithm is equivalent to an uniform sampler (in many cases). 这里只展示一个方向：

设 \mathcal{C} 为所有染色的集合，给定一个 proper coloring \sigma，并且我们有一个可以 uniformly 从 \mathcal{C} 中生成一个 proper coloring 的 oracle. 记 Z = |\mathcal{C}|. 那么
\begin{split}
\frac{1}{Z} &= \mathbf{P}r_{x \sim \mathcal{C}}[x = \sigma] \
&= \mathbf{P}r_{x \sim \mathcal{C}}[x(1) = \sigma(1) \land x(2) = \sigma(2) \land \dots] \
&= \prod_{i=1}^n \mathbf{Pr} \bigg[ x(i) = \sigma(i)\ \bigg\vert\ \bigcap_{j
计算这个东西只需要多项式个数的 samples.

接下来我们来使用 MCMC 制作这个 sampler. 假设我们已经有了一个 proper coloring，我们做如下转移：

• Pick v \in V and c \in [q] uniformly at random.
• Recolor v with c if possible.

这个图是 aperiodic 的因为有自环。对于 q \ge \Delta+2，这个图是 irreducible 的。

mixing time: 略

Spectrum of Reversible Markov Chain

Theorem 2 (Spectral Decomposition Theorem) 如果 P \in \mathbb{R}^{n \times n} 是一个 symmetric matrix，那么它有着 n 个实根以及与之相对应的 n 个两两正交的特征向量满足
P = \sum_{i=1}^n \lambda_i v_i v_i^T
如果我们令 V = [v_1, v_2, \dots, v_n] 以及 \Lambda = diag(\lambda_1, \lambda_2, \dots, \lambda_n). 那么上面式子可以写成这个形式
P = V \Lambda V^T
下面我们来推导 reversible markov chain 的谱分解定理。令 \Pi = diag(\pi). 定义 Q = \Pi^{1/2} P \Pi^{-1/2}. 那么 Q 是 symmetric 的
Q(i, j) = \pi(i)^{1/2} P(i, j) \pi(j)^{-1/2} = \pi(j)^{1/2} P(j, i) \pi(i)^{-1/2} = Q(j, i)
因此我们可以对 Q 进行谱分解
Q = \sum_{i=1}^n \lambda_i u_i u_i^T
如果我们定义 v_i := \Pi^{-1/2} u_i, 那么
P = \sum_{i=1}^n \lambda_i \Pi^{-1/2} u_iu_i^T \Pi^{1/2} = \lambda_i v_i v_i^T \Pi
我们声称 v_1, \dots, v_n 是 P 相对于 \lambda_1, \dots, \lambda_n 的特征向量. 这是因为（正交性）
\begin{split}
P v_j &= \sum_{i=1}^n \lambda_i \Pi^{-1/2} u_iu_i^T \Pi^{1/2} \Pi^{-1/2} u_i \
&= \lambda_i v_j
\end{split}
如果我们定义内积 \langle x, y \rangle_\Pi := x^T \Pi y, 那么在这个内积下 v_1, \dots, v_n 是正交的。

Lec 13

Variational Characterization of Eigenvalues

在本章，我们假设 P 是一个 reversible chain w.r.t. \pi 并且有特征值 \lambda_1, \dots, \lambda_n 和特征向量 v_1, \dots, v_n . 因此有分解 P = \lambda_i v_i v_i^T \Pi. 假设 \lambda_1 \ge \lambda_2 \ge \dots \ge \lambda_n. 那么下列 proposition 成立

Proposition 1 1 = \lambda_1 \ge \lambda_2 \ge \dots \ge \lambda_n \ge -1

Proof: 由于 P 是一个 stochastic matrix，|\lambda_i| \le 1. 并且 1 是一个特征值，对应的特征向量为 \mathbf{1}.

定义 Rayleigh quotient
R_P(\mathbf{x}) = \frac{\langle \mathbf{x}, P\mathbf{x} \rangle_\Pi}{\langle \mathbf{x}, \mathbf{x} \rangle_\Pi}
我们可以将 \lambda_1 写成
\lambda_1 = \max_{\mathbf{x} \neq 0} R_P(\mathbf{x})
这可以通过 P 的 spectral decomposition 来验证. 假设 \mathbf{x} = \sum_{i=1}^n a_i v_i.
R_P(\mathbf{x}) = \sum_{i=1}^n\frac{a_i^2}{\sum_{j=1}^n a_j^2} \lambda_i
这可以看成所有特征值的加权和。因此最大的情况当然是全部放在最大的特征值上。一般地，
\lambda_k = \max_{\mathbf{x} \neq 0, \mathbf{x} \perp span(v_1, \dots, v_{k-1}} R_P(\mathbf{x})
这也等价于
\lambda_k = \max_{\text{k-dim subspace } V \subseteq \mathbb{R}^n} \min_{\mathbf{x} \in V \setminus {0}} R_P(\mathbf{x})

FTMC for Reversible Chains

由谱分解
P^t = \sum_{i=1}^n \lambda_i^t v_i v_i^T \Pi = \mathbf{1} \pi^T + \sum_{i=2}^n \lambda_i^t v_i v_i^T \Pi
由于 \mu^T \mathbf{1} \pi^T = \pi^T. 因此
\lim_{t \rightarrow \infty} \mu^T P^t = \pi^T + \lim_{t \rightarrow \infty} \mu^T \bigg( \sum_{i=2}^n \lambda_i^t v_i v_i^T \Pi \bigg)
因此只要这部分成立
\lim_{t \rightarrow \infty} \mu^T \bigg( \sum_{i=2}^n \lambda_i^t v_i v_i^T \Pi \bigg) = 0
只有两种情况会使得这个不对：\lambda_2 = 1 或者 \lambda_n = -1. 我们下面将展示这两种情况分别对应reducibility 和 periodicity。回忆 reversible chain 的 irreducible 意味着它 connected，aperiodical 意味着有奇环（not bipartite）

Proposition 3 \lambda_2 = 1 当且仅当这个图不连通.

Proof:
\begin{split}
\lambda_2 &= \max_{\mathbf{x} \neq 0,\ \mathbf{x} \perp \mathbf{1}} R_P(\mathbf{x}) \
&= \max_{\mathbf{x} \neq 0,\ \mathbf{x} 1 - \perp \mathbf{1}} 1 - \frac{\sum_{(i, j) \in E} \pi(i) P(i, j) (x(i) - x(j))^2}{ \sum_{i \in V} \pi(i) x(i)^2}
\end{split}
ok. （仔细想想）

Proposition 4 \lambda_n = -1 iff 这个图是二分图。
\begin{split}
\lambda_n &= \min_{\mathbf{x} \neq 0} R_P(\mathbf{x}) \
&= \min_{\mathbf{x} \neq 0} \frac{\sum_{(i, j) \in V^2} \pi(i) P(i, j) (x(i) + x(j))^2 }{2 \sum_{i=1}^n \pi(i) x(i)^2} -1
\end{split}
x(i) = -x(j) 即图可以被 2-染色.（仔细想想）

Relaxation Time

上面我们分析了 \lambda_2 和 \lambda_n 对收敛性的影响。事实上，如果 \lambda_2<1 且 \lambda_n > -1，或者等价的 P 是 aperiodic 且 irreducible，那么
\lim_{t \rightarrow \infty} \mu^T \bigg( \sum_{i=2}^n \lambda_i^t v_i v_i^T \Pi \bigg) = 0
事实上这两个特征值的绝对值还影响收敛速度。我们定义 \lambda^* = \max{|\lambda_2|, |\lambda_n|}. 定义 relaxation time 为
\tau_{rel} := \frac{1}{1 - \lambda^*}
这个 relaxation time 和 mixing time 有一个关系

Theorem 5
(\tau_{rel}-1) \log \frac{1}{2\varepsilon} \le \tau_{mix}(\varepsilon) \le \tau_{rel} \log \frac{1}{\varepsilon \pi_{min}}

From Coupling to Spectral Gap

Theorem 6 (Mu-Fa Chen, 1998) 如果有一个 coupling {\omega_t} 使得
\mathbf{E}_{(X_{t+1}, Y_{t+1}) \sim \omega_t} [d(X_{t+1}, Y_{t+1})\ \vert\ (X_t, Y_t)] \le (1 - \alpha) d (X_t, Y_t)
那么有 \lambda^* \le 1 - \alpha.

Spectral Gap 即最大的特征值和第二大的特征值之间的距离.

Proof: 略

• Coupling: 概率
• Spectral Gap: 1 - \lambda^* 代数
• Graph Expansion: 几何

Graph Expansion

Example 1 考虑图上的随机游走. 由于 P(i, j) = \frac{1}{deg(i)}，因此 stationary distribution 为 \pi(i) \sim deg(i). 可以看出完全图的 mixing time 要快于其它图.（mixing time 为常数，几乎走一步就行）

令 P 是一个 \Omega 上的 reversible chain。定义 i 到 j 的概率流 Q(i, j) := \pi(i) P(i, j). 我们想要定义 "瓶颈": 将图分成两部分，在这两部分之间的流是很少的。先定义 Q(S, \overline{S}) := \sum_{i \in S, j \in \Omega \setminus S} Q(i, j). 我们定义 S 的 expansion 为
\Phi(S) = \frac{Q(S, \overline{S})}{\pi(S)}
这里 \pi(S) = \sum_{i \in S} \pi(i).

意义：从 \Omega 中抽一个点，condition on 这个点落在 S ，它按照 markov chain 走一步走到 \overline{S} 的概率。

P 的 expansion 定义为
\Phi(P) = \min_{S \subseteq \Omega: \pi(S) \le \frac{1}{2}} \Phi(S)
我们总是取小于一半的 S. 使得 \Phi(S) = \Phi(P) 的 S 是这个图的瓶颈.

下面的定理说明了 small expansion implies slow mixing.

Theorem 7
\tau_{mix}(\varepsilon) \ge \frac{1-2\varepsilon}{2} \frac{1}{\Phi(P)}
Proof: 令 S 为这个图中的瓶颈.
\begin{split}
\mathbf{Pr}[X_t \in \overline{S}\ \vert\ X_0 \in S] &= \frac{\mathbf{Pr}[X_t \in \overline{S} \land X_0 \in S]}{\mathbf{Pr}[X_0 \in S]} \
&\le \frac{\sum_{i=0}^{t-1} \mathbf{Pr}[X_i \in S \land X_{i+1} \in \overline{S}]}{\mathbf{Pr}[X_0 \in S]} \
&= t \mathbf{Pr}[X_1 \in \overline{S}\ \vert\ X_0 \in S] = t \cdot \Phi(S)
\end{split}
因此
\mathbf{Pr}[X_t \in S\ \vert\ X_0 = x_0] \ge 1 - t \cdot \Phi(S)
那么
D_{TV} (P^t(x_0, \cdot), \pi) \ge 1 - t \cdot \Phi(S) - \pi(S) \ge \frac{1}{2} - t \cdot \Phi(S)

令它 \ge \varepsilon，得到 t \le \frac{1-2 \varepsilon}{2} \frac{1}{\Phi(P)}. 因此 mixing time 必须大等于它.

Lec 14

Graph Expansion (Cont')

Graph Expansion 还能在一般的带权无向图上定义
\Phi(S) = \frac{\sum_{i \in S, j \in \Omega \setminus S} w(i, j) }{\sum_{i, j \in S} w(i, j)}
我们回顾 sampling coloring. 我们已经证明了 \tau_{mix}(\varepsilon) \le q n \ log \frac{n} \varepsilon 对于 q > 4 \Delta. 这里我们用 Graph Expansion 来做。

考虑一个 star，并且设 1 是中间的点。记 Z 是所有的 proper colorings，S 是所有将 1 染成 1 的 proper colorings. 那么有
Q(S, \overline{S}) = \sum_{i \in S, j \in \overline{S}} \pi(i) P(i, j) = \frac{(q-1)(q-2)^{n-1}}{Z \cdot nq}
\pi(S) = \frac{(q-1)^{n-1}}{Z}. 那么
\Phi(S) = \frac{1}{nq} \frac{(q-2)^{n-1}}{(q-1)^{n-2}} = \frac{q-1}{nq} \cdot \bigg( 1 - \frac{1}{q-1}\bigg)^{n-2} \le \frac{1}{n} \exp \bigg( - \frac{n-2}{q-1} \bigg).
也就是说 \tau_{mix} = \Omega \bigg( n \cdot \exp \frac{n-2}{q-1} \bigg)= n^{\omega(1)} 若 q = O(\frac{n}{\log n}) .

Cheeger's Inequality

考虑 P 的 Laplacian，也就是 L = I - P. 有分解
L =\sum_{i=1}^n (1-\lambda_i) v_i v_i^T \Pi
我们记它的特征值为 \gamma_i = 1 - \lambda_i. 那么有 0 = \gamma_1 \le \gamma_2 \le \dots \le \gamma_n \le 2.

Cheeger's Inequality 为
\frac{\gamma_2}{2} \le \Phi(P) \le \sqrt{2 \gamma_2}