4. Graphon 空间的紧致性

定义 4.1. 鞅是一个随机变量的序列 $X_0,X_1,X_2,\dots$, 且对于任意的 $n$, $$\mathbb{E}\left[X_n\mid X_{n-1},X_{n-2},\dots ,X_0\right]=X_{n-1}$$

例 4.2. 令 $X_n$ 表示在公平赌场 $n$ 轮游戏后的余额, 其中每轮收益的预期值为 $0$, 那么 ${\left\{X_n\right\}}_{n>0}$ 是鞅.

定理 4.3 (鞅收敛定理). 任意有界的鞅以概率 1 收敛 (即 a.s. 收敛) .

笔记 4.4. 实际上, 不必要求有界, $L^1$ 有界或一致可积就已经足够, 这两者都可以保证 $\sup \mathbb{E}\left(X_n^{+}\right)<\infty$.

我们将给出一个受投注策略启发的证明思路. 下面的证明省略了一些技术细节, 但对于有概率基础的人来说可以很容易地完善省去的细节.

证明. $[a,b]$ 的 “上交叉” 由区间 $[n,n+t]$ 组成, 其中 $X_n<a$ 且 $X_{n+t}$ 是 $X_n$ 之后第一个满足 $X_{n+t}>a$ 的变量. 参考图 ??, 假设有一个不收敛的有界鞅 $\left\{X_n\right\}$ , 则存在有理数 $0<a<b<1$ 使得 $\left\{X_n\right\}$ 无限次向上穿过区间 $[a,b]$ . 我们将证明该事件发生的概率为 0. (...)“上交叉” 的例子

将 $u_N$ 记作从开始到时间 $N$ 之间的上交叉次数 (从区间下方穿到上方的次数) . 考虑以下投注策略: 在任何时候, 我们持有 0 或 1 的份额. 如果 $X_n<a$, 则买入 1 股并持有, 直到价格 $\left(X_n\right)$ 第一次取值超过 $b$ 卖出. 考虑我们从这种投注策略中的获利? 每个 “上交叉” 我们赚到差价 $b-a$. 考虑我们的初始余额和最终余额之间的差异, 我们的至少获利 $(b-a)u_N-1$ . 另一方面, 可选抽样定理 ¹告诉我们所有 “公平” 的投注策略收益预期为零. 所以$$0=\mathbb{E}\text{ profit }\ge (b-a)\mathbb{E}{u}_N-1$$所以 $\mathbb{E}{u}_N\le \frac{1}{b-a}$. 令 $u_{\infty }={\lim }_{N\to \infty }{u}_N$ 表示 “上交叉” 的总次数. 根据单调收敛定理, 我们有 $\mathbb{E}{u}_{\infty }\le \frac{1}{b-a}$, 因此 $\mathbb{P}\left(u_{\infty }=\infty \right)=0$, 证明完毕.

$\square$

我们现在使用之前介绍的工具来证明 graphon 的主要定理. 所需的工具为弱正则性引理 (定理 3.0.3) 和鞅收敛定理 (定理 4.3) . 我们将首先证明 graphon 的空间是紧致的 (定理 1.23) . 在下一节中, 我们将应用这个结果来依次证明定理 1.22 和定理 1.21. 我们还将看到如何使用紧致性来证明 graphon 的强正则性引理.

回想一下, 如果 ${\delta }_{\square }(W,U)=0$ , ${\tilde{W}}_0$ 是模掉等价关系 $W\sim U$ 的 graphon 空间. 我们可以看到 $\left({\tilde{W}}_0,{\delta }_{\square }\right)$ 是一个度量空间.

定理 4.5 (graphon 空间的紧致性). 度量空间 $\left({\tilde{W}}_0,{\delta }_{\square }\right)$ 是紧致的.

证明. 由于 ${\tilde{W}}_0$ 是一个度量空间, 我们证明序列紧致就足够. 固定一个序列 $W_1,W_2,\dots$ 的 graphon. 我们想证明存在一个子序列在 ${\delta }_{\square }$ 意义下收敛到某个极限 graphon.

