CSCI3160 Exercise 1：随机算法与期望分析

课程：CSCI3160 本组：Regular Exercise Set 1，Problem 1–5；题目原件（本地课件） p.1；官方答案（本地课件） p.1–3 定位：理解均匀随机数的构造、期望重复次数、最坏情况上下界，以及随机选择为什么能做到期望线性时间。前后：下一组 Exercise 2：分治与线性合并

这是一份学习解析，不是官方答案的翻译。题意以中文概述，完整英文题面见原件。以下证明补充、例子与勘误均为本解析所作；自取数字会单独注明。页码指 PDF 页码。运行时间沿用课程 RAM 模型：一个字长内的整数运算、比较、数组访问视为常数时间，各次随机调用独立。

Problem 1：把 1–128 的随机源变成 1–100（题目 p.1；答案 p.1）

题意概述。 唯一可用的随机操作均匀返回 1 到 128。要求输出均匀的 1 到 100，期望耗时为常数。

为什么直接取余不对

“让结果落在范围里”和“让每个结果概率相等”是两个要求。若输出 ((z-1) mod 100)+1，结果 1 有两个来源：1 和 101；结果 29 只有来源 29。因此前 28 个数各有概率 $2/128$ ，剩余数各有概率 $1/128$ 。输出合法，却不均匀。

正确做法是拒绝采样：不公平地折叠多余结果会造成偏差，直接丢弃多余结果则不会偏袒任何保留结果。

重复：
    z ← RANDOM(1, 128)
    若 z ≤ 100：返回 z

为什么最终输出是均匀的

固定任意一个目标值 $a\in\{1,\ldots,100\}$ 。一次抽到它的概率是 $1/128$ 。要在第 $t$ 次才输出它，必须先连续拒绝 $t-1$ 次，再抽到 $a$ 。一次拒绝的概率是 $28/128$ ，于是

\begin{aligned} \Pr[\text{output}=a] &=\sum_{t=1}^{\infty}\left(\frac{28}{128}\right)^{t-1}\frac{1}{128}\\ &=\frac{1}{128}\cdot\frac{1}{1-28/128}\\ &=\frac{1}{100}. \end{aligned}

每个 $a$ 得到同一个概率，这才完成均匀性的证明。连续拒绝 $t$ 次的概率随 $t$ 趋向无穷而趋向零，因此算法以概率 1 终止。

为什么期望时间是常数

设 $N$ 为抽样次数，包括最后成功的那一次。成功概率 $p=100/128$ 。第一次抽样必花一次；若失败，剩余任务与一开始完全一样，所以

\begin{aligned} \mathbb{E}[N]&=1+(1-p)\mathbb{E}[N],\\ p\mathbb{E}[N]&=1,\\ \mathbb{E}[N]&=\frac{128}{100}=1.28. \end{aligned}

一次抽样、比较都只需常数时间，故总期望时间是 $O(1)$ 。

官方措辞核对。 答案 p.1 将期望调用次数写成“两次”。精确值是 1.28；“不超过两次”可作为上界，不能当作精确期望。这个差别不影响 $O(1)$ 的结论。

算一遍（自取抽样序列）。 抽到 123，拒绝；再抽到 104，拒绝；再抽到 37，返回 37。这里实际用了 3 次，与期望 1.28 不矛盾：期望是多次独立运行的平均意义，不是单次上限。

易错点。 不要写“最多抽两次”。任意多次失败都有非零概率，所以不存在统一的有限最坏次数上界；本题要求的是期望时间。

Problem 2：仅靠公平硬币生成任意范围的均匀整数（题目 p.1；答案 p.1）

题意概述。 只允许生成均匀的 0 或 1。对正整数 $n$ ，生成均匀的 1 到 $n$ ，期望时间为 $O(\log n)$ 。

第一步：把范围扩大到二的幂

设 $b=\lceil\log_2 n\rceil$ ， $M=2^b$ 。无需调用对数函数：令 $M=1,b=0$ ，不断把 $M$ 翻倍并将 $b$ 加一，直到 $M\ge n$ 。对 $n>1$ ，最小性的关键含义是

\frac{M}{2}<n\le M<2n.

这里 $M$ 是候选范围大小，不是随机结果。选择最小的二次幂保证候选范围不会比目标范围大到两倍或更多。

第二步：用 b 个随机位生成候选数

