Vince Jiang

CSCI3160 / 辅导 · 本站更新

CSCI3160 T02 递归与拒绝采样练习

课程：CSCI3160 Design and Analysis of Algorithms 本讲：T02 递归与拒绝采样练习 · 原件 T02-三种基本技巧-未核-隐藏.pdf（本地课件） p.1–18 定位：把公平随机比特、常数成功概率和按比例缩小串起来。 承接：L01 递归、重试与几何级数

p.1–3：均匀分布不能用随意取模替代【新】

p.1 标题，p.2 回顾递归、重复至成功、几何级数。p.3 只允许RANDOM(1,128)，要均匀输出1至100，期望常数时间。若取模100，1至28会有两个原像，其他只有一个，因此不均匀。

p.4–5：拒绝采样

p.4 “Output z if it is in [1, 100].”

取z，若z≤100接受，否则重新取。每轮成功100/128，期望轮数128/100=1.28，讲义用“至多2次”的粗界。对任意合法j，最终输出概率为

∑r=0∞(28/128)r(1/128)=1/100. \sum_{r=0}^{\infty}(28/128)^r(1/128)=1/100.

因此同时证明均匀性与期望时间，而不是只证明会终止。

补充：输出事件可以按第一次成功轮数拆开。 输出某个固定 j∈{1,…,100} 有互斥情形：第一轮直接抽 j；第一轮拒绝、第二轮抽 j；前两轮拒绝、第三轮抽 j；依此类推。它们概率分别为 1/1281/128、(28/128)/128(28/128)/128、(28/128)2/128(28/128)^2/128。求和而不是相乘，是因为只需其中一种情形发生。所有 j 的这一列完全相同，最后又必以概率 1 接受，故各占 1/100。

自测：保留拒绝值并将 101–128 减 100，为什么错误？

此时 1–28 每个有两个原像，例如 1 来自 1 或 101，概率 2/128；29–100 每个只有一个原像，概率 1/128。接受条件依结果类别改变时，均匀原随机数不保证均匀输出。拒绝采样的关键正是只保留每个合法输出同样数量的原像。

p.6–8：公平比特生成二的幂大小区间

p.6 只允许RANDOM(0,1)，目标1至n。p.7 当n=2^k，每个公平比特选择上半或下半，连续k次确定一个位置。p.8 递推T(n)=T(n/2)+O(1)，深度log₂n。每个结果对应恰一个k位序列、概率2^−k，所以均匀。

数字是我为演示取的，讲义没给：n=8，抽到比特1,0,1对应零基整数5，输出6。若n=5仍简单把两半各以1/2选，大小2和3的分区会导致单点概率不同。

不用隐含子问题的可执行写法如下；每轮 b 必须调用 RANDOM(0,1)。

UniformPowerOfTwo(m):
  若 m=1：返回 1
  b = RANDOM(0,1)
  返回 UniformPowerOfTwo(m/2) + b*(m/2)

当 b=0 返回前半，当 b=1 加偏移到后半；两半同样大小，每个结果概率都是 (1/2)/(m/2)=1/m。其基例时间为 O(1)。

p.9：先补到二的幂，再拒绝

找最小m=2^k≥n，因此m<2n。均匀生成1至m，超过n则拒绝，每轮成功n/m>1/2，期望少于2轮，每轮O(log n)。例如n=5、m=8，接受概率5/8，期望8/5轮，每轮3比特；所有1至5输出概率相同。n=1直接返回1，避免对数零值叙述的问题。

p.10–12：给一个好 pivot，就能做线性选择

p.10 假设黑盒能确定性线性求中位数，问任意k选择。p.11 按中位数分区，保留含目标的半边并调整秩；p.12 递推T(n)≤T(n/2)+O(n)，展开n+n/2+n/4≤2n，得O(n)。原文的“return S′,k′”是在返回子问题，完整选择算法还要递归到答案。

原页 p.11 的两个子问题是：S1={x∈S:x≤v}S_1=\{x\in S:x\le v\}、S2={x∈S:x>v}S_2=\{x\in S:x>v\}。若 k≤∣S1∣k\le|S_1|，递归 (S1,k)(S_1,k)；否则递归 (S2,k−∣S1∣)(S_2,k-|S_1|)。取低中位数、元素互异并设 n≤2 直接处理，可保证规模严格下降；分析中 ceil(n/2) 的取整不改变几何级数结论。

