几率方法

在数学中，几率方法是一个非构造性的证明方法。几率方法由艾狄胥·帕尔发扬光大，主要在组合数学中用于证明具有某性质的数学物件的存在性。几率方法证明如果以某种方式随机抽取物件，那有大于 0 的几率抽到给定性质的物件，进而推论这样的物件存在。虽然证明利用到几率，但最终结论是确定性的。

几率方法在数学的其他分支也被广泛利用，像是数论、线性代数、实分析、电脑科学和信息论。

## 引言

如果一群数学物件的集合都不满足某性质，那么从这个集合随机选出的物件满足该性质的几率为零。从逆否命题可知，如果从集合随机选出的物件满足该性质的几率大于零，则这个集合的某个物件必然满足该性质。

同样地，我们可以透过证明满足性质的几率小于一，来证明存在不满足某条件的物件。

计算某随机变数的期望值也是几率方法中的常见手法。一个随机变数有非零的几率大于等于期望值，因此可以证明这样子的物件存在。进一步来说，如果可以证明此随机变数有非零的几率小于期望值，那就可以证明这个随机变数也有非零的几率大于期望值。

几率方法常常需要使用马可夫不等式、切尔诺夫不等式和 Lovász Local Lemma 等数学工具。

## 应用几率方法的例子

虽然在艾狄胥之前就有利用几率方法的证明（像是 Szele (1943) 用几率方法证明了存在有很多哈密顿环的竞赛图），许多利用几率方法的有名证明是艾狄胥给出的，像是以下的两个例子。

### 范例一

艾狄胥（1947）透过几率方法给出了一个拉姆齐数 $R(r, r)$ 的下界。$R(r, r)$ 为最小的正整数 $n$，使得把大于等于 $n$ 个点的完全图每条边染上红色或蓝色后，必定存在边全为红色或蓝色的完全图 $K_n$。

我们想要证明存在足够小的 $n$，使得在把完全图 $K_n$ 的边染上红色或蓝色后，不存在同色的完全图 $K_r$，这会使得 $R(r, r) > n$。

证明的方法为把图上每条边以 $1/2$ 的几率染上红色、$1/2$ 的几率染上蓝色。我们可以用以下方法计算同色子图 $K_r$ 出现次数的期望值。

考虑任意大小为 $r$ 的点集 $S_r$。我们定义 $X(S_r)$：如果连接 $S_r$ 中两点的所有边颜色都相同，则 $X(S_r) = 1$，否则 $X(S_r) = 0$。定义 $X$ 是所有可能 $S_r$ 的 $X(S_r)$ 总和，可以注意到 $X$ 会是此图中同颜色 $K_r$ 的数量。对于任意一个点集 $S_r^i$，$X(S_r^i)$ 的期望值就是 ${r \choose 2}$ 条边颜色相同的几率（全为蓝色或全为红色）：

$$E[X(S_r^i)] = 2 \cdot 2^{-{r \choose 2}}$$

对任意 ${n \choose r}$ 个点集来说，$E[X(S_r^i)]$ 都相同。又因为期望值的可加性，$X$ 的期望值就是

$$E[X] = \sum\limits_{i = 1}^{n \choose r} E[X(S_r^i)] = {n \choose r}2^{1-{r \choose 2}}.$$

如果 $E[X]$ 小于 $1$，那么就存在一个边着色的方法使得图中边同色的 $K_r$ 子图数量小于 $1$，也就是子图数量为 $0$。因此，如果

$$E[X(S_r)] = {n \choose r}2^{1-{r \choose 2}} < 1 \Rightarrow {n \choose r} < 2^{{r \choose 2} - 1}$$

那必然存在边着色的方法使得图中没有同色的 $K_r$ 子图。

根据拉姆齐数的定义，只要正整数 $n, r$ 满足上式，那就代表 $R(r, r) > n$。这代表 $R(r, r)$ 会随 $r$ 呈指数性成长。

