2026-08-19 · 把极限变成随机生成器

0. 导读与元结构 (Orientation & Meta-structure)

前两日留下一个尚未闭合的接口：graphon $W$ 是定义在连续概率空间上的确定性可测函数，有限图却是离散对象；为何这个“极限”不仅能记录子图统计，还能生成有限随机图，并且生成律恰好由有限图统计刻画？

今天的对象分成四层：

1. 固定的有限测试图 $F$；
2. 对称可测函数 $W:[0,1{]}^2\to [0,1]$；
3. 从 $W$ 抽样得到的有限随机图 $G(n,W)$；
4. 邻接指标阵 $A=(A_{ij}{)}_{i,j\ge 1}$ 所定义的无限随机图。

量词也分成两组。图极限一侧要求“对每个有限简单图 $F$，同态密度 $t(F,\cdot )$ 收敛”；概率一侧要求“对每个有限置换 $\sigma$，重标号后的阵 $(A_{\sigma (i)\sigma (j)})$ 与原阵同分布”。两组量词由一个等式连接：$t(F,W)$ 正是“$F$ 的所有边在一次 $W$-抽样中出现”的概率。

先修：测度与条件概率、独立性、同态密度，以及昨日的截割距离与 counting lemma。去向：可交换阵 (exchangeable arrays)、graphon 统计估计、随机网络模型，以及稀疏情形中的 graphex 或局部弱收敛。主导机制是潜变量抽样、置换不变性、重叠对计数和表示定理。

这是三日 arc 的收束：第 1 日把有限图压成可测函数，第 2 日说明截割范数为何控制固定图计数；第 3 日把同一个极限对象转译成概率律。这里的 bridge 不是重复定义 graphon，而是建立“解析极限 ↔ 可交换随机结构”的新等价层。

1. 核心概念、定理与谱系 (Concept, Theorem & Lineage)

1.1 从 graphon 到随机图

设 $(\mathrm{\Omega },\mathcal{F},\mathbb{P})$ 承载彼此独立的随机变量

$$U_1,U_2,\dots \stackrel{\mathrm{i}.\mathrm{i}.\mathrm{d}.}{\sim }\mathrm{Unif}[0,1],{\xi }_{ij}\stackrel{\mathrm{i}.\mathrm{i}.\mathrm{d}.}{\sim }\mathrm{Unif}[0,1](1\le i<j),$$

并且两族相互独立。给定 graphon，即对称可测函数 $W:[0,1{]}^2\to [0,1]$，定义

$$A_{ij}=A_{ji}=\mathbf{1}\{{\xi }_{ij}\le W(U_i,U_j)\},A_{ii}=0.$$

顶点集 $[n]$ 上由 $(A_{ij}{)}_{1\le i,j\le n}$ 给出的图记为 $G(n,W)$；全部指标给出的无限图记为 $G(\mathrm{\infty },W)$。等价地说：先抽取顶点潜变量 $U_i$，再在给定 $(U_i)$ 的条件下，让各条边独立，并令边 $ij$ 出现的条件概率为 $W(U_i,U_j)$。

该构造自动具有两项相容性：

• 限制相容性 (projective consistency)：$G(n+1,W)$ 在前 $n$ 个顶点上的诱导子图与 $G(n,W)$ 同分布；
• 联合可交换性 (joint exchangeability)：对每个只移动有限多个正整数的置换 $\sigma$，

$$(A_{\sigma (i)\sigma (j)}{)}_{i,j\ge 1}\stackrel{d}{=}(A_{ij}{)}_{i,j\ge 1}.$$

证明只用到 $(U_i)$ 同分布独立，以及 $({\xi }_{ij})$ 在无序顶点对上的同分布独立；置换改变标签，不改变联合律。

1.2 同态密度就是有限事件概率

设 $F$ 是顶点集 $[k]$ 上的有限简单图。定义

