Continuous Trajectory: 从 Independent Set Process 到另类 Giant Component

Independent Set Process

大部分时候，随着一个自然的随机过程的进行，随机变量的变化都很平滑。例如，考虑在 (G(n,p)) 上进行如下的贪心求最大独立集算法：从 1 到 (n) 遍历每个点，能选就选。这里我们假设 (p=d/n)，这样每个点期望度数都是常数 (d)。如果每个点度数真的这么多，只能选 (n/(d+1)) 个点。但这个情况其实很坏：每个点影响的是“它后面的点”，越后面的点的有效度数越小。所以以平均度数描述整个过程并不合理。于是我们想，能不能不用线性函数，而是换一个函数来描述这个过程？为了好描述，把上述算法写成：

记录 (I=varnothing,X) 为全集
每次随机从 (X) 中选一个点 (v)，加入 (I) 并令 (X-{v}-N(v)to X)
直到 (X=varnothing)

记 (X_i) 为 (i) 步后 (|X|) 的值。为了描述 (X_i)，我们猜测存在一个比较好的函数 (x(t))，满足 (X_i/napprox x(i/n))。换句话说，如果 (d) 相同，则即使 (n) 不同，则在看了一定比例的点之后，选出的独立集标记掉的点比例是一样的。如果存在这样的 (x(t))，如何求出它的表达式呢？我们考虑一步（(ito i+1)）时 (X) 的变化，变化量 (E[X_{i+1}-X_imid X_1,dots,X_i]=-1-frac dn(X_i-1))，因为在 (X) 中选出的点期望有 (p(X_i-1)) 个邻居。反映到 (x) 上就是（令 (t:=i/n)）

[nx(t+1/n)-nx(t)approx -1-frac dn(nx(t)-1) ]

忽略低阶项再令 (nto infty)（注意 (x(0)=1)）：

