App. A 概率 / 线代 / 图论背景：翻译 + 学习笔记

证明目标：证明 $\mathbb P(X\ge a)\le\mathbb EX/a$，其中 $X\ge0$ 且 $a>0$。

在事件 $\{X\ge a\}$ 上有 $X\ge a$，在其补集上 $X1_{X\ge a}=0$，所以逐点有 $$X\ge X1_{X\ge a}\ge a1_{X\ge a}.$$ 两边取期望，得到 $$\mathbb EX\ge\mathbb E(X1_{X\ge a})\ge a\mathbb E1_{X\ge a}=a\mathbb P(X\ge a).$$ 除以 $a$ 即得结论。闭合检查：只使用了非负性与 $a>0$；不需要独立性或方差存在。

证明目标：对正整数值 $X$，证明 $\mathbb P(X\ne0)\le\mathbb EX$。

整数值性给出事件恒等式 $$\{X\ne0\}=\{X>0\}=\{X\ge1\}.$$ 对阈值 $a=1$ 应用 Proposition A.6： $$\mathbb P(X\ne0)=\mathbb P(X\ge1)\le\frac{\mathbb EX}{1}=\mathbb EX.$$ 闭合检查：正值保证 Markov 的非负条件；整数值保证把“非零”变成阈值至少为 $1$ 的事件。

令 $X=\sum_{i=1}^{m}1_{A_i}$。这是一个正整数值随机变量，且 $$\{X>0\}=\bigcup_{i=1}^{m}A_i,\qquad \mathbb EX=\sum_{i=1}^{m}\mathbb E1_{A_i}=\sum_{i=1}^{m}\mathbb P(A_i).$$ 由 Corollary A.2， $$\mathbb P\left(\bigcup_{i=1}^{m}A_i\right)=\mathbb P(X>0)\le\mathbb EX=\sum_{i=1}^{m}\mathbb P(A_i).$$ 这里不需要事件相互独立；这正是并集界在网络随机事件估计中便于使用的原因。

令 $Y=(X-\mathbb EX)^2\ge0$。事件 $\{|X-\mathbb EX|\ge a\}$ 等价于 $\{Y\ge a^2\}$，因此由 Markov 不等式 $$\mathbb P(|X-\mathbb EX|\ge a)=\mathbb P(Y\ge a^2)\le\frac{\mathbb EY}{a^2}=\frac{\operatorname{Var}X}{a^2}.$$ 闭合检查：$a>0$ 使 $a^2$ 可作 Markov 阈值；无需对 $X$ 作有界性假设，只需方差有限才使右端有限。

令 $U_n=(X_1+\cdots+X_n)/n$。若 $X_i$ 独立同分布，均值为 $\mu$、方差为 $\sigma^2$，则 $$\mathbb E U_n=\mu,\qquad \operatorname{Var}(U_n)=\frac{1}{n^2}\sum_{i=1}^{n}\operatorname{Var}(X_i)=\frac{\sigma^2}{n}.$$ 对 $U_n$ 使用中心化的 Chebyshev 不等式，得到 $$\mathbb P(|U_n-\mu|\ge\varepsilon)\le\frac{\operatorname{Var}(U_n)}{\varepsilon^2}=\frac{\sigma^2}{n\varepsilon^2}\longrightarrow0.$$

原书显示式写成 $\mathbb P(|U_n|\ge\varepsilon)$，且把 $U_n$ 的方差叙述为 $\sigma^2$；这两处与上面的闭合推导不一致，译文已用校勘提示保留原样，学习笔记只说明能使陈述成立的标准解释。原书随后提到“有限方差不是必要条件”和强大数律；这两句是未展开的外部理论指针，不在本附录内证明。