$$t(F,W)={\int }_{[0,1{]}^k}\prod _{ab\in E(F)}W(x_a,x_b)d{x}_1\cdots d{x}_k.$$

对潜变量条件化并利用边的条件独立性，立即得到

$$\boxed{{\displaystyle t(F,W)=\mathbb{P}(F\subseteq G(k,W)).}}$$

右侧的事件只要求 $F$ 的边出现，并不要求 $F$ 的非边保持为非边。若要求诱导子图恰等于 $F$，则概率是

$$\mathbb{P}(G(k,W)=F)={\int }_{[0,1{]}^k}\prod _{ab\in E(F)}W(x_a,x_b)\prod _{ab\notin E(F),a<b}(1-W(x_a,x_b))d\mathbf{x}.$$

这一区分不可省略：同态密度对应“包含指定边”的矩，而诱导子图概率还要用 inclusion–exclusion（容斥）恢复非边信息。

1.3 抽样定理：生成的图回到原 graphon

定理（$W$-随机图抽样）　对每个 graphon $W$，当 $n\to \mathrm{\infty }$ 时，$G(n,W)$ 几乎必然收敛到 $W$ 所代表的 graphon 等价类。特别地，对每个有限简单图 $F$，

$$t(F,G(n,W))⟶t(F,W)\text{a.s.},$$

并且在截割距离的商空间中

$${\delta }_{◻}(W_{G(n,W)},W)⟶0\text{a.s.}$$

这里 $W_{G(n,W)}$ 是随机图的经验 step graphon。

证明架构。 对固定 $F$，把单射同态密度写成所有顶点单射对应指标的平均。两个指标只要使用不交的顶点集合便独立；有交的有序对只占全部有序对的 $O_F(1/n)$。这先给出方差趋零。进一步用 bounded differences / Azuma–Hoeffding 型集中不等式可得可求和的尾概率，于是对每个固定 $F$ 得到几乎必然收敛；有限图类型可数，所以可同时对全部 $F$ 成立。最后由 graphon 空间中“全部同态密度收敛”与截割距离收敛的等价性，得到第二个结论。昨日的 counting lemma 负责连续方向，逆向识别则使用 graphon 空间的紧致性与 inverse counting 机制。

1.4 从随机图反推 graphon：表示定理

称无限简单随机图 $H$ 顶点可交换，若其邻接阵对每个有限顶点置换联合可交换。

定理（Aldous–Hoover；图论形式见 Diaconis–Janson）　每个顶点可交换的无限简单随机图律都是 $G(\mathrm{\infty },W)$ 律的混合：存在取值于 graphon 等价类空间的随机元素 $\mathbf{W}$，使得在给定 $\mathbf{W}$ 后，$H$ 具有 $G(\mathrm{\infty },\mathbf{W})$ 的条件分布。混合测度在 graphon 的弱同构商空间上唯一。

一般 Aldous–Hoover 表示可写成

$$A_{ij}=f({\xi }_{\varnothing },{\xi }_i,{\xi }_j,{\xi }_{ij}),$$

其中各层随机变量独立且均匀，$f$ 对中间两个变量对称。给定全局变量 ${\xi }_{\varnothing }$ 后，把边层随机性条件平均掉，就得到一个随机 graphon；全局变量正是“在不同 graphon 成分之间混合”的来源。

以下三个条件刻画不再需要全局混合的情形：

1. 该可交换律是所有可交换图律凸集的极点；
2. 不交顶点集上的有限诱导子图彼此独立（dissociated）；
3. 表示中的 graphon 等价类可以取为确定的。

于是，确定 graphon 并不对应一个确定无限图，而对应一个极端的可交换随机图律。

1.5 可识别的不是坐标，而是概率律

若 $\varphi :[0,1]\to [0,1]$ 保测，则

$$W^{\varphi }(x,y)=W(\varphi (x),\varphi (y))$$

与 $W$ 产生相同的抽样律。更一般地，对 graphon $U,W$，下列条件等价：

