07 概率与随机算法

本章对应考试中的：R1 近似取大值（2011期末，15 分）、R2 指纹法测字符串相等（样题1/试卷1/试卷3）、简答 Q3（伪多项式算法、Monte Carlo→Las Vegas、子集和）、简答 Q4（Las Vegas 与 Monte Carlo 区别）、选择题第 6～8 题，以及判断题 29～31（在 11_判断选择填空专项与高频陷阱.md 速记）。

---

核心考点

概率算法（probabilistic / randomized algorithm）：在计算过程中随机地做某些选择（比如随机选一个数、随机选一个枢轴），借助随机性来降低复杂度或简化问题。

本章要能：说清四类概率算法的区别（尤其 Monte Carlo 与 Las Vegas，年年考）；会做概率计算题（R1、R2，核心是"独立事件的概率相乘"）；答伪多项式算法的概念（Q3）。

---

从零开始的前置知识

四类概率算法

这是判断题、选择题、简答题的核心，必须分清。

1. 数值概率算法（numerical probabilistic algorithm）：用随机采样求数值问题的近似解，采样越多、解越精确。例：向一个正方形里随机投点，用"落在内切圆里的点的比例"估算 $\pi$。它得到的是近似值，不是精确解。

2. 蒙特卡罗算法（Monte Carlo algorithm）：总能给出一个解，但这个解可能是错的，而且一般无法判断对错。多运行几次可以降低出错的概率。例：素数测试（费马测试）——它说"是素数"时可能其实是合数。

3. 拉斯维加斯算法（Las Vegas algorithm）：不一定能给出解（有时会"失败、不给答案"），但只要给出解，就一定是正确的。多运行几次可以提高"成功给出解"的概率。

4. 舍伍德算法（Sherwood algorithm）：总能给出正确解，它用随机化来消除算法性能对特定输入的依赖（即消除最坏情况总落在某些特定输入上的现象）。例：随机化快速排序——随机选枢轴，使"最坏情况 $O(n^2)$"不再固定对应"已排好序的输入"。注意它不改变平均复杂度，只是打散最坏情况。

Monte Carlo 与 Las Vegas 的对比（高频）

	Monte Carlo（蒙特卡罗）	Las Vegas（拉斯维加斯）
会不会给出解	总能给出解	不一定给出解
给出的解对不对	可能错	一定对
一句话	有解但可能错	解必对但可能没有

判断题陷阱（详见 11）：把 Monte Carlo 的性质安到 Las Vegas 头上、或反过来，是经典错误项。记牢上表两行即可。

概率计算的基本工具：独立事件相乘

如果若干次随机操作是相互独立的（一次的结果不影响另一次），那么"它们同时发生"的概率等于各自概率相乘。例如一次操作失败的概率是 $0.95$，那么 $k$ 次相互独立的操作全部失败的概率是 ${0.95}^k$。R1、R2 两道计算题都靠这一条。

伪多项式算法

输入规模有两种数法：一种按"输入里有几个数"或"数值大小 $L$"，另一种按"输入写成二进制要多少位"。一个数值 $L$ 写成二进制只要约 ${\log }_{2}L$ 位，所以"数值大小"和"输入位数"是指数关系。

伪多项式算法（pseudo-polynomial algorithm）：运行时间是关于输入中数值大小 $L$ 的多项式，而不是关于输入长度（二进制位数） 的多项式。因为位数 $\approx {\log }_{2}L$，所以关于 $L$ 是多项式、关于位数却是指数。例：背包/子集和的动态规划算法，时间约 $O(nW)$（$W$ 是容量数值），是伪多项式的。

---

答题模板

概率算法题三步：
① 写出算法（通常很短：随机取若干个 → 输出某个统计量）。
② 分析"单次随机操作"出错/失败的概率 p。
③ 用独立性：k 次都出错/失败的概率 = p^k；
   于是"输出正确"的概率 = 1 - p^k（或按题意列不等式解出 k）。

---

逐题精解

R1 近似取大值（2011期末，15 分）

原题：在互不相等的 1000 个数中，任意找出最大的那 50 个数中的一个。设计一个简单概率算法，写出伪代码，并分析输出正确结果的概率。

