概率方法

概率方法（probabilistic method）是一类证明存在性的办法：先在候选对象上定义一个随机选择过程，再证明所需性质发生的概率严格大于零，于是至少存在一个满足性质的对象。结论可以完全不含随机性；随机性是论证时安排对象的工具。

例如，给一个含 $m$ 条边的有限无向简单图分成两组顶点，总能使至少 $m/2$ 条边跨在两组之间。并不需要先猜出哪一种分组最好。让每个顶点独立抛一次公平硬币，就能先算出跨组边数的平均值，再从平均值推出好分组一定存在。

从平均值推出存在性

对有限概率空间中的实随机变量 $X$，一定有某个正概率取值不小于 $𝔼X$。否则所有可能值都严格小于这个平均值，其加权平均也会严格更小，产生矛盾。若 $X$ 为整数计数，便存在 $X\ge \lceil 𝔼X\rceil$ 的对象。

另一种常用表达是：令 $B$ 为坏事件数，若 $𝔼B<1$，则 $\mathbb{P}(B\ge 1)\le 𝔼B<1$，从而 $\mathbb{P}(B=0)>0$。不等式来自 $B\ge {\mathrm{𝟏}}_{\{B\ge 1\}}$。这里必须是严格小于一；均值等于一不能排除所有对象都恰有一个坏处。

证明正概率只是存在性证明，未必给出高效找到对象的算法。即使成功概率是正数，若小到随规模指数衰减，简单重试也可能很慢。设计随机分布时，应区分“足以证明存在”与“足以有效生成”。

图分割的完整证明

设 $G=(V,E)$ 是有限无向简单图，$|E|=m$。对每个顶点独立选择颜色零或一，各以概率二分之一；相同颜色放在同一组。对边 $e=uv$，定义 $$I_e=\{\begin{array}{cc}1,& u,v\text{颜色不同},\\ 0,& u,v\text{颜色相同}.\end{array}$$ 端点颜色有 $00,01,10,11$ 四种等概率结果，恰两种颜色不同，故 $𝔼I_e=1/2$。跨组边总数为 $X=\sum _{e\in E}{I}_e$，期望的线性性给出 $$𝔼X=\sum _{e\in E}𝔼I_e=\frac{m}{2}.$$ 所以至少存在一个分割，使跨组边不少于 $\lceil m/2\rceil$。

这一步不要求各条边的指示变量相互独立。比如三角形中，三条边不可能同时跨组，边的联合状态有约束；但每条边单独跨组的概率仍为一半，线性相加完全成立。把线性期望误写成必须独立，会无端限制这个方法。

每条边有一半机会跨组。右图是五边形的一种分割，四条实线跨组，一条虚线留在同组；它超过期望 5/2，但不能据此断言每一种分割都如此。

逐步固定随机选择

上面的证明可以变成确定性算法。先固定一个顶点次序。尚未决定的顶点仍视为独立公平随机；决定下一个顶点的颜色时，比较把它放入两组后的条件期望。

设当前顶点已有 $a$ 个已固定的零色邻点、$b$ 个已固定的一色邻点。若它取零色，与这些邻点形成 $b$ 条跨组边；若取一色，则形成 $a$ 条。与未固定邻点的边，条件期望仍各为二分之一，不受本次取色影响。故选择较大者 $max(a,b)$，不会降低条件期望，因为它至少为两种选择平均值 $(a+b)/2$。

逐个固定后，条件期望始终不小于初始的 $m/2$；全部固定时已无剩余随机性，条件期望就等于实际跨组边数。这是条件期望法的一次去随机化。局部选择维护的是全局下界，不保证找到最大割。

对按顺序 $0,1,2,3,4$ 排列的五边形，依次得到颜色 $$0,1,0,1,0.$$ 最后一个顶点已看到各一个零色和一色邻点，两种选择各贡献一条新跨边，平局取零。得到四条跨边。这个结果也达到该五边形的最大值：奇数环不可能每条边都跨组，否则沿环交替着色回到起点会矛盾。

决定颜色时只需比较已固定邻点的两种颜色数。最后一步平局，取任一边均保留不小于初始平均值的保证。

可运行的构造

以下实现接受编号 $0,\dots ,n-1$ 的顶点及无重边、无自环的边表，返回颜色列表和跨组边数。它不修改输入，使用整数计算，不借助随机数。

Python 3

def half_cut(n, edges):
    if type(n) is not int or n < 0:
        raise ValueError("n must be a nonnegative integer")
    adjacency = [[] for _ in range(n)]
    seen = set()
    for u, v in edges:
        if type(u) is not int or type(v) is not int:
            raise TypeError("Vertex labels must be integers")
        if not (0 <= u < n and 0 <= v < n) or u == v:
            raise ValueError("Invalid edge")
        edge = (min(u, v), max(u, v))
        if edge in seen:
            raise ValueError("Duplicate edge")
        seen.add(edge)
        adjacency[u].append(v)
        adjacency[v].append(u)
    color = [-1] * n
    for vertex in range(n):
        zero = sum(color[w] == 0 for w in adjacency[vertex])
        one = sum(color[w] == 1 for w in adjacency[vertex])
        color[vertex] = 1 if zero > one else 0
    cut = sum(color[u] != color[v] for u, v in seen)
    return color, cut


print(half_cut(5, [(0, 1), (1, 2), (2, 3), (3, 4), (4, 0)]))
# ([0, 1, 0, 1, 0], 4)

每条边只在邻接表中出现两次，所以构造和扫描需要 $O(n+m)$ 时间及 $O(n+m)$ 存储；这里按集合查重的平均常数时间模型计。未固定邻点的颜色为 $-1$，不计入零色或一色邻点，因此实现与上述条件期望推导一致。

变式。 对三角形三条边，程序返回 $(0,1,0)$ 和两条跨边。下界为 $\lceil 3/2\rceil =2$，而三个点中总有两个同色，所以两条也是最优值。空图则返回全零着色和零条跨边，结论仍成立。

并集界、二阶矩与边界

有些性质需要同时避开许多坏事件 $A_1,\dots ,A_s$。并集界 $$\mathbb{P}\left(\bigcup _i{A}_i\right)\le \sum _i\mathbb{P}(A_i)$$ 不要求事件独立；若右端严格小于一，就存在避开所有坏事件的对象。证明可逐点比较指示变量：发生至少一个坏事件时，坏事件指示变量之和至少为一，再取期望。

但一个计数 $X$ 的均值很大，并不能保证它经常为正；少数巨大值可能抬高平均。二阶矩方法正是进一步计算 $𝔼X^2$，控制这种情形。概率方法不等于“大量模拟后看见一次成功”：一次模拟可以找到一个经检查有效的构造，而要证明任意规模下存在，仍须给出覆盖所述范围的论证。