• 对每个有限简单图 $F$，$t(F,U)=t(F,W)$；
• 对每个 $n$，$G(n,U)$ 与 $G(n,W)$ 同分布；
• $G(\mathrm{\infty },U)$ 与 $G(\mathrm{\infty },W)$ 同分布；
• ${\delta }_{◻}(U,W)=0$。

因此 graphon 的自然参数不是某张固定“像素图”，而是弱同构 (weak isomorphism) 等价类。统计上若只观察一张大型随机图，所能一致估计的也正是这个等价类，而不是潜变量坐标本身。

现代延伸。 该对应把稠密图极限、非参数随机图模型和可交换阵理论接在一起：graphon estimation 研究从单个 $G(n,W)$ 恢复 $W$ 的等价类；交换性给出模型的对称性来源；截割距离则给出与有限子图抽样相容的损失函数。

2. 固定模板习题 (Template Exercise)

题目

设 $F$ 是顶点集 $[k]$ 上的固定简单图，$G(n,W)$ 按第 1 节构造。对每个单射 $\varphi :[k]\hookrightarrow [n]$，令

$$X_{\varphi }=\prod _{ab\in E(F)}{A}_{\varphi (a)\varphi (b)},$$

并定义单射同态密度估计量

$${\hat{t}}_n=\frac{1}{(n{)}_k}\sum _{\varphi :[k]\hookrightarrow [n]}{X}_{\varphi },(n{)}_k=n(n-1)\cdots (n-k+1).$$

证明：

1. $\mathbb{E}{\hat{t}}_n=t(F,W)$；
2. $\mathrm{Var}({\hat{t}}_n)\le k^2/n$；
3. 因而 ${\hat{t}}_n\to t(F,W)$ 依概率收敛。

模板识别

信号是“许多同分布指标的平均，但指标并非全部独立”。不要逐项计算复杂协方差；先按两份局部结构的支撑是否重叠分类。不交支撑给零协方差，误差只来自占比很小的重叠对。这是随机图计数、U-statistics 和局部依赖变量中反复出现的二阶矩模板。

分级提示

1. 固定 $\varphi$，先对潜变量 $(U_{\varphi (1)},\dots ,U_{\varphi (k)})$ 条件化。
2. 若 $\mathrm{im}\varphi \cap \mathrm{im}\psi =\varnothing$，检查 $X_{\varphi }$ 与 $X_{\psi }$ 实际依赖哪些 $U_i$ 与 ${\xi }_{ij}$。
3. 固定 $\varphi$。对交点在 $\varphi (a)=\psi (b)$ 的可能性作 union bound；每个 $(a,b)$ 固定后，$\psi$ 的其余 $k-1$ 个像至多有 $(n-1{)}_{k-1}$ 种。
4. 用 $|\mathrm{Cov}(X_{\varphi },X_{\psi })|\le 1$，再应用 Chebyshev 不等式。

3. 大家之言 (Mathematician in Their Own Words)

语境。 2026 年 5 月 3 日，计算机科学家 Richard Lipton 在个人理论计算机科学博客 Gödel’s Lost Letter and P=NP 的短文 “A Question” 中，叙述了一个因邮件排序方式而产生的“消息丢失”假象。问题由换一个观察顺序立即解决；他随后把这件小事转向数学问题的表述方式：

“Does this mean that sometimes we all have a bad view of a problem? Can we need some cool insight to see how a problem can be solved?”

中译。 “这是否意味着，有时我们所有人看待问题的视角都不对？我们是否需要某种巧妙洞见，才能看见问题应当怎样解决？”

这段话的数学内容不在“灵光一现”四字，而在先诊断表示是否携带了偶然坐标。同一个邮箱按日期或发件人排序，会呈现完全不同的表象；同一个 graphon 经保测重标号，也会呈现完全不同的像素图。若把坐标图像误当成对象，就会把排序假象当成结构差异。