因为证明是非构造性的，找出一种涂色方法非常困难，是个未解问题。

### 范例二

艾狄胥（1959）（详见参考文献）回答了图论中的下列问题：给定正整数 $g$ 跟 $k$，是否存在一张图的着色数至少为 $k$，但只存在长度至少 $g$ 的环？

透过几率方法，我们可以证明这样的图对任意 $g, k$ 皆存在。我们选择一个足够大的 $n$，并考虑 $n$ 个点的随机图 $G$。我们让 中的每条边都有 $p = n^{\frac{1}{g} - 1}$ 的几率存在。我们可以证明以下两个性质。

性质 1. 有超过 $\frac{1}{2}$ 的几率，使得 $G$ 中最多只有 个长度小于 $g$ 的环。

证明. 令 X 为长度小于 $g$ 的环的个数。对于正整数 $i$，完全图 $K_n$ 中有

$$\frac{n!}{2\cdot i \cdot (n-i)!} \le \frac{n^i}{2}$$

个长度恰好为 $i$ 的环。每个这样的环在 $G$ 的出现几率为 pi。根据马可夫不等式。

$$\Pr \left (X> \tfrac{n}{2} \right )\le \frac{2}{n} E[X] \le \frac{1}{n} \sum_{i=3}^{g-1} p^i n^i = \frac{1}{n} \sum_{i=3}^{g-1} n^{\frac{i}{g}} \le \frac{g}{n} n^{\frac{g-1}{g}} = gn^{-\frac{1}{g}} = o(1).$$

因此，对于足够大的 $n$，性质 1 有大于 $\frac{1}{2}$ 的几率为真。

性质 2. G 不存在大小为 $\lceil \tfrac{n}{2k} \rceil$ 的独立集。

证明. 令 $Y$ 为 $G$ 中最大独立集的大小。当 $y = \left \lceil \frac{n}{2k} \right \rceil\!.$ 时，我们有

$$\Pr (Y\ge y) \le {n \choose y}(1-p)^{\frac{y(y-1)}{2}} \le n^y e^{-\frac{py(y-1)}{2}} = e^{- \frac{y}{2} \cdot (py -2\ln n - p)} = o(1)$$

因此，对于足够大的 $n$，性质 2 有大于 $\frac{1}{2}$ 的几率为真。

因为性质 1 跟 2 对足够大的 $n$ 都有大于 $\frac{1}{2}$ 成立，这两个性质不能是互斥的。因此，存在一张图 $G$ 使这两个性质皆成立。

根据性质 1，只要从 $G$ 移除最多 $\frac{n}{2}$ 个点，我们就可以得到一张新的图 $G'$，它有 $n'\geq n/2$ 个点，而且只存在长度至少 $g$ 的环。这个新图 $G'$ 仍然没有大小 $\left \lceil \frac{n}{2k}\right\rceil \leq \left \lceil \frac{n'}{k}\right\rceil$ 的独立集，至少要被分成 $k$ 个独立集，所以 $G'$ 的着色数至少为 $k$。

## 参见

- 互动式证明系统
- 拉斯维加斯算法
- Incompressibility method
- Method of conditional probabilities
- 随机图

## 延伸阅读

- Probabilistic Methods in Combinatorics, MIT OpenCourseWare

## 参考文献

- Alon, Noga; Spencer, Joel H. (2000). The probabilistic method (2ed). New York: Wiley-Interscience. .
- J. Matoušek, J. Vondrak. The Probabilistic Method. Lecture notes.
- Alon, N and Krivelevich, M (2006). Extremal and Probabilistic Combinatorics
- Elishakoff I., Probabilistic Methods in the Theory of Structures: Random Strength of Materials, Random Vibration, and Buckling, World Scientific, Singapore, , 2017
- Elishakoff I., Lin Y.K. and Zhu L.P., Probabilistic and Convex Modeling of Acoustically Excited Structures, Elsevier Science Publishers, Amsterdam, 1994, VIII + pp. 296; 0 444 81624 0