处理重复值的稳妥补充：划分为小于、等于、大于pivot三段。若k落在相等段直接返回pivot，否则只递归严格小于或大于段。即使全相等也会结束；直接用“≤”且无额外处理可能不缩小。

p.13：只要固定比例严格小于一

黑盒改成4n/5分位，最坏保留约4n/5；总工作n+(4/5)n+…≤5n。99n/100同理，总和≤100n，仍是O(n)，常数显著更大。取整导致小n时可能无缩小，所以小规模直接处理；比例随n趋近1时不能再无条件称线性。

p.14–15：做两次常数缩小

p.14 希望一次降到至多n/2；p.15 连续使用两次至多2n/3的子问题构造，剩余至多4n/9<n/2，总期望工作O(n)+O(2n/3)=O(n)。要保留目标秩的更新，不是随意连续删除两块元素。

p.16–18：两个 pivot 的端点要核对

p.16 在前中四分位区间拒绝采样p1，p.17 在后中四分位区间采样p2，根据目标秩选择左、中、右区间，p.18 用常数成功率论证期望线性。

原页选择区间明确为 r1=rank(p1)∈[n/4,n/2]r_1=rank(p_1)\in[n/4,n/2]、r2=rank(p2)∈[n/2,3n/4]r_2=rank(p_2)\in[n/2,3n/4]。秩可以扫描 S、数不大于 pivot 的元素求得，单次 O(n)；两次拒绝采样各有至少 1/4 的成功率，所以找两个合格 pivot 的总期望仍为 O(n)，并非假设能免费知道秩。

原文存在两个边界问题：保留“≥p2”时新秩应为k−rank(p2)+1；当rank(p2)=n/2时，这个包含端点的尾段大小是n/2+1，不能称至多n/2。可修正为遇k等于任一pivot秩直接返回pivot；否则保留严格<p1、严格在两pivot间、严格>p2三段，第三段的新秩为k−rank(p2)，各段至多n/2（讲义此处假定n是4的倍数且值互异）。

数字是我为演示取的，讲义没给：n=8，rank(p1)=2、rank(p2)=4，目标k=6，应保留秩5至8并把目标改为2；若错误保留秩4至8而仍写2，会返回原秩5。采样闭区间包含端点时成功概率至少1/4，所以期望至多4轮；原文“4 repeats”是方便的上界，未必精确等号。

本辅导只承接主课的递归、随机选择和几何级数，不把这些新练习登记为讲义已讲条目。

本讲核心考点

  • （C 级 通识）拒绝采样同时证明均匀性与期望轮数。
  • （C 级 通识）常数比例缩小的几何求和。
  • （C 级 通识）秩从1计数时，包含或排除pivot影响新k和规模。

附录

本讲所需过程已在正文展开。

来源与证据

  • 本次逐页复核：2026-10-13，依据上述本地课件；保留已发布深化内容，页码指 PDF 物理页。历史考试演练保留其原有出处，本次不将旧记录冒充重新阅卷。

  • 原件：T02-三种基本技巧-未核-隐藏.pdf（本地课件）；页码均为 PDF 页号。

  • 版本记录（2026-09-17）：当时从教师官网下载并逐字节核对，与本地原件一致；此日期不是本次重新联网核验。原始学期未核，不据网页学期补猜。

  • 发布状态（2026-09-17 核验时）：官网链接所在行隐藏，当时按预习参考处理；不据此推断后续发布或考试范围。

  • 既有考试证据记录（2026-09-17）：当时读取了教师官网、Midterm-2021T1-题目.pdf、Midterm-2021T1-题解.pdf、Review-Quiz-2020T2-题目.pdf、Review-Quiz-2020T2-题解.pdf、Quiz-01-2025T1-题解.pdf、Midterm-A-2025T1-缺题干-解答.pdf、Quiz-02-2025T1-缺题干-解答.pdf、Quiz-03-2025T1-缺题干-解答.pdf、Final-2021T1-题解.pdf、Final-2024T1-缺判断-题目.pdf、Final-2025T1-题目.pdf、Final-2025T1-缺题干-解答.pdf；未识别用途的 PDF：无

  • 缺题干解答卷仅用于核对已取得的题面，不由答案反推题目。