算法：随机取出 $k$ 个数，输出其中的最大值 $M$。

RandPickTop(A, k):
    从 A 中随机取 k 个数
    M ← 这 k 个数里的最大值
    return M

正确性分析：

• "最大的 50 个数"之外有 $1000-50=950$ 个数。单次随机抽到的数落在这 950 个之中（即不属于前 50）的概率是 ${\displaystyle \frac{950}{1000}}=0.95$。
• 取 $k$ 个数是相互独立的，$k$ 次全部落在前 50 之外（即输出的最大值 $M$ 不属于前 50、答案错）的概率是 ${0.95}^k$。
• 所以输出正确（$M$ 属于最大的 50 个）的概率是

$$P_{\text{正确}}=1-(0.95{)}^k.$$

怎么套用：题目若要求正确率达到某值，就解不等式。例如要 $P_{\text{正确}}\ge 0.99$，即 ${0.95}^k\le 0.01$，解得 $k\ge 90$ 左右（${0.95}^{90}\approx 0.01$），取 $k=90$。

---

R2 指纹法测字符串相等（样题1/试卷1/试卷3）

原题：测字符串相等的概率算法用指纹函数 $I_p(x)=I(x)modp$，$I(x)$ 是比特串 $x$ 的十进制整数表示。已知：$x,y$ 长度均为 $n$、$p$ 是随机选取的小于 $2n^2$ 的素数时，$I_p(x)=I_p(y)$ 但 $x\ne y$ 的概率 $p_f\le 1/n$。又 ${\log }_{2}10\approx 3.32$。问：测两个十万位比特串的相等性，需随机产生并传送几次指纹，可使假匹配概率低于 ${10}^{-30}$？总共传送多少比特？

前置：什么是指纹与假匹配。 直接比较两个超长串很费传输。指纹（fingerprint） 是把长串 $x$ 用 $I_p(x)=I(x)modp$ 压成一个小数（$x$ 的整数值对素数 $p$ 取余数）。比较指纹比比较原串省得多。假匹配（false match）：两个串其实不相等（$x\ne y$），但指纹却恰好相等，导致误判"相等"。题目已告诉我们单次假匹配概率 $p_f\le 1/n$。

求需要几次指纹：

• $n={10}^5$（十万位），单次假匹配概率 $p_f\le {\displaystyle \frac{1}{n}}={10}^{-5}$。
• 送 $k$ 次相互独立的指纹（用不同的随机素数 $p$），只有 $k$ 次全部碰巧相等才会造成假匹配，概率 $\le {\left({\displaystyle \frac{1}{n}}\right)}^k={10}^{-5k}$。
• 要求假匹配概率低于 ${10}^{-30}$：

$${10}^{-5k}<{10}^{-30}⟹5k>30⟹k>6⟹\boxed{{\displaystyle k=7}}.$$

（若题意按"$\le {10}^{-30}$"理解，则 $k=6$ 即可。因为"低于"是严格小于，这里取 $k=7$。）

求总共传送多少比特：每个指纹是一个小于 $2n^2=2\times {10}^{10}$ 的数，它写成二进制的位数为

$$\lceil {\log }_2(2n^2)\rceil =1+2{\log }_{2}n=1+2\times 5\times 3.32\approx 35\text{比特}.$$

（解释：${\log }_2(2n^2)={\log }_{2}2+2{\log }_{2}n=1+2{\log }_{2}n$；而 $n={10}^5$ 所以 ${\log }_{2}n=5{\log }_{2}10\approx 5\times 3.32=16.6$，故 $1+2\times 16.6\approx 34.2$，向上取整 35。）

所以总共传送约

$$k\times 35\approx 7\times 35=245\text{比特}(\text{若取 }k=6\text{ 则约 }210\text{ 比特}).$$

---

简答 Q3：伪多项式算法、Monte Carlo→Las Vegas、子集和

原题：何谓伪多项式算法？如何将一个 Monte Carlo 算法转化为 Las Vegas 算法？以子集和问题为例说明伪多项式时间算法和 FPAS 可以有的关系。

答案：