若 $X=0$，则 $|X-\mathbb EX|=\mathbb EX$；更一般地，$|X-\mathbb EX|\ge\mathbb EX$ 蕴含 $X\le0$ 或 $X\ge2\mathbb EX$，所以 $$\{X=0\}\subseteq\{|X-\mathbb EX|\ge\mathbb EX\}.$$ 由 Chebyshev， $$\mathbb P(X=0)\le\frac{\operatorname{Var}X}{(\mathbb EX)^2}.$$ 再用 $\operatorname{Var}X=\mathbb E(X^2)-(\mathbb EX)^2$，得到 $$\frac{\operatorname{Var}X}{(\mathbb EX)^2}=\frac{\mathbb E(X^2)}{(\mathbb EX)^2}-1.$$

因为 $X=X1_{X>0}$（$X$ 为正随机变量），Cauchy–Schwarz 给出 $$\mathbb EX=\mathbb E(X1_{X>0})\le\sqrt{\mathbb E(X^2)}\sqrt{\mathbb P(X>0)}.$$ 两边平方并除以 $\mathbb E(X^2)$，有 $$\mathbb P(X>0)\ge\frac{(\mathbb EX)^2}{\mathbb E(X^2)}.$$ 取补集并使用 $\mathbb E(X^2)-(\mathbb EX)^2=\operatorname{Var}(X)$，便得 $$\mathbb P(X=0)\le1-\frac{(\mathbb EX)^2}{\mathbb E(X^2)}=\frac{\operatorname{Var}(X)}{\mathbb E(X^2)}.$$

由分布定义，$\mathbb EX_n=n^2(1/n)=n$，且 $\mathbb E(X_n^2)=n^4(1/n)=n^3$。因此 $$\operatorname{Var}(X_n)=\mathbb E(X_n^2)-(\mathbb EX_n)^2=n^3-n^2=n^2(n-1).$$ 并且 $\mathbb P(X_n>0)=1/n\to0$，所以这里至少能无条件读成 $X_n\to0$ 依概率；若要说几乎处处收敛，还需要关于不同 $n$ 之间联合分布的额外信息，原书没有给出。

自反性：每个节点 $u$ 都有长度为 $0$ 的路径回到自身，故 $u\leftrightarrow u$。

传递性：若 $u\leftrightarrow v$，存在从 $u$ 到 $v$ 的路径；若 $v\leftrightarrow z$，存在从 $v$ 到 $z$ 的路径。把两条路径在 $v$ 处拼接，得到从 $u$ 到 $z$ 的路径，故 $u\leftrightarrow z$。

对称性：无向图中从 $u$ 到 $v$ 的路径逐边反向后就是从 $v$ 到 $u$ 的路径，故 $u\leftrightarrow v$ 蕴含 $v\leftrightarrow u$。三条性质成立，所以 $\leftrightarrow$ 是等价关系。

无自环时，$A_{ii}=0$；对无向无权图，若 $i\sim j$ 则 $A_{ij}=1$，否则 $A_{ij}=0$，而 $D_{ii}=d_i$。因此 $L=D-A$ 给出 $$L_{ii}=d_i,\quad L_{ij}=-1\ (i\sim j),\quad L_{ij}=0\ \text{（其他）}.$$ 又因为 $\mathcal L=D^{-1/2}LD^{-1/2}$，对角元为 $d_i^{-1/2}d_i d_i^{-1/2}=1$；相邻的非对角元为 $d_i^{-1/2}(-1)d_j^{-1/2}=-1/\sqrt{d_id_j}$，其余为 $0$。这正是引理中的两个分段式。

二次型恒等式。由于 $d_i=\sum_j a_{ij}$ 且 $A$ 对称， $$ \begin{aligned} \frac12\sum_{i,j}a_{ij}(x_i-x_j)^2 &=\frac12\sum_{i,j}a_{ij}x_i^2-\sum_{i,j}a_{ij}x_ix_j+\frac12\sum_{i,j}a_{ij}x_j^2\\ &=\sum_i d_i x_i^2-\sum_{i,j}a_{ij}x_ix_j\\ &=x^\top Dx-x^\top Ax=x^\top Lx. \end{aligned} $$ 对矩阵 $X=[X_{\cdot1},\ldots,X_{\cdot K}]$，迹的线性性给出 $$\operatorname{Tr}(X^\top LX)=\sum_{k=1}^{K}X_{\cdot k}^\top LX_{\cdot k},$$ 对每一列使用刚证明的恒等式即得命题中的矩阵式。