[begin{aligned} n(x(t+1/n)-x(t))approx -1-dx(t)\ to x'(t)=-1-dcdot x(t)\ to x(t)=-frac 1d+frac{d+1}de^{-dt} end{aligned} ]

成功了！可以发现，由于上述随机过程符合“下一步的变化量期望可以被当前的状态描述”，所以这个分析给我们带来了一个微分方程，解出了很好看的结果。为了求 (I) 的大小，我们要求 (x(t)=0)，得 (t=frac{ln (d+1)}{d})。因此我们猜测

Statement 1 w.h.p. 上述过程会选出 ((1+o(1))cdot frac{ln (d+1)}{d}cdot n) 个点。

这比之前的 (n/(d+1)) 大多了。事实上，上述过程是完全合理的，用 (x(t)) 去描述整个过程也没有任何问题。接下来我们证明

Theorem 1 w.h.p. 对于所有 (i=0,1,dots,I_{max}=frac{ln (d+1)}dn-n^{3/4}) 都有 (X_iin x(t)npm e(t)n^{3/5})，其中 (t=i/n)，(e(t)) 是关于 (t) 增大的误差函数（步数越多允许的误差越大）。

如何证明这么一个结论呢？注意到我们分析的是每一步的变化量，这个变化量只和之前的结果有关，我们希望所有步的变化量加起来不要和期望差得太多，这个 setting 其实正好就是鞅的 Azuma-Hoeffding 不等式解决的问题。比如我们要证明上界 w.h.p. (X_ile x(t)n+e(t)n^{3/5})，我们希望最好 (e(t)n^{3/5}) 足够大，把 (x(t)n) 对 (X_i) 近似的误差全部掰回去，使得 (Y_i=X_i-x(t)n-e(t)n^{3/5}) 是一个下鞅，也即 (E[Y_{i+1}mid X_1,dots,X_i]le Y_i)。这样，它 (ge 0) 的概率就可以用 Azuma 不等式控制了。因此，暂时忽略其它细节，现在我们需要计算 (E[Y_{i+1}-Y_imid X_1,dots,X_i])：

[begin{aligned} &E[Y_{i+1}-Y_imid X_1,dots,X_i]\&=E[X_{i+1}-X_imid X_1,dots,X_i]-(x(t+1/n)-x(t))cdot n-(e(t+1/n)-e(t))cdot n^{3/5}\ &=-1-frac dn(X_i-1)-(x'(t)+O(1/n))-(e'(t)n^{-2/5}+o(1/n))\ &le -1-frac dn(x(t)n+e(t)n^{3/5}-1)-x'(t)-e'(t)n^{-2/5}+O(1/n)\ &={color{red}(-1-dx(t)-x'(t))}-(de(t)-e'(t))n^{-2/5}&\ &=(de(t)-e'(t))n^{-2/5} end{aligned} ]

其中把差变成导数用的是中值定理，第三行小于等于用到了 (X_ile x(t)n+e(t)n^{3/5})，(-1) 被吸收到最后的 (O(1/n)) 里去了。注意最后红色的项全消掉了在意料之中，毕竟 (x(t)) 就是这么解出来的。只要 (de(t)-e'(t)<0)，（如果 (X_ile x(t)n+e(t)n^{3/5})），例如取 (e(t)=e^{2dt})，我们就可以说 (Y_i) 是下鞅。

但是这时出现了几个问题：

1. 如果 (X_i=0)，则 (E[X_{i+1}-X_i]) 就不能这么写了。
2. 如果中途 (X_i) 就跑出了区间，导致 (X_ile x(t)n+e(t)n^{3/5}) 不成立了怎么办？此时 (Y_i) 就不是下鞅了。
3. (Y_i) 的变化量完全没有上界，而 Azuma 不等式需要 (Y_i) 变得很小。

第一个问题就是用 (I_{max}) 解决的：容易说明对于 (ile I_{max})，我们定理给出的 (X_i) 取值区间都严格正，所以只要不跑出区间就可以这么写，这就把这个问题归结到了第二个问题。对于后两个问题，我们可以用统一的办法来解决这两个问题：Freezing。注意到

1. 如果 (X_i) 跑出了区间，则 (Y_i) 已经 (>0) 了。
2. (Y_i) w.h.p. 都变得很小（因为 (X_i) 变化量期望是常数，(Y_i) 加的那些变化量就是常数）。

所以我们定义停时 (T) 是第一次 (1) (X_i) 跑出区间或者 (2) 遇到一个度数 (>n^{1/20}) 的点的 (i)。我们新定义 (Z_i=Y_{min(i,T)})，显然 (Z_i) 也是下鞅。而且我们有：

1. 如果中途 (X_i) 跑出了区间，则 (Z_T=Y_i>0)。
2. 如果 (Z_Tle 0)，则要么整个过程都没问题，要么中途因为遇到大度数的点被 freeze 了（这部分概率是 (o(1))）。

所以整个过程都不出问题的概率 (ge 1-o(1)-P(Z_Tge 0))。而 (Z_i) 的变化量是 (O(n^{1/20}))，总共有 (Theta(n)) 步，初值 (Z_0=Y_0=-e(0)n^{3/5}=-Theta(n^{3/5}))，所以

[P(Z_Tge 0)le exp(-n^{6/5}/(2ncdot n^{1/10}))=exp(-Omega(n^{1/10})) ]

证毕。

Giant Component：一种基于 Continuous Trajectory 的做法

事实上，这样“把随机过程投影到连续函数”上的思想可以套用在很多随机过程上，随便写一个“下一步能简单地用上一步描述的过程”基本上都可以（例子：Balls and Bins，(n) 个瓶子，每次随机两个瓶子，把一个球放进球数更少的瓶子里，问 (k) 次操作后应该有几个空瓶子。不妨作为读者的练习题）。接下来我们来看一个很弱的 Giant Component 结论的证明。与几乎所有人第一次学的 Branching Process 版本不同，这个证明用复杂得多的逻辑证明了弱得多的结论。

Theorem 2 考虑下述随机过程：从 (n) 个点空图开始，每次均匀随机选两个点 (xne y)，连边 ((x,y))（为了简单，不忽略重边）。对于常数 (c<1)，连 ((n/2)cdot c) 条边时，w.h.p. 最多存在大小为 (O(n^{1-epsilon})) 的连通块。

这个模型和我们熟知的 (G(n,c/n)) 模型基本是一样的，具体怎么变成一样略。事实上直接对 (kln n) 个点的连通块（上的 BFS）进行 Union Bound 直接就能证明 w.h.p. 最多存在大小为 (O(log n)) 的连通块，但我们的证明从完全不同的角度说明了这件事。对于加了 (i) 条边的图 (G_i)，设 (c_1,c_2,dots,c_k) 为其连通块大小，记 (Y_i=sum_{p=1}^k c_p^2)，我们试图把 (Y_i) 投影到连续函数上。还是令 (t=i/n,Y_iapprox ny(t))（(y(0)=1)），计算期望：

[begin{aligned} E[Y_{i+1}-Y_imid Y_1,dots,Y_i]&=sum_{1le u<vle k}2c_uc_vcdot frac{c_uc_v}{binom n2}\ &=frac{1}{binom n2}left(Y_i^2-sum_{p=1}^k c_p^4right) end{aligned} ]

这里 (sum_{p=1}^k c_p^4) 比较烦人。但如果 (c_p) 都不大（which we know is the case），则这一项是远远没有前面的平方项大的，我们暂时先不管。那就有

[n(y(t+1/n)-y(t))approx 2y(t)^2to y'(t)approx 2y(t)^2to y(t)=frac{1}{1-2t} ]

这个结果还是很振奋人心的，因为它正确指出了 giant component 的 threshold 确实应该在 (t=1/2) 也就是大概 (n/2) 条边的时候。那我们就希望有这么一个 Statement:

Statement 2 w.h.p. 对于所有 (i=0,1,dots,(n/2)cdot c) 其中 (c<1) 都有 (Y_iin y(t)npm e(t)S(n))，其中 (t=i/n)，(e(t)) 是关于 (t) 增大的误差函数（步数越多允许的误差越大），(S(n)=o(n))。

但我们现在很难证明 Statement 2。首先 (Y_i) 的变化量没有上界（我们肯定不能作弊，用别的工具去 bound (c_u) 上界）；其次我们还忽略了低阶项 (sum_p c_p^4)，但如果没有上界，我们根本不知道这一项能不能忽略。因此我们必须在 (Y_i) 的语境下找到一种 bound (c_p) 的方法。这里的想法是：既然我们都知道其实 (c_p) 甚至不到多项式级别，那无论我把 (Y_k) 的指数 2 取到多大，总是差不多可以“忽略低阶项”，而且指数取得很大的话，我们又知道在这个投影成立的情况下 (Y_i=O(n))，所以这就可以 bound 住 (c_p) 了。为了做非常粗糙的估计，我们先取 (Z_i=sum_{p=1}^k c_p^3) 看看情况。注意：由于 (Z_i) 的存在是为了 bound 住 (Y_i) 的 trajectory 服务的，所以我们只需要 (Z_i) 的上界。我们用一样的方法分析 (Z)，令 (Z_iapprox nz(t))，有

[begin{aligned} E[Z_{i+1}-Z_imid Y_1,dots,Y_i]&=sum_{1le u<vle k}(3c_u^2c_v+3c_uc_v^2)cdot frac{c_uc_v}{binom n2}\ &=frac{3}{binom n2}left(Y_iZ_i-sum_{p=1}^k c_p^5right) end{aligned} ]

暂时忽略减掉的东西（这个不会出问题，因为最后我们只要上界），

[n(z(t+1/n)-z(t))approx 6y(t)z(t)to z(t)=frac{1}{(1-2t)^3} ]

很有道理，看来 (Z_i) 在 (i=n/2cdot c) 条边的时候仍然是 (O(n)) 的。接下来我们看看 (Z) 是如何对 (Y) 施加影响的。

• 第一，我们希望用 (Z) 去控制 (Y)，所以实际上我们正在同时考虑以下三个事件：

  1. 对于所有 (i=0,1,dots,(n/2)cdot c) 都有 (Y_ile y(t)n+e(t)S(n))。
  2. 对于所有 (i=0,1,dots,(n/2)cdot c) 都有 (Y_ige y(t)n-e(t)S(n))。
  3. 对于所有 (i=0,1,dots,(n/2)cdot c) 都有 (Z_ile z(t)n+e(t)S(n))。

  （这三个 (e,S) 不一定全相同。）为了利用 freezing 技巧，所以我们需要设 (T) 为第一次发生上述三个事件任意一个出问题的时间，并令 (Y'_i=Y_{min(i,T)},Z'_i=Z_{min(i,T)})。

• 第二，(Z=O(n)) 并不能直接说明 (c_p) 都很小。它只能说明：对于固定的参数 (gamma)，(c_p=Omega(n^{gamma})) 的 (p) 很少，只有 (O(n^{1-3gamma})) 个。这时就引入一个可能看起来很难以理解的 idea：我们直接修改这个随机过程，忽略所有会导致存在 (n^{gamma}) 大小的连通块的边。

换句话说，我们现在考虑的随机过程是这样。固定常数 (gamma)，重复 (ccdot n/2) 次：

1. 随机一条边。
2. 如果加了这条边，这张图上会有大小为 (n^{gamma}) 大小的连通块，则不要加这条边。
3. 否则，加入这条边，并判断如果上述 i ii iii 三个条件有不满足的，立刻 freeze。

接下来我们都在这个随机过程上分析。我们想说明：在这个随机过程上，w.h.p. 三个条件会一直满足。

以 (Y_i) 的下界为例，这是最麻烦的一个。我们先暂时不管“忽略会导致存在 (n^{gamma}) 大小的连通块的边”，令 (Y'_i=Y_i-y(t)n+e(t)S(n))：

[begin{aligned} &E[Y'_{i+1}-Y'_imid Y_1,dots,Y_i]\ &=E[Y_{i+1}-Y_imid Y_1,dots,Y_i]-(y(t+1/n)-y(t))n+(e(t+1/n)-e(t))S(n)\ &=frac{1}{binom n2}left(Y_i^2-sum_{p=1}^k c_p^4right)-y'(t)+e'(t)cdot (S(n)/n)+O(1/n)\ &ge frac 2{n^2}Y_i^2-y'(t)+e'(t)cdot (S(n)/n)+O(n^{-2/3})\ &ge frac 2{n^2}(y(t)n-e(t)S(n))^2-y'(t)+e'(t)cdot (S(n)/n)+O(n^{-2/3})\ &={color{red}(2y(t)^2-y'(t))}+(e'(t)-4e(t)y(t))cdot (S(n)/n)+o(S(n)/n)+O(n^{-2/3}) end{aligned} ]

其中利用 (Z_i=O(n)) 说明了 (sum c_p^4=O(n^{4/3}))。红色部分为 0，所以我们需要 (e'(t)>4e(t)y(t))。这里可以取 (e(t)=frac{1}{(1-2t)^3})，同时为了吸收掉 (O(n^{-2/3})) 需要 (S(n)=w(n^{1/3}))。这样，(Y_i') 就是上鞅了。

我们还剩两件事：

1. 把“忽略会导致存在 (n^{gamma}) 大小的连通块的边” 对 (Y_i) 变化的影响搞清楚。
2. 控制 (Y_i) 单步变化量以便使用 Azuma 不等式。

一步一步来，先看第一件事。设 (overline Y_i) 表示考虑忽略这些边之后的 (Y_i)，我们想看

[begin{aligned} &|E[Y_{i+1}-Y_imid Y_1,dots,Y_i]-E[overline Y_{i+1}-overline Y_imid Y_1,dots,Y_i]|\ end{aligned} ]

如果要忽略选择的这条边，它一定有一个端点在大小至少是 (n^{gamma/2}) 的连通块里，所以上式

[begin{aligned} &le sum_{c_uge n^{gamma}/2}sum_v frac{c_u^2c_v^2}{binom n2}\ &le frac 1{binom n2} cdot Y_icdot sum_{c_uge n^{gamma}/2} c_u^2\ &=O(n^{-gamma}) end{aligned} ]

最后一步是因为 (Z_i=O(n))，所以 (sum_{c_uge n^{gamma}/2} c_u^2=O(n^{1-gamma}))。只要 (S(n)=w(n^{1-gamma}))，(S(n)/n) 就还是主项。

现在忽略了会导致出现大小 (ge n^{gamma}) 连通块的边，再来看第二件事，(Y_i) 每步变化量 (M) 就不超过 (O(n^{2gamma}))。Azuma 不等式给出 (Y_i) 超出下界的概率 (le exp(Omega(S(n)^2/nM^2)))，可以看出，只要 (gamma) 足够小，(S(n)=n^{1-gamma/2})，所有限制就都满足了。于是我们证明了 w.h.p. (Y_i) 不会超出下界。

(Y_i) 的上界和 (Y_i) 的下界唯一区别就是，不需要用 (Z_i) 的上界说明 (sum c_p^4) 确实是低阶项了；(Z_i) 的上界和 (Y_i) 的上界几乎完全一致。这样我们就证明了 w.h.p. 这三个条件会一直一起满足。

我们还剩下最后一个问题：我们直接把所有会带来大连通块的边都忽略了！现在我们要在做完整个随机过程的 (ccdot n/2) 步之后，再把这些边加进来，再证明此时没有 giant component。不过这也是容易的，因为就算不考虑边数要求，把所有不考虑会导致大连通块的边时，已经 (ge n^{gamma}/2) 个点的连通块（显然，没加进来的边一定和这些块相邻）的所有邻边全都加进来，至多也就连上这些连通块总点数的相邻连通块总点数个点。在 (Z_i) 有上界的前提下，总点数是 (O(n^{1-3gamma})times O(n^{gamma}))；每个点邻边个数根据 Chernoff Bound 知道是 (O(log n)) 级别的（注意这并不是作弊，这比另一个做法的 Chernoff Bound 弱得多）；每条邻边连接的小连通块至多 (O(n^{gamma})) 个点，全部乘起来还是 (o(n^{1-gamma/2}))。因此，就算把忽略的边全加上，也不会出现 giant component。证毕。

实战演练

上述做法绕了一大圈证 giant component 的一半确实没什么用。不过这个思想可以直接用到 branching process 黯然失色的问题上，比如稍微改一改 giant component 的 setting，加一点类似之前说的 balls and bins 的博弈元素：我每一次随机两条边，我按照某种策略优先选一条边，这时候什么时候才会出现 giant component？这个做法仍然适用，但是 Branching Process 需要 BFS 每一步具有独立性，就不行了。读者若有兴趣，可阅读 https://www.math.cmu.edu/~af1p/Texfiles/nogiant.pdf