正文
以下部分是我学习CMU 15-751: TCS Toolkit的课堂笔记。由于只是个人笔记，因此许多地方在推导上可能不那么严谨，还望理论大佬多多包涵。
1 问题定义
1.1 无向图\(G\)
在本文中，我们将研究对象限定在无向图（undirected graph）\(G=(V, E)\)，且满足：
- 有限（finite）；
- 允许重边和自环；
- 不允许度为0的顶点（即孤立，isolated顶点），但允许有多个连通分量；
此外，我们在某些情况下可能会假设\(G\)是正则的。
正则图：指各顶点的度均相同的无向简单图。
1.2 顶点标签\(f\)
定义 设函数
\[f: V\rightarrow \mathbb{R}
\]
将图的每个顶点用一个实数值来进行标记，我们称其为顶点标签（vertex labelling）。在实际应用场景中，\(f\)可能是温度、电压、嵌入的坐标（推广到\(\mathbb{R}^d\)时）或者\(S\subseteq V\)的0-1示性函数。
在本文中，我们会将函数\(f\)想成是一个如下所示的（列）向量：
\[\left(\begin{aligned}
\bigg|\\
f\\
\bigg|
\end{aligned}\right)\begin{aligned}
\leftarrow &v_1\\
\leftarrow &v_2\\
&\vdots \\
\leftarrow &v_n
\end{aligned}
\]
回顾 函数集合\(\mathcal{F}=\{f: V\rightarrow \mathbb{R}\}\)上带有加法和标量乘法：
- 加法：\(f+g\)（逐点）；
- 标量乘法：\(c\cdot f\)（\(c\in\mathbb{R}\)）；
可以证明，\(\mathcal{F}\)是一个向量空间，且维度\(n=|V|\)。后面我们还会在\(\mathcal{F}\)上定义内积和范数。
2 Laplacian二次型
2.1 定义
接下来我们将要介绍的是谱图论（spectral graph theory）的关键，也就是Laplacian二次型（Laplacian quadratic form），其定义如下：
\[\mathcal{E}\left[f\right] = \frac{1}{2}\cdot\mathbb{E}_{u\sim v}\left[ \left(f\left(u\right) - f\left(v\right)\right)^2\right]
\]
（符号约定：\(u\sim v\)表示服从均匀分布的随机无向边\((u, v)\in E\)）
直观地理解，Laplacian二次型刻画了图的“能量”（energy），这也是我们为什么用\(\mathcal{E}(f)\)来表示它的原因。它在其它语境下，又被称为Dirichlet形式（Dirichlet form），局部方差（local variance），解析边界大小（analytic boundary size）。
2.2 性质
关于Laplacian二次型，我们有以下事实：
-
\(\mathcal{E}\left[f\right]\geqslant 0\)；
-
\(\mathcal{E}\left[c \cdot f\right] = c^2 \cdot \mathcal{E}\left[f\right]\)；
-
\(\mathcal{E}\left[f + c \right] = \mathcal{E}\left[f\right]\)（\(c\in\mathbb{R}\)）；
直觉上，\(\mathcal{E}\left[f\right]\)的值越小，也就意味着\(f\)更加“光滑”（smooth），即其值不会沿着边变化得太剧烈。
例 设图顶点的子集\(S\subseteq V\), 0-1示性函数\(f=\mathbb{I}_{S}\)用于指示顶点是否在集合\(S\)中，即：
\[f(u) = \left\{\begin{matrix}
1\quad\text{if}\quad u\in S\\
0\quad\text{if}\quad u\notin S
\end{matrix}\right.
\]
则我们有：
\[\begin{aligned}
\mathcal{E}\left[f\right] &= \frac{1}{2}\cdot\mathbb{E}_{u\sim v}\left[\left(\mathbb{I}_S(u) - \mathbb{I}_S(v)\right)^2\right] \\
&= \frac{1}{2} \cdot \mathbb{E}_{u\sim v}\left[\mathbb{I}_{(u, v) \text{ crosses the cut } (S, \bar{S})}\right]\\
&= \frac{1}{2}\left[\text{frac. of edges on the boundary of $S$}\right]\\
&= \text{Pr}_{u\sim v}\left[u\rightarrow v \text{ is stepping out of } S\right]
\end{aligned}
\]
注意上述式子中要乘以\(1/2\)是因为我们考虑的是无向图，要避免有向边的重复计数（即“伸出”与“伸入”\(S\)），最后只需计算“伸出”\(S\)的边。
2.3 标准随机游走
为了选择一个随机顶点，我们可以：
- 均匀随机地选择一条边 \((u, v)\)；
- 输出 \(u\)（或\(v\)）；
我们依据此采样方式得到的顶点分布记为\(\pi\)，\(\pi_i\)表示顶点\(i\)被抽中的概率。我们有以下事实：
事实 \(\pi(u)\)正比于\(\text{deg}(u)\)，即
\[\pi [u] = \frac{\text{deg}(u)}{2|E| }，
\]
（注意这里用到了握手定理，即\(\sum_v \text{deg}(v)=2|E|\)）
直观地看，\(\pi\)为每个顶点给出了权重/重要性。
注：如果\(G\)是正则的，那么\(\pi\)是在\(V\)上的均匀分布。
在此基础上，我们可以得到一些有用的结论。
事实 下列步骤：
- 随机采 \(u\sim \pi\)；
- 再均匀随机地采\(u\)的一个邻居\(v\)（记为\(v\sim u\)）
实质上就等价于均匀随机地采样边\((u, v)\)。如果我们接着输出\(v\)，则\(v\)也服从分布\(\pi\)。
推论 设\(t\in \mathbb{N}\)，随机采\(u\sim \pi\)，进行\(t\)步的 “标准随机游走”（standard random walk，S.R.W.）：
\[\underbrace{u \rightarrow \cdot \rightarrow \cdot \rightarrow \cdots \rightarrow v}_{t}
\]
则\(v\)的分布也是\(\pi\)。
定义 \(\pi\)是不变（invariant）/ 平稳（stationary）分布。
Q： 现在假设\(u_0\in V\)是非随机的，并从\(u_0 \overset{t}{\rightsquigarrow}v\)。随着\(t\rightarrow \infin\)，\(v\)的分布是否还会\(\rightarrow \pi\)？
A： 当\(G\)非连通图时不是；当\(G\)为二分图时也不是；而其它情况都是如此（我们后面会介绍原因）。
Q： 那么需要多少步才能到达平稳分布呢（也即马尔可夫链的混合时间，mixing time）？
A： 这需要考虑图\(G\)的谱（特征值），具体我们会在下一讲中介绍。直观的例子比如图拥有较小的割集，那么在随机游走时就需要较长的时间来跨越\(S\)和\(\bar{S}\)；更极端的例子比如非连通图直接永远不会达到平稳分布。在\(2.2\)中我们证明了若图的割集较小则其\(\mathcal{E}\left[\mathbb{I}_S\right]\)就较小，而我们后面会看到快速收敛等价于\(\mathcal{E}\left[f\right]\)永远不会小。
2.4 \(f\)的均值和方差
设\(f:V\rightarrow \mathbb{R}\)，若\(u\sim \pi\)，则\(f(u)\)是一个实随机变量（我们这里简记为\(f\)）。对于该随机变量，我们接下来讨论它的均值与方差。
均值（mean） \(f\)的均值定义为：
\[\mathbb{E}\left[f\right] = \mathbb{E}_{u\sim \pi}\left[f(u)\right]
\]
例 若\(S\subseteq V\)，\(f=\mathbb{I}_S\)，则
\[\mathbb{E}\left[ f \right] = \text{Pr}_{u\sim \pi}\left[u\in S\right]
\]
直观上，这个概率表示\(S\)的“权重”或“体积”。
方差（variance） \(f\)的方差定义为：
\[\begin{aligned}
\text{Var}\left[f\right]=\text{Var}_{u\sim \pi}\left[f(u)\right]&\overset{(1)}{=}\mathbb{E}_{u\sim \pi}\left[\left(f\left(u\right) - \mu\right)^2\right] \\
&\overset{(2)}{=}\mathbb{E}_{u\sim\pi}\left[f(u)^2\right] -\mathbb{E}_{u\sim\pi}\left[f(u)\right]^2 \\
&\overset{(3)}{=} \frac{1}{2}\mathbb{E}_{\underset{\text{indep.}}{u, v \sim \pi}}\left[\left(f\left(u\right) - f\left(v\right)\right)^2\right]
\end{aligned}
\]
注意，上述式\((3)\)成立是由于：
\[\begin{aligned}
&\mathbb{E}\left[\left(f\left(u\right) - f\left(v\right)\right)^2\right]\\
&=\mathbb{E}\left[f(u)^2 - 2f(u)f(v) + f(v)^2\right] \\
&=\underbrace{\mathbb{E}\left[f(u)^2\right] + \mathbb{E}\left[f(v)^2\right]} - \underbrace{2 \mathbb{E}\left[f(u)f(v)\right]}\\
&= 2\cdot \mathbb{E}\left[f(u)^2\right] - \underbrace{2\mathbb{E}\left[f(u)\right]\mathbb{E}\left[f(v)\right]}_{2\cdot\mathbb{E}\left[f(u)\right]^2}
\end{aligned}
\]
辨析 这里要注意\(f\)的方差\(\text{Var}(f)\)和其能量\(\mathcal{E}(f)\)的差异，它们俩的对比如下：
\[\begin{aligned}
\text{Var}\left[f\right]&=\frac{1}{2}\mathbb{E}_{\underset{\text{indep.}}{u, v \sim \pi}}\left[\left(f\left(u\right) - f\left(v\right)\right)^2\right] \\
\mathcal{E}\left[f\right]&=\frac{1}{2}\mathbb{E}_{u \sim v}\left[\left(f\left(u\right) - f\left(v\right)\right)^2\right]
\end{aligned}
\]
可见方差\(\text{Var}[f]\)是对图的顶点取期望（我们称其为关于\(f\)的全局方差，global variance），而\(\mathcal{E}[f]\)则是对图的边取期望（我们称其为关于\(f\)的局部方差，local variance）。
3 Laplacian二次型的极值
3.1 \(\mathcal{F}\)上的的内积与范数
接下来我们讨论Laplacian二次型的极值，而这就需要我们先定义\(\mathcal{F}=\{f: V\rightarrow \mathbb{R}\}\)空间上的内积和范数。
定义 设\(f, g: V\rightarrow\mathbb{R}\)，则向量空间\(\mathcal{F}\)上的 加权内积（weighted inner product） 可以定义为：
\[\langle f, g \rangle_{\pi} := \mathbb{E}_{u\sim \pi}[f(u)\cdot g(u)]
\]
直观地，我们可以将其写做：
\[\langle
\left(\begin{aligned}
\bigg| \\
f\\
\bigg|
\end{aligned}\right),
\left(\begin{aligned}
\bigg| \\
g\\
\bigg|
\end{aligned}\right)
\rangle_{\pi}
\]
注： 当\(G\)是正则图时（此时\(\pi\)为均匀分布），上式是经由\(\frac{1}{|V|}\)缩放的“标准点积”（normal dot product）。
回顾 实向量空间上的内积满足以下性质
- \(\langle f, g\rangle_{\pi}=\langle g, f\rangle_{\pi}\)；
- \(\langle c\cdot f + g, h\rangle_{\pi} = c\langle f, h\rangle_{\pi} + \langle g, h \rangle_{\pi}\)（\(c\in\mathbb{R}\)）；
- \(\langle f, f\rangle_{\pi}=\mathbb{E}_{u\sim\pi}\left[f(u)^2\right]\geqslant 0\quad \text{with equality iff } f\equiv 0\)；
定义 对于\(f\in\mathcal{F}\)，我们可以由内积诱导出\(f\)的\(2\)-范数：
\[\lVert f \rVert_2 := \sqrt{\langle f, f\rangle_{\pi}} = \sqrt{\mathbb{E}_{u\sim\pi}\left[f(u)^2\right]}。
\]
处理2-范数的平方通常比直接处理它更容易，故我们常常使用\(
\lVert f \rVert^2_2:=\langle f, f\rangle_{\pi}=\mathbb{E}_{u\sim\pi}\left[f(u)^2\right]
\)。
此外，我们还可以定义\(f\)的\(1\)-范数：
\[\lVert f \rVert_1 := \mathbb{E}_{u\sim \pi}\left[|f(u)|\right]
\]
例 设\(S\subseteq V\)，\(f=\mathbb{I}_S\)，则
\[\begin{aligned}
\lVert f\rVert_1 &:= \mathbb{E}_{u\sim\pi}\left[|f(u)|\right] =\mathbb{E}_{u\sim\pi}\left[f(u)\right] \\
&= \text{Pr}_{u\sim\pi}\left[u\in S\right] = \text{Volume}(S)
\end{aligned}
\]
且我们有
\[\begin{aligned}
\lVert f\rVert_2^2 := \mathbb{E}_{u\sim\pi}\left[f(u)^2\right] = \mathbb{E}_{u\sim\pi}\left[f(u)\right] = \lVert f\rVert_1 &
\end{aligned}
\]
3.2 最小化/最大化\(\mathcal{E}\left[f\right]\)
我们在 2.3 中提到随机游走快速收敛等价于\(\mathcal{E}\left[f\right]\)永远不会小，那么\(\mathcal{E}\left[f\right]\)能够有多小呢？
最小化 现在我们来考虑最小化\(\mathcal{E}\left[f\right]\)，即求解：
\[\min \mathcal{E}[f]
\]
我们已知\(\mathcal{E}[f]\geqslant0\)，故我们接下来讨论什么样的\(f\)可以使\(\mathcal{E}[f]=0\)。
首先对于\(f\equiv 0\)（即将图的每个顶点都映射到\(0\)）这一trival的情况，\(\mathcal{E}\left[f\right]=0\)；
接下来考虑non-trival的情况。我们注意到\(f\equiv 1\)（或任何其它常数）时，
\[\mathcal{E}[ f ]=\frac{1}{2} \mathbb{E}_{u\sim v}\left[\left(f(u) - f(v)\right)^2\right] = 0
\]
事实上，由于图的不同连通分量之间是不存在边的，因此只要保证\(f\)在图\(G\)的每个连通分量上是常数就行。
命题 \(\mathcal{E}[f]=0\)当且仅当\(f\)在\(G\)的每个连通分量上是常数。此时：
\[\#\text{ connected components of } G = \#\text{ lin. indep } f \text{ with } \mathcal{E}[f]=0
\]
即当图的连通分量为\(S_1,\cdots, S_l\)时, \(\mathbb{I}_{S_1}, \mathbb{I}_{S_2}, \cdots, \mathbb{I}_{S_l}\)是线性无关的（linearly independent）（并满足\(\mathcal{E}\left[f\right]=0\)约束）。所谓线性无关，直观上即如下所示的关系：
\[\begin{aligned}
S_1\bigg\{ \\
\\
\\
\\
\end{aligned} \left(\begin{aligned}1\\1\\1\\0\\\vdots\\0\end{aligned}\right)
\begin{aligned}
\\
\\
\\
\\
S_2 \bigg\{\\
\\
\end{aligned}\left(\begin{aligned}0\\0\\0\\1\\\vdots\\1\end{aligned}\right)
\]
更一般地说，集合\(\{f: \mathcal{E}[f]=0\}\)事实上就是\(\mathbb{I}_{S_1}, \mathbb{I}_{S_2}\cdots, \mathbb{I}_{S_l}\)的张成空间\(\{\sum^l_{i=1}c_i\mathbb{I}_{S_i}: c_1,\cdots, c_l\in \mathbb{R}\}\)。
最大化 接下来我们来考虑最大化\(\mathcal{E}\left[f\right]\)，即求解
\[\begin{aligned}
&\text{max } \mathcal{E}[f]\quad \\
\text{s.t.}\quad &\text{Var}[f]=1(\leqslant 1)
\end{aligned}
\]
（这里需要注意由于\(\mathcal{E}[c\cdot f]=c^2\mathcal{E}[f]\)，故我们要添加关于\(\text{Var}\left[f\right]\)的约束项以控制常数缩放因子的影响）
事实上，上述优化问题即等价于：
\[\begin{aligned}
&\text{max } \mathcal{E}[f]\quad \\
\text{s.t.}\quad &\lVert f \rVert^2_2=\mathbb{E}\left[ f^2 \right]=1 (\leqslant1)
\end{aligned}
\]
这是因为：
\[\begin{aligned}
\text{Var}[f] &= \mathbb{E}[f^2] - \mathbb{E}[f]^2\\
\Rightarrow\mathbb{E}[f^2] &= \text{Var}[f] + \underbrace{\mathbb{E}[f]^2}_0
\end{aligned}
\]
直觉上，该优化问题是在寻找一个好的嵌入\(V\rightarrow \mathbb{R}\)，使得边的两个端点在嵌入空间中能够尽可能“远”。那么，什么样的\(G\)才能最成功呢？答案是二分图。
如果\(G\)是二分图，\(V=(V_1, V_2)\)。设
\[f = \mathbb{I}_{V_1} - \mathbb{I}_{V_2}
\]
也即
\[f(u) = \left\{\begin{aligned}
+1, \quad \text{if } u \in V_1 \\
-1, \quad \text{if } u \in V_2
\end{aligned}\right.，
\]
于是我们有\(\lVert f \rVert^2_2=\mathbb{E}[f^2]=\mathbb{E}\left[1\right]=1\)，且\(\mathcal{E}[f]=2\)（由于\(\frac{1}{2}\mathbb{E}_{u\sim v}[(f(u) - f(v))^2]\)中\(f(u)\)和\(f(v)\)都为\(\pm1\)）
命题 \(\mathcal{E}[f] \leqslant 2 \lVert f \rVert^2_2\)（即\(2\mathbb{E}[f^2]\)）
证明如下：
\[\begin{aligned}
\mathcal{E}[f] &= \frac{1}{2}\mathbb{E}_{u\sim v}\left[(f(u)-f(v))^2\right]\\
&= \frac{1}{2} \mathbb{E}_{\underbrace{u\sim v}_{u\sim\pi}}[f(u)^2] + \frac{1}{2}\mathbb{E}_{\underbrace{u\sim v}_{v\sim\pi}}[f(v)^2] - \mathbb{E}_{u\sim v}[f(u)f(v)]\\
& \leqslant \mathbb{E}[f^2] + \underbrace{\sqrt{\mathbb{E}_{u\sim v}[f(u)^2]}}_{\mathbb{E}\left[f^2\right]}\underbrace{\sqrt{\mathbb{E}_{u\sim v}[f(v)^2]}}_{\mathbb{E}\left[f^2\right]} \quad (\text{Cauchy Schwarz})\\
&=2 \mathbb{E}[f^2]
\end{aligned}
\]
例 等式\(\mathcal{E}[f] = 2 \lVert f\rVert^2_2\)当且仅当\(G\)为二分图的时候成立。
4 Markov转移算子
4.1 定义
根据我们前面在 3.2 中的的叙述，我们已经知道
$\mathcal{E}[f]=\text{arithm}= \lVert f\rVert^2_2 - \mathbb{E}_{u\sim v}[f(u)\cdot f(v)] $
这里
\[\mathbb{E}_{u\sim v}[f(u)\cdot f(v)]=\mathbb{E}_{u\sim\pi}\mathbb{E}_{v\sim u}[f(u)f(v)] = \mathbb{E}_{u\sim\pi}\left[f(u)\cdot \underbrace{\mathbb{E}_{v\sim u}\left[f(v)\right]}_*\right]
\]
注意上图中的带\(*\)表达式\(\mathbb{E}_{v\sim u}\left[f(v)\right]\)刻画的是顶点\(u\)邻居集合\(\{v\}\)的\(f\)标签平均值。而这个表达式实际上描述了一个将顶点\(u\)映射到其邻居标签平均值的函数，接下来我们就来进一步研究这个函数。
定义 我们定义函数\(Kf: V\rightarrow\mathbb{R}\)满足
\[ \quad (Kf)(u)= \mathbb{E}_{v\sim u}\left[f(v)\right]
\]
由于我们是离散状态空间，故上式可以写为\((Kf)(u)=\sum_v f(v)\text{Pr}\left[v\rightarrow u\mid v\right]\)，这里\(\text{Pr}[v\rightarrow u\mid v]\)表示邻居顶点\(v\)到当前顶点\(u\)的状态转移概率。直观地理解，函数\(Kf\)使得顶点\(u\)被赋予其邻居集合的\(f\)标签平均值。
这里\(K\)为定义在函数空间\(\mathcal{F}=\{f: V\rightarrow \mathbb{R}\}\)上的线性算子，它将函数\(f\in\mathcal{F}\)映射到\(Kf\in\mathcal{F}\)，并满足：
\[\begin{aligned}
&K(f + g) = Kf + Kg \\
&K(c\cdot f) = c\cdot\left( Kf\right)\quad (c\in \mathbb{R})
\end{aligned}
\]
定义 我们将上述的算子\(K\)称为图\(G\)的Markov转移算子（Markov transition operator）/归一化邻接矩阵（normalized adjacency matrix）。
我们可以将算子\(K\)表示成一个矩阵，该矩阵以如下方式作用：
\[\begin{aligned}
u\rightarrow\\
\\
\end{aligned}\left(
\begin{matrix}
& \cdots & \\
& K & \\
& &
\end{matrix}\right)\left(\begin{matrix}
\bigg| \\
f \\
\bigg|
\end{matrix}\right)\begin{aligned}
\leftarrow &v_1\\
&\vdots\\
\leftarrow &v_n
\end{aligned}
=\left(\begin{aligned}
\bigg|\\
K&f \\
\bigg|
\end{aligned}\right)
\begin{aligned}
\leftarrow u \\
\\
\\
\end{aligned}
\]
且满足
\[K[u, v]=\left\{
\begin{aligned}
& \frac{1}{\text{deg}(v)}, f(v, u)\in E \\
& 0
\end{aligned}
\right\}=\text{Pr}_{\text{S.R.W.}}[v\rightarrow u\mid v]
\]
所以\(K\)是归一化后的邻接矩阵\(A\)的转置（当然这里由于我们关注无向图，\(A^T=A\)），其每一列的和为\(1\)（代表一个概率分布）。这样的矩阵被称为随机矩阵（stochastic marix）。
4.2 自伴性质
如果图\(G\)是\(d\)-正则的（即所有顶点的度都为\(d\)），那么我们有：
\[K = \frac{1}{d} A \quad \& \quad K\text{ is symmtric, } K^T= K
\]
那么对于非正则图呢？此时\(K\)的矩阵表示（在非规范正交基下）尽管可能不再是对称阵，但是算子\(K\)仍然满足自伴的性质。我们有以下事实：
事实 对于\(f, g: V\rightarrow \mathbb{R}\)，
\[\langle f, Kg\rangle=\mathbb{E}_{u\sim v}\left[f(u)\cdot g(v)\right]=\mathbb{E}_{v\sim u}\left[f(v)\cdot g(u)\right]
\]
证明
\[\begin{aligned}
\langle f, Kg\rangle &=\mathbb{E}_{u\sim \pi}\left[f(u)\cdot (Kg)(u) \right]\\
&=\mathbb{E}_{u\sim\pi}\left[f(u)\cdot \mathbb{E}_{v\sim u}\left[g(v)\right]\right] \\
&= \underbrace{\mathbb{E}_{u\sim \pi}\mathbb{E}_{v\sim u}}_{(u, v)\text{ rand edge}}\left[f(u)\cdot g(v)\right]\\
&= \mathbb{E}_{u\sim v}\left[f(u)\cdot g(v)\right]\\
&= \mathbb{E}_{v\sim u}\left[f(v)\cdot g(u)\right]\\
\end{aligned}
\]
基于此，我们有下列推论：
推论
\[\langle Kf, g \rangle = \langle f, Kg \rangle
\]
也即\(K\)是自伴的（self-adjoint）。而这在图\(G\)是正则图的情况下就等价于\(K\)是对称的。
接下来再来看我们熟悉的那个示性函数例子。
例 设\(S, T\subseteq V\)（\(S\cap T=\emptyset\)），\(f=\mathbb{I}_S\)，\(g=\mathbb{I}_T\)，则：
\[\begin{aligned}
\langle f, Kg\rangle &=\mathbb{E}_{u\sim v}\left[\mathbb{I}_S(u) \cdot \mathbb{I}_T(v)\right] \\
&= \text{Pr}_{u\sim v}\left[u\in S, v\in T\right]
\end{aligned}
\]
4.3 Markov链
概率分布转移 设\(p\)为在顶点\(V\)上的概率分布，即
\[p = \left(\begin{aligned}
p_1\\
p_2\\
\vdots\\
p_n
\end{aligned}\right)\begin{aligned}
\leftarrow v_1 \\
\\
\\
\leftarrow v_n
\end{aligned}
\]
我们进行如下步骤：
- 随机采一个顶点\(u\sim p\)。
- 进行一步从\(u\rightarrow v\)的随机游走，并设\(p^{\prime}\)为\(v\)的概率分布。
则我们有如下的概率分布转移关系：
\[ \left(\begin{aligned}
\bigg|\\
p^{\prime}\\
\bigg|
\end{aligned}\right)=
\left(
\begin{matrix}
& & \\
& K & \\
& &
\end{matrix}\right) \left(\begin{aligned}
\bigg|\\
p\\
\bigg|
\end{aligned}\right)
\]
推论 对于平稳概率分布\(\pi\)，满足
\[\pi K = \pi
\]
接下来我们再展示一个例子说明概率转移具体是如何运作的。
引理 对于算子$K^2 = K \circ K $，我们有：
\[(K^2 f)(u) = \mathbb{E}_{\begin{aligned}
u\rightarrow w\\
2 \text{ step}
\end{aligned}}\left[f(w)\right]
\]
证明 给定\(f\)，设\(g=Kf\)，则
\[K^2f = K(Kf) = Kg,
\]
故
\[（K^2f)(u) = (Kg)(u) = \mathbb{E}_{v\sim u}\left[g(v)\right] = \mathbb{E}_{v\sim u}\left[(Kf)(v)\right] = \mathbb{E}_{v\sim u}\left[\mathbb{E}_{w\sim v}\left[f(w)\right]\right]
\quad\blacksquare
\]
推论 \(\forall t \in \mathbb{N}\)，\((K^tf)(u)=\mathbb{E}_{u \overset{t\text{-step S.R.W}}{ \rightsquigarrow} w}\left[ f(w)\right]\)（甚至\(t=0\)时，我们也有\(I f(u) = f(u)\)）。
参考
[1] CMU 15-751: TCS Toolkit
[2] Bilibili: CMU计算机科学理论(完结)—你值得拥有的数学和计算机课)
[3] Spielman D. Spectral graph theory[J]. Combinatorial scientific computing, 2012, 18: 18.
[4] Axler S. Linear algebra done right[M]. springer publication, 2015.