对于任意的 $n$, 重复应用弱正则性引理 (定理 3.0.3) , 我们得到一系列划分$${\mathcal{P}}_{n,1},{\mathcal{P}}_{n,2},{\mathcal{P}}_{n,3},\dots$$满足

1.	对于所有的 $n,k$, ${\mathcal{P}}_{n,k+1}$ 是 ${\mathcal{P}}_{n,k}$ 的加细.
2.	$\left|{\mathcal{P}}_{n,k}\right|=m_k$, 其中 $m_k$ 是只关于 $k$ 的函数.
3.	${\Vert W_n-W_{n,k}\Vert }_{\square }\le 1/k$, 其中 $W_{n,k}={\left(W_n\right)}_{{\mathcal{P}}_{n,k}}$

弱正则性引理仅能够保证 $\left|{\mathcal{P}}_{n,k}\right|\le m_k$, 但如果我们允许划分中空集的存在, 那么我们可以保证等号成立.

最初, 每个块是一个任意的可测集. 然而, 对于任意的 $n$, 我们可以对 $W_{n,1}$ 和 ${\mathcal{P}}_{n,1}$ 作用一个保测的双射 $\varphi$, 使得 ${\mathcal{P}}_{n,1}$ 将 $[0,1]$ 划分为多个区间. 对于任意的 $k\ge 2$, 假设 ${\mathcal{P}}_{n,k-1}$ 是 $[0,1]$ 到区间的划分, 我们可以对 $W_{n,k}$ 和 ${\mathcal{P}}_{n,k}$ 作用一个保测的双射, 使得 ${\mathcal{P}}_{n,k}$ 是 $[0,1]$ 到区间的划分, 并且是 ${\mathcal{P}}_{n,k-1}$ 的加细. 通过归纳, 我们得到: 对于任意的 $n,k$, ${\mathcal{P}}_{n,k}$ 是满足 (a) 和 (b) 的划分. 虽然性质 (c) 可能不成立, $W_{n,k}={\left(W_n\right)}_{{\mathcal{P}}_{n,k}}$ 不再成立, 我们仍然有 ${\delta }_{\square }\left(W_n,W_{n,k}\right)\le 1/k$ 对于所有 $n,k$ 成立. 对我们来说这已经足够.

现在, 证明的关键是在可数多步骤中的对角化论证. 从序列 $W_1,W_2,\dots$ 开始, 我们将反复挑选子序列. 在第 $k$ 步中, 我们选择一个子序列 $W_{n_1},W_{n_2},\dots$ 满足:

1.	$i\to \infty$ 时, ${\mathcal{P}}_{n_i,k}$ 中各部分的端点都分别收敛.
2.	$i\to \infty$ 时, $W_{n_i,k}$ 几乎处处收敛于某个 graphon $U_k$ .

因为每个划分 ${\mathcal{P}}_{n,k}$ 正好有 $m_k$ 个部分, 并且每个部分的长度都在 $[0,1]$ 中, 所以满足 (1) 的子序列一定存在. 我们考虑满足 (1) 的子序列 ${\left(W_{a_i}\right)}_{i=1}^{\infty }$, 每个 $W_{a_i,k}$ 可以很自然地通过函数 $f_{a_i,k}:{\left[m_k\right]}^2\to [0,1]$ 来确定. 此类函数的空间是有界的, 因此 ${\left(f_{a_i}\right)}_{i=1}^{\infty }$ 收敛到 $f:{\left[m_k\right]}^2\to [0,1]$ . 因为 $f$ 对应一个 graphon $U_k$ ($U_k$ 为子序列 ${\left(W_{n_i}\right)}_{i=1}^{\infty }$ 的极限) , 所以 (2) 也是满足的.