• 伪多项式算法：运行时间是关于输入数值大小 $L$（输入里的最大数值）的多项式，而不是关于输入长度（二进制位数） 的多项式。由于位数约为 ${\log }_{2}L$，所以它关于 $L$ 是多项式、关于位数是指数。
• Monte Carlo → Las Vegas 的转化：Monte Carlo 每次都给解但可能错；Las Vegas 给的解必对但可能不给解。做法是在 Monte Carlo 算法后面附加一个验证算法：若验证它给出的解是正确的，就输出该解；若不正确，就不输出（即"不给解"）。这样就把"可能给错解"的 Monte Carlo 变成了"要么给对解、要么不给解"的 Las Vegas。（前提是解的正确性能被有效验证。）
• 子集和：子集和问题有一个伪多项式时间的动态规划算法（时间是关于目标数值的多项式）；据此可以构造它的完全多项式近似方案（FPTAS / FPAS）（近似算法详见 08_下界_近似算法与性能比.md）。

---

简答 Q4：Las Vegas 与 Monte Carlo 的区别（2011期末/试卷4）

原题：简述拉斯维加斯算法和蒙特卡洛算法的主要区别。

答案：前者（Las Vegas）不一定总能给出解，但给出的解一定正确；后者（Monte Carlo）总能给出解，但给出的解可能错误。

---

选择题第 6～8 题

• 第 6 题：以下算法中适合求问题近似解的是（B 蒙特卡罗算法）。（数值概率算法求数值近似，蒙特卡罗适合判定型近似解。按本题参考答案选 B。）
• 第 7 题：（B 蒙特卡罗算法）能求得解，但无法有效判定解的正确性。（这正是 Monte Carlo 的特征：总给解、但可能错且难验证。）
• 第 8 题：素数测试方法所用的数学原理是（A 费尔马小定理）。

前置：费马小定理。 费马小定理（Fermat's little theorem）：若 $p$ 是素数，且整数 $a$ 不被 $p$ 整除，则

$$a^{p-1}\equiv 1(\mathrm{mod}p).$$

含义：$a^{p-1}$ 除以 $p$ 余 1。素数测试（费马测试，一种 Monte Carlo 算法）就是反过来用它：随机取 $a$，若 $a^{n-1}\not\equiv 1(\mathrm{mod}n)$，则 $n$ 一定不是素数；若 $\equiv 1$，则 $n$ "很可能"是素数（但可能错，所以是 Monte Carlo）。

---

高频陷阱 / 易错点小结

1. Monte Carlo 与 Las Vegas 别搞反：MC 总给解但可能错；LV 解必对但可能不给。判断题 31"Monte Carlo 有时不给解但给出就对"是错的（那是 LV 的性质）。
2. 概率计算靠独立相乘：$k$ 次独立失败的概率是 $p^k$，正确率 $=1-p^k$。
3. 指纹位数：$\lceil {\log }_2(2n^2)\rceil =1+2{\log }_{2}n$，别忘了那个 $+1$ 和系数 2。
4. "低于"是严格小于：R2 取 $k=7$（${10}^{-35}<{10}^{-30}$），而非 $k=6$（恰等于）。
5. 伪多项式的"伪"在于：它对数值大小是多项式，对输入位数是指数；不要说成"它是多项式算法"。
6. 舍伍德不改变平均复杂度，只消除最坏情况对特定输入的依赖（与"能把平均复杂度降得更低"无关，见判断题 15）。

---

自测清单

• [ ] 说出四类概率算法（数值/蒙特卡罗/拉斯维加斯/舍伍德）各自特征与一个例子。
• [ ] 默写 Monte Carlo 与 Las Vegas 的区别（两行表）。
• [ ] 写出 R1 的算法与正确率公式 $1-(0.95{)}^k$，并解出 $P\ge 0.99$ 时 $k\approx 90$。
• [ ] 做出 R2：得 $k=7$ 次、每个指纹约 35 比特、共约 245 比特。
• [ ] 解释伪多项式算法，并说明 Monte Carlo 怎么加验证变成 Las Vegas。
• [ ] 答出选择 6～8（B、B、A）与费马小定理。