对称与半正定。$D$、$A$ 对称，所以 $L$ 对称；二次型恒等式右边是非负项之和，故 $x^\top Lx\ge0$，$L$ 半正定。

谱与零向量。实对称矩阵的特征值为实数，半正定性使它们都非负。最后，$A1_n=d$（其中 $d=(d_1,\ldots,d_n)^\top$），所以 $$L1_n=(D-A)1_n=d-d=0_n.$$ 闭合检查：二次型恒等式同时给出能量解释与零空间入口；它是 Lemma A.7、Proposition A.12 以及后续谱方法的共同依赖。

证明目标：证明 $\mathcal L=D^{-1/2}LD^{-1/2}$ 的二次型恒等式、半正定性、谱区间 $[0,2]$ 与零特征向量。以下假设没有孤立节点，或采用 Remark A.6 的逆矩阵约定。

令 $y=D^{-1/2}x$。由 Proposition A.10 的二次型恒等式， $$x^\top\mathcal Lx=(D^{-1/2}x)^\top L(D^{-1/2}x)=y^\top Ly=\frac12\sum_{i,j}a_{ij}(y_i-y_j)^2,$$ 即 $$x^\top\mathcal Lx=\frac12\sum_{i,j}a_{ij}\left(\frac{x_i}{\sqrt{d_i}}-\frac{x_j}{\sqrt{d_j}}\right)^2.$$ 对矩阵 $X$ 按列相加即可得到迹公式。因此 $\mathcal L$ 对称且半正定。

为证明上界，对任意实数 $u,v$ 使用 $(u-v)^2\le2(u^2+v^2)$： $$ \begin{aligned} x^\top\mathcal Lx &\le\frac12\sum_{i,j}a_{ij}\,2(y_i^2+y_j^2)\\ &=2\sum_i d_i y_i^2=2\sum_i x_i^2=2\|x\|_2^2. \end{aligned} $$ Rayleigh 商因此落在 $[0,2]$，所有特征值都在该区间。最后，$L1_n=0$，所以 $$\mathcal L(D^{1/2}1_n)=D^{-1/2}LD^{-1/2}D^{1/2}1_n=D^{-1/2}L1_n=0,$$ 即 $D^{1/2}1_n$ 是零特征向量。闭合检查：谱上界只使用非负权重与对称性；若存在孤立节点，需按 Remark A.6 的约定逐坐标解释。

设 $V_1,\ldots,V_K$ 是连通分量。若 $LX=0$，则 $$0=X^\top LX=\frac12\sum_{i,j}a_{ij}(x_i-x_j)^2.$$ 每一项均非负，因此每条有正权边 $(i,j)$ 都满足 $x_i=x_j$。同一连通分量中的任意两个节点可由路径连接，沿路径逐边使用相等性，得到该分量上 $X$ 为常值。

反过来，若 $X$ 在每个 $V_k$ 上为常值，则每条边的两端属于同一连通分量，所以 $x_i-x_j=0$。于是对每个 $i$， $$ (LX)_i=\sum_j a_{ij}(x_i-x_j)=0, $$ 从而 $LX=0$。这补全了原书 “Reciprocally, direct computation” 留下的一步。

按连通分量排序节点，$L$ 呈块对角形式 $\operatorname{diag}(L_1,\ldots,L_k)$。每个连通块 $L_r$ 由 Lemma A.7 知道其零空间恰由常向量张成：若 $L_rz=0$，则 $z$ 在该连通分量上为常值；反之常向量确实被 $L_r$ 消去。因此每个块的零特征值重数为 $1$，整体零空间维数为 $k$。

对每个分量 $V_r$，指标向量 $1_{V_r}$ 在该分量上为 $1$、其他分量上为 $0$，故 $L1_{V_r}=0$。这些向量支撑集互不相交，线性无关；又整体零空间维数为 $k$，因此它们构成 $\operatorname{Ker}L$ 的一组基。于是零特征值重数正好等于连通分量数。