今天的可交换律给出一种系统性的“换视角”：不问潜变量标签是什么，而问所有有限抽样事件的概率是否相同。若相同，就把两个表示放进同一个弱同构类。洞见由此落实为可检验准则：找出问题中真正应当保持不变的量，再对偶然坐标取商。

4. 反例与边界 (Counterexample & Boundary)

稀疏 Erdős–Rényi 图在稠密 graphon 拓扑中塌缩

固定 $c>0$，令

$$G_n\sim G(n,c/n).$$

逐项检查：

1. 它确实稀疏。 每条边出现概率为 $c/n$，所以

$$\mathbb{E}|E(G_n)|=(\genfrac{}{}{0ex}{}{n}{2})\frac{c}{n}\sim \frac{c}{2}n.$$

边数是一阶量 $O(n)$，而不是稠密理论中的 $\mathrm{\Theta }(n^2)$。

2. 稠密截割距离看不见这些边。 对经验 graphon $W_{G_n}$，

$$\parallel W_{G_n}{\parallel }_{◻}\le \parallel W_{G_n}{\parallel }_1=\frac{2|E(G_n)|}{n^2}.$$

右侧依概率趋于 $0$，故 $W_{G_n}$ 在稠密 graphon 空间中趋于零 graphon。

3. 所有含边的固定图密度也消失。 若 $F$ 至少含一条边，则“随机映射是 $F$-同态”必然要求某一指定边映成 $G_n$ 的边，因此

$$0\le t(F,G_n)\le \frac{2|E(G_n)|}{n^2}\stackrel{\mathbb{P}}{\to }0.$$

4. 但图并不等同于空图。 一个固定顶点的期望度为 $(n-1)c/n\to c$；其有限半径局部结构保留非平凡的 Poisson 分枝信息。零 graphon 却把这些 $O(n)$ 条边全部压没。

暴露出的边界很精确：graphon 的归一化把 $n^2$ 当作边的自然尺度，所以它适合稠密图；把“每个稀疏图序列也有能保留度分布的普通 graphon 极限”当作邻近命题是错误的。

交换性也显示同一障碍。若一个无限简单随机图在所有顶点置换下可交换，并且几乎处处局部有限，那么它必须几乎必然为空图。直观上，固定一条边的边际概率若为正，前 $n$ 个顶点中的期望边数便是 $\mathrm{\Theta }(n^2)$；更严格地，对固定顶点观察其邻接指标的可交换序列并应用 de Finetti，可见非零混合参数会产生无穷多个邻点。要描述非平凡稀疏网络，必须改变尺度、观察窗口或对称性，而不能只把稠密 graphon 中的数值机械地调小。

5. 今日一问与数学地图 (Question & Map)

设 $U,W$ 为两个 graphon，并假设

$$t(F,U)=t(F,W)$$

对每个有限连通简单图 $F$ 都成立。仅知道连通测试图是否已经足以推出 $G(\mathrm{\infty },U)$ 与 $G(\mathrm{\infty },W)$ 同分布，进而推出 ${\delta }_{◻}(U,W)=0$？

请尝试明确补出两座桥：

1. 如何从连通图密度恢复任意不连通图密度？
2. 如何从“指定边全部出现”的概率恢复“某个诱导子图恰好出现”的概率？

方向提示。 第一座桥应寻找不交并下的乘法结构；第二座桥应在缺失边集合上使用容斥。不要直接援引完整的 graphon 唯一性定理，先说明有限维分布为何已经被确定。

数学地图如下：

$$\text{条件概率与乘法性}⟶\text{graphon 同态密度}⟶\text{可交换图的有限维分布}⟶\text{Aldous--Hoover 表示与弱同构}⟶\text{graphon estimation}.$$

边界方向则是

$$\text{稠密顶点交换性}⇢\text{稀疏性障碍}⟶\{\text{graphex},\text{edge exchangeability},\text{local weak convergence}\}.$$

附录 A：习题完整解答 (Full Solution)