一个长度为 $b$ 的二进制串对应 0 到 $2^b-1$ 中的唯一整数。每一位独立且公平，所以每个串的概率都是 $2^{-b}=1/M$ 。

若 n = 1：返回 1
M ← 1；b ← 0
当 M < n：
    M ← 2M；b ← b + 1
重复：
    z ← 0
    重复 b 次：
        z ← 2z + RANDOM(0, 1)
    若 z < n：返回 z + 1

z ← 2z + bit 的意思是在当前二进制数右侧再接一位。官方用“把区间反复二分，随机选择左右半区”表达同一构造：每走一步选一位，共走 $b$ 步。

算一遍：n = 5（数字是本解析自取）

此时 $M=8,b=3$ 。八个等概率串依次对应：

随机位	z	候选输出 z+1	处理
000	0	1	接受
001	1	2	接受
010	2	3	接受
011	3	4	接受
100	4	5	接受
101	5	6	拒绝
110	6	7	拒绝
111	7	8	拒绝

一次候选需要 3 次随机调用；期望候选次数为 $8/5$ ；期望随机位数为 $3\cdot8/5=4.8$ 。例如位串 110 被拒绝，下轮 010 则返回 3。

均匀性与时间的完整连接

每轮每个合法值的概率均为 $1/M$ ，而拒绝概率是 $1-n/M$ 。重复到成功后，每个合法值的最终概率是

\frac{1/M}{1-(1-n/M)}=\frac{1}{n}.

每轮接受概率 $p=n/M>1/2$ ，故期望轮数 $1/p=M/n<2$ 。预处理花 $O(\log n)$ ，每轮花 $O(\log n)$ ，从而总期望时间为 $O(\log n)$ 。严格处理 $n=1$ 时，统一写法可以是 $O(1+\log n)$ 。

官方勘误。 答案 p.1 在解释成功概率时写随机结果 $y\ge x/2$ ，这并不总成立，例如抽到 1。所需条件应当是目标范围大小 $n>x/2$ （这里官方的 $x$ 对应本文的 $M$ ）。这来自“最小的不小于 $n$ 的二次幂”，与随机结果大小无关。

易错点。 不能只取 $\lfloor\log_2 n\rfloor$ 位，那样会遗漏一些目标值；也不能将多余结果取模，除非已经证明原范围大小能被 $n$ 整除。期望轮数为常数，不代表生成一轮也只花常数时间。

Problem 3：减法版 GCD 的上下界（题目 p.1；答案 p.1）

题意概述。 输入非负整数 $n\le m$ 。若较小数为 0 就返回较大数，否则把较大数减去较小数，重新排序两个数后递归。证明最坏情况时间上界和下界都是线性的。

算法为什么仍在求最大公约数

这里每次只做一次减法，不是通常使用取余的快速欧几里得算法。对于 $n>0$ ，有

\gcd(n,m)=\gcd(n,m-n).

原因有两个方向：若 $d$ 同时整除 $n,m$ ，它也整除 $m-n$ ；若它整除 $n,m-n$ ，它也整除 $(m-n)+n=m$ 。所以公约数集合不变。交换参数的顺序也不改变公约数集合。最终到达 $(0,d)$ ，最大公约数就是 $d$ 。

上界：选一个每步必下降的量

一个稳妥的势函数是两数之和 $\Phi=n+m$ 。每次非终止调用后，新数对是 $n,m-n$ ，无论之后是否交换，总和都是 $m$ 。因此一次减少恰好 $n\ge1$ 。初始总和不超过 $2m$ ，且始终非负，所以减法步数至多 $2m$ ，再加一次终止调用仍是 $O(m)$ 。每层只做常数次操作，总时间为 $O(m)$ 。

为何不用含糊的“较大数总会下降”。 官方 p.1 用最大值每步下降来证明。但当两数相等，如 $(5,5)\to(0,5)$ ，最大值并未下降；这是进入终止状态的最后一步。可以给原证明补上这个例外，或像上面那样改用两数之和，避免例外。两种修补都保留 $O(m)$ 结论。

下界：找一族真正会慢的输入

固定 $n=1$ 。对任意正整数 $m$ ，数对依次为

(1,m)\to(1,m-1)\to\cdots\to(1,1)\to(0,1).