对 $M=\begin{pmatrix}1&i\\i&-1\end{pmatrix}$， $$ \det(M-\lambda I)=\det\begin{pmatrix}1-\lambda&i\\i&-1-\lambda\end{pmatrix} =(1-\lambda)(-1-\lambda)-i^2=\lambda^2. $$ 唯一特征值是 $0$，且代数重数为 $2$。但 $\ker M$ 只有一维（例如方程 $x+iy=0$ 只给出一个独立约束），几何重数为 $1$，所以 $M$ 不可对角化。这里“对称”是转置对称，不是 Hermitian 共轭转置对称。

对任意 $x\in\mathbb R^n$， $$x^\top M^\top Mx=(Mx)^\top(Mx)=\|Mx\|_2^2\ge0,$$ 所以 $M^\top M$ 对称且半正定。若 $M$ 可逆，则 $Mx=0$ 只可能在 $x=0$ 发生，于是对每个非零 $x$ 有 $\|Mx\|_2^2>0$，矩阵才是正定。故原书 “for all $M$ ... definite positive” 少了 $M$ 可逆的条件；译文保留原书措辞，学习笔记明确给出最小修正。

设 $p\ge1$，$\|x\|_p=(\sum_i|x_i|^p)^{1/p}$。

1. 正性：每个 $|x_i|^p\ge0$，所以 $\|x\|_p\ge0$。
2. 定性：$\|x\|_p=0$ 当且仅当每个 $|x_i|^p=0$，也就是每个 $x_i=0$，故 $x=0$。
3. 齐次性：对 $t\in\mathbb R$， $$\|tx\|_p=\left(\sum_i|t x_i|^p\right)^{1/p}=|t|\left(\sum_i|x_i|^p\right)^{1/p}=|t|\|x\|_p.$$
4. 三角不等式：Minkowski 不等式给出 $$\left(\sum_i|x_i+y_i|^p\right)^{1/p}\le\left(\sum_i|x_i|^p\right)^{1/p}+\left(\sum_i|y_i|^p\right)^{1/p}.$$

因此 $\|\cdot\|_p$ 是范数。原书 Proof 只写“前三条 straightforward，三角不等式由 Minkowski”，本卡补足了前三条的逐点验证；Minkowski 本身作为标准不等式使用。

先看 $\|x\|=1$ 的情形。若 $x\ne0$，令 $y=x/\|x\|$，则 $\|y\|=1$ 且由齐次性 $\|Ax\|=\|x\|\|Ay\|$。因此 $$\sup_{x\ne0}\frac{\|Ax\|}{\|x\|}=\sup_{\|y\|=1}\|Ay\|.$$ 若 $\|x\|\le1$，写成 $x=r y$（$0\le r\le1$，$\|y\|=1$）即可得 $\|Ax\|=r\|Ay\|\le\sup_{\|y\|=1}\|Ay\|$；单位球包含单位球面，所以两个 supremum 相等。最后，有限维空间中单位球是紧集，$x\mapsto\|Ax\|$ 连续，因此 supremum 在 $\|x\|\le1$ 上取得，成为最大值。

以下均从 $\|||A|||=\sup_{\|x\|=1}\|Ax\|$ 出发。

1. $1$-范数。有 $$\|Ax\|_1=\sum_i\left|\sum_jA_{ij}x_j\right|\le\sum_{i,j}|A_{ij}||x_j|=\sum_j\left(\sum_i|A_{ij}|\right)|x_j|.$$ 当 $\|x\|_1=1$ 时，右端不超过最大列和；取 $x$ 为对应最大列的坐标向量并选择符号，即可达到该列和。因此 $$\|||A|||_1=\max_j\sum_i|A_{ij}|.$$

2. $\infty$-范数。有 $$\|Ax\|_\infty=\max_i\left|\sum_jA_{ij}x_j\right|\le\max_i\sum_j|A_{ij}|\,\|x\|_\infty.$$ 取对应最大行的符号向量可达到上界，故 $$\|||A|||_\infty=\max_i\sum_j|A_{ij}|.$$