展开完整解答

这里使用的可复用模板是：重叠对方差法 (overlap-pair variance method)。

固定单射 $\varphi :[k]\hookrightarrow [n]$。由第 1 节的条件独立构造，

$$\mathbb{E}{X}_{\varphi }={\int }_{[0,1{]}^k}\prod _{ab\in E(F)}W(x_a,x_b)d\mathbf{x}=t(F,W).$$

所有单射的期望相同，而单射总数为 $(n{)}_k$，故

$$\mathbb{E}{\hat{t}}_n=\frac{1}{(n{)}_k}\sum _{\varphi }\mathbb{E}{X}_{\varphi }=t(F,W).$$

再计算方差：

$$\mathrm{Var}({\hat{t}}_n)=\frac{1}{(n{)}_k^2}\sum _{\varphi ,\psi }\mathrm{Cov}(X_{\varphi },X_{\psi }).$$

若 $\mathrm{im}\varphi \cap \mathrm{im}\psi =\varnothing$，则 $X_{\varphi }$ 与 $X_{\psi }$ 分别只依赖两组不交的顶点潜变量及其内部边随机变量。这两组基础随机变量独立，所以

$$\mathrm{Cov}(X_{\varphi },X_{\psi })=0.$$

只需计数像集相交的有序对。固定 $\varphi$。若 $\mathrm{im}\varphi \cap \mathrm{im}\psi \ne \varnothing$，则存在 $a,b\in [k]$ 使 $\varphi (a)=\psi (b)$。固定 $(a,b)$ 后，$\psi (b)$ 已定，其余 $k-1$ 个像至多有 $(n-1{)}_{k-1}$ 种选择。因此由 union bound，给定 $\varphi$ 后至多有

$$k^2(n-1{)}_{k-1}$$

个这样的 $\psi$。由于 $0\le X_{\varphi },X_{\psi }\le 1$，有

$$|\mathrm{Cov}(X_{\varphi },X_{\psi })|\le 1.$$

于是

$$\begin{array}{rl}\mathrm{Var}({\hat{t}}_n)& \le \frac{(n{)}_k{k}^2(n-1{)}_{k-1}}{(n{)}_k^2}\\ & =\frac{k^2}{n},\end{array}$$

其中用了 $(n{)}_k=n(n-1{)}_{k-1}$。最后，对任意 $\epsilon >0$，Chebyshev 不等式给出

$$\mathbb{P}(|{\hat{t}}_n-t(F,W)|>\epsilon )\le \frac{k^2}{n{\epsilon }^2}⟶0.$$

故 ${\hat{t}}_n\to t(F,W)$ 依概率收敛。

模板的核心并不是 graphon 的特殊公式，而是：局部统计量取平均时，不交支撑项独立；若重叠项只占 $O(1/n)$，二阶矩便足以给出集中。

资料与来源 (Sources)

1. Persi Diaconis and Svante Janson, “Graph Limits and Exchangeable Random Graphs,” Rendiconti di Matematica e delle sue Applicazioni 28 (2008), 33–61；arXiv:0712.2749。本文第 5–7 节给出可交换无限图、graph limit、极端律与 graphon 非唯一性的对应。摘要页：https://arxiv.org/abs/0712.2749；全文：https://arxiv.org/pdf/0712.2749。
2. László Lovász, Large Networks and Graph Limits, American Mathematical Society, Colloquium Publications 60, 2012。第 10–11 章系统处理 $W$-随机图、抽样集中、同态密度与截割距离。作者公开稿：https://www.cs.elte.hu/~lovasz/bookxx/hombook-almost.final.pdf；AMS 书目信息与索引：https://www.ams.org/books/coll/060/coll060-endmatter.pdf。
3. Richard J. Lipton, “A Question,” Gödel’s Lost Letter and P=NP, 3 May 2026。第 3 节引文逐字核对自作者博客原文：https://rjlipton.com/2026/05/03/a-question/。