总共 $m$ 次减法；若包括最初和最后的函数调用，共 $m+1$ 次调用。每次减法至少要常数时间，因此这一族输入需要 $\Omega(m)$ 时间。结合上界，最坏情况为 $\Theta(m)$ 。

算一遍（自取数字）。 $n=1,m=4$ 时调用依次是 $(1,4),(1,3),(1,2),(1,1),(0,1)$ ：4 次减法、5 次调用。最终结果为 1。

量词很重要。 上界要覆盖所有合法输入；最坏情况的下界只需要对每个足够大的 $m$ 找到一个慢输入。不能说每个输入都需要 $\Omega(m)$ ： $(m,m)$ 只用一次减法就结束。还要区分数值大小 $m$ 与编码位数 $\log m$ ，本题以数值作参数，不是说它相对输入位数是线性算法。

Problem 4：均匀抽元素等价于均匀抽秩（题目 p.1；答案 p.2）

题意概述。 120 个互异元素中均匀选一个，求其秩落在闭区间 35 到 78 的概率。

元素互异意味着排序后每个位置恰好对应一个元素。每个元素被抽中的概率均为 $1/120$ ，因此每个秩也均匀；原数组是否已经排序不影响这个概率。

闭区间包含的整数个数是 $78-35+1=44$ ，所以所求为

\frac{44}{120}=\frac{11}{30}\approx0.3667.

为什么加一。 从 35 到 78 有 43 个间隔，但有 44 个位置。若区间只有一个秩，例如 35 到 35，必须算成 1 个而不是 0 个。

易错点。 这里的范围限制的是秩，而不是元素数值。即使数组中的数都在一百万附近，答案也不变。

Problem 5：随机 Quickselect 的期望线性时间（题目 p.1；答案 p.2–3）

题意概述。 在 $n$ 个互异整数中找第 $k$ 小。均匀选择一个枢轴，扫描求秩并划分；若命中目标就返回，否则只递归进入包含目标的一侧。证明期望时间为 $O(n)$ 。

先理解为什么只递归一边，以及 k 如何改变

设枢轴秩为 $r$ ，左边有 $r-1$ 个元素，右边有 $n-r$ 个。

$r=k$ ：枢轴正是所求。
$r>k$ ：目标在左边，左边内部的目标秩仍为 $k$ 。
$r<k$ ：目标在右边；原先排在它前面的左边元素与枢轴合计 $r$ 个被删去，所以新的目标秩为 $k-r$ 。

算一遍（自取数字）。 输入 [9,1,7,3,5]，找第 4 小。若选到 3，它的秩为 2。右边是 [9,7,5]，应找第 $4-2=2$ 小，即 7。若误写成第 4 小，子问题连合法秩范围都超出了。

一层不必先排序：扫描所有元素，统计小于枢轴的个数，再加一就是 $r$ ；同时构造左右子数组，花 $O(n)$ 。算法每次只进入一侧，不能写成快速排序那样两侧都递归。

期望证明的难点是什么

枢轴可能一直选到极端元素，子问题大小依次是 $n-1,n-2,\ldots$ ，最坏时间可达 $\Theta(n^2)$ 。证明期望线性不能假装每次恰好平分，也不能把“平均子问题大小”直接代进一个未经分析的时间函数。

下面用强归纳证明一个对所有数组与所有目标秩都成立的线性期望上界。这也避开了默认时间函数随规模单调的隐含前提。

第一步：按枢轴的每个可能秩分类

设一层扫描和划分代价至多 $an$ ，其中 $a>0$ 是常数。假设所有规模 $s<n$ 的子问题都满足期望时间不超过 $cs$ 。某次选中秩 $r$ 后，真正递归规模不会超过

m_r=\max\{r-1,n-r\}.

若直接命中，则后续代价为零，也满足同样上界。给定已经发生的划分，后续随机调用依然独立；归纳假设适用于那一份具体子数组与目标秩。因此条件期望至多 $cm_r$ 。

每个枢轴秩的概率都是 $1/n$ ，由全期望公式得到

\mathbb{E}[T]\le an+\frac{c}{n}\sum_{r=1}^{n}\max\{r-1,n-r\}.

第二步：精确计算这个平均规模

若 $n=2q$ ，较大侧大小为

2q-1, 2q-2, ..., q, q, ..., 2q-2, 2q-1

每个从 $q$ 到 $2q-1$ 的整数出现两次。因此