3. $2$-范数。对 $\|x\|_2=1$， $$\|Ax\|_2^2=x^\top A^\top Ax.$$ $A^\top A$ 对称半正定，Rayleigh 商最大值是其最大特征值，所以 $$\|||A|||_2^2=\lambda_{\max}(A^\top A),\qquad\|||A|||_2=\sqrt{\lambda_{\max}(A^\top A)}.$$

4. 逆矩阵。若 $A$ 可逆，则 $A^{-1}$ 的奇异值是 $A$ 的奇异值的倒数，故 $$\|||A^{-1}|||_2=\frac{1}{\sigma_{\min}(A)}=\frac{1}{\sqrt{\lambda_{\min}(A^\top A)}}.$$ 原书写成 $1/\lambda_{\min}(A^\top A)$，缺少平方根；该卡给出的是与第 3 条和标准 Euclidean 算子范数一致的校正公式，不是对译文原文的静默修改。

对任意 $x\ne0$，由诱导范数定义及齐次性， $$\|ABx\|\le\|||A|||\,\|Bx\|\le\|||A|||\,\|||B|||\,\|x\|.$$ 除以 $\|x\|$ 后取所有 $x\ne0$ 的 supremum，得到 $\|||AB|||\le\|||A|||\,\|||B|||$。注意这里关键是同一个向量范数先控制 $A$，再控制 $B$；任意元素范数不具有这条链，Counterexample A.12 正说明了这一点。

证明目标：证明 (A.1)、(A.2)、(A.3) 的 Rayleigh 商表述，并识别取极值的特征向量。

证明一：正交对角化

由谱定理，存在正交矩阵 $P$ 与对角矩阵 $D=\operatorname{diag}(\lambda_1,\ldots,\lambda_n)$，使 $M=P^\top DP$。令 $y=Px$，则 $\|y\|_2=\|x\|_2$，且 $$x^\top Mx=y^\top Dy=\sum_{i=1}^{n}\lambda_i y_i^2.$$ 当 $\|x\|_2=1$ 时，$\sum_i y_i^2=1$，所以该值是特征值的加权平均，落在 $[\lambda_1,\lambda_n]$。令 $y=e_1$ 达到 $\lambda_1$，令 $y=e_n$ 达到 $\lambda_n$。因为 $v_i=P^\top e_i$，对应的 $x$ 正是 $v_1,v_n$。

若再施加 $x\perp v_1$，则 $$0=x^\top v_1=(Px)^\top(Pv_1)=y^\top e_1=y_1.$$ 约束变为 $\sum_{i=2}^{n}y_i^2=1$，所以最小加权平均为 $\lambda_2$，由 $y=e_2$（即 $x=v_2$）取得。这证明了三条单位球形式；对非零 $x$，将 $x$ 归一化即可得到分式形式，因为 $$\frac{(cx)^\top M(cx)}{(cx)^\top(cx)}=\frac{x^\top Mx}{x^\top x}\quad(c\ne0).$$

证明二：Lagrange 乘子

在 $\|x\|_2=1$ 的约束下，令 $$\mathcal L(x,\lambda)=x^\top Mx-\lambda(x^\top x-1).$$ 对 $\lambda$ 求导给出 $x^\top x=1$，对 $x$ 求导给出 $$\nabla_x\mathcal L=2Mx-2\lambda x=0,$$ 即 $Mx=\lambda x$。因此任何受约束临界点都是特征向量，目标值为相应特征值；全局最小值和最大值分别是最小、最大特征值。加入 $x\perp v_1$ 后，允许的特征方向排除 $v_1$，最小可取方向变为 $v_2$。这与第一种证明的全局极值和取值向量一致。

校勘/边界：若特征值有重数，arg min 不止一个向量，而是对应特征子空间中的单位向量（或 Rayleigh 商不变的子空间）；原书“由 $v_i$ 取得”是一个选取，不应理解为唯一性。