我们将子序列重新标记为 $W_1,W_2,\dots$ 并且忽略序列的丢弃项. 相应的分区也重新标记. 不失一般性的, 在步骤 $k$ 中, 我们得到含有 $W_1,\dots ,W_k$ 的子序列. 因此, 步骤 $k=1,2,\dots$ 的最终结果是一个无限长的序列, 它满足: 对于所有 $k$, ${\left(W_{n,k}\right)}_{n=1}^{\infty }$ 几乎处处 (a.e.) 逐点收敛到 $U_k$: $$\begin{array}{lccccll}& W_1& W_2& W_3& \dots & & \\ k=1& W_{1,1}& W_{2,1}& W_{3,1}& \dots & \to U_1& \text{ 逐点 a.e. }\\ k=2& W_{1,2}& W_{2,2}& W_{3,2}& \dots & \to U_2& \text{ 逐点 a.e. }\\ k=3& W_{1,3}& W_{2,3}& W_{3,3}& \dots & \to U_3& \text{ 逐点 a.e. }\end{array}$$类似地, 对于任意 $k$, ${\left({\mathcal{P}}_{n,k}\right)}_{n=1}^{\infty }$ 收敛到区间划分 ${\mathcal{P}}_k$ .

根据性质 (a) , 每个划分 ${\mathcal{P}}_{n,k+1}$ 是 ${\mathcal{P}}_{n,k}$ 的加细, 这意味着 $W_{n,k}={\left(W_{n,k+1}\right)}_{{\mathcal{P}}_{n,k}}$. 令 $n\to \infty$, 我们得到 $U_k={\left(U_{k+1}\right)}_{{\mathcal{P}}_k}$ . 现在每个 $U_k$ 都可以被认为是概率空间 $[0,1{]}^2$ 上的一个随机变量. 从这个角度看, 等式 $U_k={\left(U_{k+1}\right)}_{{\mathcal{P}}_k}$ 暗示序列 $U_1,U_2，\dots$ 是鞅.

每个 $U_k$ 的范围都在 $[0,1]$ 中, 因此鞅是有界的. 由鞅收敛定理 (定理 4.3) , 存在一个 graphon $U$, 使得当 $k\to \infty$ 时 $U_k\stackrel{\text{逐点 a.e.}}{⟶}U$ .

回想一下, 我们的目标是找到在 ${\delta }_{\square }$ 意义下的收敛子序列 $W_1,W_2,\dots$ . 我们已经通过上述对角化论证找到一个子序列, 并且该子序列在 ${\delta }_{\square }$ 意义下收敛到 $U$. 也就是说, 我们想证明当 $n\to \infty$ 时 $\delta {\left(W_n,U\right)}_{\square }\to 0$. 下面我们将通过将 “3-epsilons ” 操作来证明这一点.

对任意 $ϵ>0$, 根据 Lebesgue 控制收敛定理, 存在 $k>3/ϵ$ 使得 ${\Vert U-U_k\Vert }_1<ϵ/3$. 由于 $W_{n,k}\stackrel{\text{逐点 a.e.}}{⟶}{U}_k$ (应用控制收敛定理) , 存在 $n_0\in \mathbb{N}$ 使得 ${\Vert U_k-W_{n,k}\Vert }_1<ϵ/3$ 对所有的 $n>n_0$ 成立. 最后, 因为我们选择 $k>3/ϵ$, 所以我们有 $\delta {\left(W_n,W_{n,k}\right)}_{\square }<ϵ/3$ 对于所有 $n$ 成立. 综上, $$\begin{array}{rl}\delta {\left(U,W_n\right)}_{\square }& \le \delta {\left(U,U_k\right)}_{\square }+\delta {\left(U_k,W_{n,k}\right)}_{\square }+\delta {\left(W_{n,k},W_n\right)}_{\square }\\ & \le {\Vert U-U_k\Vert }_1+{\Vert U_k-W_{n,k}\Vert }_1+\delta {\left(W_{n,k},W_n\right)}_{\square }\\ & \le ϵ\end{array}$$第二个不等号是因为对于任意的 graphon $W_1,W_2$ 我们有$$\delta {\left(W_1,W_2\right)}_{\square }\le {\Vert W_1-W_2\Vert }_{\square }\le {\Vert W_1-W_2\Vert }_1$$

$\square$

1.	^ 在特定条件下, 停时的鞅的期望值等于其初始值.