\begin{aligned} \frac{1}{n}\sum_{r=1}^{n}m_r &=\frac{2}{2q}\cdot\frac{(q+2q-1)q}{2}\\ &=\frac{3q-1}{2}\\ &=\frac{3n}{4}-\frac12. \end{aligned}

若 $n=2q+1$ ，中间秩对应大小 $q$ ，而 $q+1$ 到 $2q$ 各出现两次。因此

\begin{aligned} \sum_{r=1}^{n}m_r &=q+2\sum_{j=q+1}^{2q}j\\ &=q+q(3q+1)\\ &=3q^2+2q. \end{aligned}

这也不超过 $3n^2/4$ ，因为

\frac{3(2q+1)^2}{4}-(3q^2+2q)=q+\frac34>0.

所以无论奇偶，平均的较大侧大小都不超过 $3n/4$ 。

第三步：选常数，闭合归纳

代回第一步：

\mathbb{E}[T]\le an+\frac{3cn}{4}\le cn

只需 $c\ge4a$ 。再把 $c$ 选得足够大以覆盖 $n=1$ 的常数时间，强归纳完成。结论对每个合法输入及目标秩都成立：期望时间为 $O(n)$ 。

数值核对（自取 n=8）。 八种枢轴秩的较大侧规模是 [7,6,5,4,4,5,6,7]，总和 44，平均 5.5，小于 $3n/4=6$ 。这只是检查求和直觉；一般性由前面的奇偶推导保证。

补充：先条件化，再平均，才不会把随机规模塞进错误位置。 以 n=5、目标 k=4 为自取检验，五个枢轴秩 r=1,2,3,4,5 对应实际后续规模依次4、3、2、0、4。平均为13/5=2.6；证明使用的较大侧上界为4、3、2、3、4，平均16/5=3.2，因此确实保守。命中 r=4 时应立即返回，不会真的递归那一侧的三个元素。归纳只需要对每一种结果分别提供 cs 上界，之后对这些上界加权。

自测：可以写 E[T(子问题大小)]=T(E[子问题大小]) 吗？

一般不可以。自取随机大小S以一半概率为1或3，若成本函数T(s)=s²，则 E[T(S)]=(1+9)/2=5，而 T(E[S])=2²=4。这里是先用每个规模上的线性归纳界 T(s)≤cs，才有 E[T(S)]≤cE[S]；不是直接交换函数与期望。

怎样读官方 p.2–3 的较长推导

官方把求和放宽后设 $t=\lceil k/2\rceil$ ，最终得到

f(k)<(a+c)k+3c-\frac{ck}{4}.

为保证右侧不超过 $ck$ ，需要 $ak+3c\le ck/4$ 。可以让 $ak$ 和 $3c$ 各不超过 $ck/8$ ：前者由 $c\ge8a$ 保证，后者由 $k\ge24$ 保证；小于 24 的有限个规模由扩大常数 $c$ 覆盖。24 是这套放缩得到的技术阈值，不是算法的特殊参数。本文的精确求和减小了放缩损失，因此无需该阈值。

复述检查。 能否解释：随机的是什么，期望对谁取；一层为什么是线性；为什么只有一条递归路径；为什么必须按秩条件化；常数 $c$ 为何可以统一选定。只写“随机枢轴平均平分，所以线性”还没有完成证明。

本讲核心考点

Q1：拒绝采样必须分别证明均匀性与期望代价，题目 p.1。
Q2：公平随机位构造二次幂范围，再以成功概率大于二分之一保证常数期望轮数，题目 p.1。
Q3：最坏情况上界覆盖所有输入，下界用一族慢输入，题目 p.1。
Q4：互异元素与秩的一一对应、闭区间计数，题目 p.1。
Q5：条件期望与强归纳证明随机选择的期望线性界，题目 p.1。

上述是本组练习覆盖点，不表示已经核实出现在某次考试中。

来源与证据

官方题目，p.1；官方答案，p.1–3。下载核验日期：2026-09-30。
2026-09-30 核验时官网可见的 Regular Exercises List 1；源 PDF 未标明学期，不补猜原始学期。
本文补充了均匀性推导、GCD 势函数证明、Quickselect 的精确求和证明，区分了官方简写与精确结论。
考试证据：本次仅核对官方练习与答案，未据此断言考试范围。