令 $M=V\Lambda_MV^\top$，其中 $V=[v_1,\ldots,v_n]$ 正交，$\Lambda_M=\operatorname{diag}(\lambda_1,\ldots,\lambda_n)$。对约束 $H^\top H=I_K$，令 $Y=V^\top H$，则 $Y^\top Y=I_K$，且 $$\operatorname{Tr}(H^\top MH)=\operatorname{Tr}(Y^\top\Lambda_MY)=\sum_{i=1}^{n}\lambda_i\|Y_{i\cdot}\|_2^2.$$ 这里 $0\le\|Y_{i\cdot}\|_2^2\le1$ 且 $\sum_i\|Y_{i\cdot}\|_2^2=\operatorname{Tr}(Y^\top Y)=K$。把总权重 $K$ 放在最小的 $K$ 个特征值上，所得下界为 $\sum_{i=1}^{K}\lambda_i$，由 $Y=[e_1,\ldots,e_K]$（即 $H=[v_1,\ldots,v_K]$）达到。因此该 $H$ 是一个最小化解。

原书 Lagrange 计算 $\partial_H\mathcal L=2MH-2H\Lambda=0$ 只说明列向量是特征向量，还需要上面的谱权重比较才能说明选的是最小的 $K$ 个方向。若存在特征值重数，任何相应最小特征子空间中的正交基都可给出等价解。

由图梯度定义， $$ \begin{aligned} \langle\operatorname{grad}f,G\rangle_{\mathcal F(E)} &=\sum_{i,j}\gamma(w_{ij})(f(j)-f(i))G(i,j)\\ &=\sum_{i,j}\gamma(w_{ij})f(j)G(i,j)-\sum_{i,j}\gamma(w_{ij})f(i)G(i,j). \end{aligned} $$ 在第一项中交换哑指标 $i,j$，得到 $$\sum_{i,j}\gamma(w_{ji})f(i)G(j,i).$$ 于是 $$ \langle\operatorname{grad}f,G\rangle =\sum_i f(i)\sum_j\left[\gamma(w_{ji})G(j,i)-\gamma(w_{ij})G(i,j)\right]. $$ 根据伴随定义，方括号中的和就是 $(\operatorname{div}G)(i)$，从而 $$ (\operatorname{div}G)(i)=\sum_j\gamma(w_{ji})G(j,i)-\gamma(w_{ij})G(i,j). $$ 若图无向，$w_{ij}=w_{ji}$，提出同一个 $\gamma(w_{ij})$ 即得翻译页中的简化式。这里把 OCR 中重复且下标混乱的中间行按 PDF 文本层的指标交换恢复；恢复的是原书推导，不是学习层的新结论。

记 $\gamma_{ij}=\gamma(w_{ij})$。由 Lemma A.14 和梯度定义， $$ \begin{aligned} (\Delta_\gamma f)(i) &=(\operatorname{div}\operatorname{grad}f)(i)\\ &=\sum_j\left[\gamma_{ji}(\operatorname{grad}f)(j,i)-\gamma_{ij}(\operatorname{grad}f)(i,j)\right]\\ &=\sum_j\left[\gamma_{ji}^2(f(i)-f(j))-\gamma_{ij}^2(f(j)-f(i))\right]\\ &=\sum_j(\gamma_{ij}^2+\gamma_{ji}^2)(f(i)-f(j)). \end{aligned} $$ 这就是引理的公式。若图无向，两个权重相等，于是得到 $$\Delta_\gamma f(i)=2\sum_j\gamma(w_{ij})^2(f(i)-f(j)).$$

因子与函数依赖提示。原书随后直接写 $L=\Delta_\gamma$（取 $\gamma(x)=\sqrt{x}$）以及 $L_{\rm rw}=\Delta_\gamma$（取 $\gamma(w_{ij})=\sqrt{w_{ij}/d_i}$）。若每条无向边按两个方向计入上述求和，前者会出现因子 $2$；后者的“$\gamma$”还依赖 $i$。因此这里应把原书识别式看作依赖其边集/归一化约定的排印陈述；译文保留原式，不能静默去掉这个疑点。