第3章 · 万变中的不变——随机

按图解版第3章重建蒲丰投针、随机游走、大小数据抽样、期望时间、随机准确性、字符串哈希、碰撞风险，以及贪心加随机的可复现实验方法。

学习目标

  • 能解释随机的方法与巧算圆周率——蒲丰投针实验在“第3章 · 万变中的不变——随机”中的适用条件
  • 能围绕“怎样同时记录随机算法的分布、种子、失败概率、期望成本和确定性验证？”运行正常与失败轨迹，定位第一处错误决策
  • 能用“第3章 · 万变中的不变——随机的题面摘要、约束表、输入生成器、算法伪码或代码版本、复杂度推导、正确性理由、最小反例、实际输出与资源统计。”证明“同一生成器状态可重放同一轨迹，随机性只影响已声明的时间或误差边界。”

来源、目录与技术核对边界

“第3章 · 万变中的不变——随机”以天瓏书店详细书目与目录核对段忠杰、顾业鸣著、中国水利水电出版社、ISBN 9787522615059、245 页以及全书 6 章；该页标出版日期 2023 年 6 月 1 日。河南省政府采购书目记录同一 ISBN、题名、作者和出版社，但出版时间写作 2023 年 5 月。日期口径相差一个月，本课程保留差异，不自行断言哪一天是正式首发日。

对“第3章 · 万变中的不变——随机”而言，公开来源只提供书目和详细目录，不含可授权改写的完整正文；本站的解释、推导、代码、交互、练习和答案均为独立教学重写。目录页第 4 章和第 6 章标题存在明显 OCR 或排版异常，站内按上下文规范化标题，但在清单中披露校正。

“第3章 · 万变中的不变——随机”的技术事实另以Vitter 蓄水池抽样原始论文与 WG21 C++ 随机库草案复核：技术来源 1、技术来源 2。来源用于检查概念、语言语义或历史算法边界，不把现代竞赛规则静默投射成 2023 年原书的逐字内容。

围绕“怎样同时记录随机算法的分布、种子、失败概率、期望成本和确定性验证？”，先预测正确轨迹，再只注入“只记录最终随机结果，不保存生成器、种子、调用顺序和失败判据”。若不能用最小反例定位第一处错误决策，就拒绝当前算法解释。

从“随机结果不能复现”开始

先预测：若程序使用随机数后偶尔出错，最重要的日志是什么？不是“它随机坏了”，而是随机数生成器、seed、调用顺序、输入与失败判据。计算机里的随机通常由确定性状态机生成；只要这些条件相同，失败就能逐步重放。

让同一程序拥有两个看似矛盾的能力：不同seed探索不同轨迹，同一seed精确复现同一轨迹。

3.1 随机的方法

随机的方法不是统一模板。它可能用于：

  • 估计量：随机抽样近似总体性质；
  • 选择顺序：随机pivot避免固定输入模式触发坏路径；
  • 搜索空间探索：随机起点越过局部最优；
  • 指纹压缩：随机或混合hash把大对象映射到小范围；
  • 对抗输入解耦：让输入难以预知算法内部选择。

设计时要明确随机变量、概率空间和成功事件。若“随机选择”没有分布定义，期望与失败概率都无从计算。

3.1.1 巧算圆周率——蒲丰投针实验

巧算圆周率——蒲丰投针实验把针随机投到间距为tt的平行线上。针长L≤tL\le t，针中心到最近线的距离均匀分布在[0,t/2][0,t/2]，针与平行线夹角均匀分布在[0,π][0,\pi]。相交概率为：

p=2Lπtp=\frac{2L}{\pi t}

若做NN次独立实验、相交CC次，用p^=C/N\hat p=C/N估计：

π^=2LNtC\hat\pi=\frac{2LN}{tC}

这是：增加样本通常缩小误差，但不会让某次有限实验自动变成数学证明。若C=0C=0，估计式甚至无定义，代码必须处理小样本边界。

3.1.2 迷宫的十字路口

迷宫的十字路口展示随机游走：每到分岔点随机选择一个可走方向。它不需要维护完整搜索树，能用极少状态持续探索；但可能反复回到旧位置，命中出口时间具有长尾。

若图是有限、连通、无吸收陷阱，随机游走最终访问目标的概率可以很高，甚至为1；这不意味着有小的确定性步数上界。加入visited偏好、回退栈或启发式后，它逐渐接近随机化搜索，而不再是纯随机游走。

std::mt19937_64 rng(seed);
std::uniform_int_distribution<int> pick(0, degree - 1);
int next = neighbors[pick(rng)];

必须使用与目标范围匹配的均匀分布，而不是简单rng() % degree；当生成器范围不能被degree整除时，取模会产生轻微偏差。

3.1.3 大数据与小数据

大数据与小数据的矛盾是：总体太大，无法全部保存或反复扫描，但仍想得到无偏样本。蓄水池抽样维护kk个位置。第ii个元素到来时，以k/ik/i概率进入reservoir，并均匀替换一个旧元素。

template<class T, class URBG>
std::vector<T> reservoir_sample(Stream<T>& stream, std::size_t k, URBG& rng) {
    std::vector<T> sample;
    T value;
    std::size_t seen = 0;
    while (stream.read(value)) {
        ++seen;
        if (sample.size() < k) sample.push_back(value);
        else {
            std::uniform_int_distribution<std::size_t> pick(0, seen - 1);
            const std::size_t j = pick(rng);
            if (j < k) sample[j] = value;
        }
    }
    return sample;
}

对任意早期元素，它先进入reservoir，之后每一步留下的概率连乘：

ki∏j=i+1n(1−1j)=kn\frac{k}{i}\prod_{j=i+1}^{n}\left(1-\frac1j\right)=\frac{k}{n}

因此最终每个元素具有相同保留概率。这个证明比“看起来抽得挺散”更重要。

3.2 随机的时间复杂度

必须说明期望对谁求。随机快速排序通常固定任意输入排列，只对随机pivot求期望；这与假设输入本身均匀随机不同。

若一次尝试以概率qq成功，失败后独立重试，则尝试次数XX服从几何分布：

E[X]=1q\mathbb E[X]=\frac1q

期望是长期平均，单次仍可能连续失败。工程上要同时给出重试上限、尾部概率和fallback。

3.2.1 多米诺骨牌上的等差数列

多米诺骨牌上的等差数列可用来观察“随机探测发现结构”的速度。等差数列相邻差为dd；随机抽到若干项后，观测差值的最大公因数可能是dd，也可能是dd的倍数，因为样本可能只落在每隔两项、三项的位置。

随机样本能快速提出候选dd，但还需用边界、成员关系或额外样本验证。算法可以把昂贵的完整搜索替换为“随机提出候选 + 确定性检查”；只要检查严格，随机性影响时间，不影响最终正确性。

3.2.2 小算的生活费

小算的生活费说明抽样平均的直觉：从许多天的支出中随机抽取若干天，用样本均值估计总体均值。异常支出会增大方差，小样本尤其不稳定。

若样本独立同分布、方差为σ2\sigma^2，样本均值方差为：

Var⁡(Xˉ)=σ2k\operatorname{Var}(\bar X)=\frac{\sigma^2}{k}

标准误差只按1/k1/\sqrt{k}下降；想把典型误差减半，样本量约要增至四倍。若抽样有周期偏差，例如只抽工作日，增加样本也不能修复偏差。

3.3 随机的准确性

随机的准确性要区分三类合同：

  1. 答案始终正确，时间随机：Las Vegas风格，例如随机pivot但完整验证的选择算法。
  2. 时间有界，答案小概率错误：Monte Carlo风格，例如只比较有限位指纹。
  3. 近似优化：始终返回可行解，但最优差距由概率或经验描述。

概率相乘还要求独立性或可证明的条件概率上界。仅把seed依次加1，不保证不同运行在统计上独立；较差的生成器可能让相邻seed产生相关前缀。需要严格失败界时，应选有明确质量保证的生成器、从足够宽的seed空间独立取样，并把“每次失败概率至多多少”的前提写进结论。

3.3.1 从字符串到数字——哈希算法

从字符串到数字——哈希算法依靠把任意长度字符串映射到固定整数范围。多项式rolling hash可写成：

hi+1=(Bhi+ci) mod Mh_{i+1}=(Bh_i+c_i)\bmod M 
std::uint64_t hash_string(std::string_view text) {
    std::uint64_t hash = 0;
    for (unsigned char ch : text) {
        hash = hash * 131 + ch;
    }
    return hash;
}

无符号整数溢出按2642^{64}取模定义，适合作为快速fingerprint；但hash相等不能证明字符串相等。哈希表还必须通过开放寻址或链地址处理碰撞。

3.3.2 哈希算法的隐患

哈希算法的隐患首先是碰撞不可消除：从无限字符串集合映射到有限整数集合，由抽屉原理必有不同字符串同hash。若把hash相等当作对象相等，程序会得到概率错误。

在理想均匀模型中，把mm个键放入MM个桶，至少一次碰撞的近似概率为：

1−exp⁡(−m(m−1)2M)1-\exp\left(-\frac{m(m-1)}{2M}\right)

这就是生日效应。即使mm远小于MM，碰撞也可能已经明显。面对不可信输入，还要考虑攻击者构造大量碰撞使哈希表退化；可随机化seed、使用抗攻击hash，或改用有最坏上界的树结构。

3.4 贪心+随机——探索最优解

贪心+随机——探索最优解常采用随机多起点：每次随机打乱候选或扰动评分，再按贪心规则构造可行解，最后保留目标值最好的结果。

能降低一次坏起点的影响，却不能证明全局最优。若单次命中目标区域概率至少为pp，独立重启rr次全部失败概率为：

(1−p)r(1-p)^r

问题在于pp通常未知。因此输出必须明确是“当前最好可行解”，并用上界、下界或小规模oracle评估差距。

Solution best;
for (int run = 0; run < restarts; ++run) {
    auto order = candidates;
    std::shuffle(order.begin(), order.end(), rng);
    Solution current = greedy_construct(order);
    verify_feasible(current);
    if (!best.valid() || current.score() > best.score()) best = current;
}

正式节点与算法证据

  • ：第 1 个正式节点要能回到“同一生成器状态可重放同一轨迹，随机性只影响已声明的时间或误差边界。”，并给出成功输入与失败反例。
  • ：第 2 个正式节点要能回到“同一生成器状态可重放同一轨迹，随机性只影响已声明的时间或误差边界。”，并给出成功输入与失败反例。
  • ：第 3 个正式节点要能回到“同一生成器状态可重放同一轨迹，随机性只影响已声明的时间或误差边界。”，并给出成功输入与失败反例。
  • ：第 4 个正式节点要能回到“同一生成器状态可重放同一轨迹，随机性只影响已声明的时间或误差边界。”，并给出成功输入与失败反例。
  • ：第 5 个正式节点要能回到“同一生成器状态可重放同一轨迹，随机性只影响已声明的时间或误差边界。”，并给出成功输入与失败反例。
  • ：第 6 个正式节点要能回到“同一生成器状态可重放同一轨迹，随机性只影响已声明的时间或误差边界。”，并给出成功输入与失败反例。
  • ：第 7 个正式节点要能回到“同一生成器状态可重放同一轨迹，随机性只影响已声明的时间或误差边界。”，并给出成功输入与失败反例。
  • ：第 8 个正式节点要能回到“同一生成器状态可重放同一轨迹，随机性只影响已声明的时间或误差边界。”，并给出成功输入与失败反例。
  • ：第 9 个正式节点要能回到“同一生成器状态可重放同一轨迹，随机性只影响已声明的时间或误差边界。”，并给出成功输入与失败反例。
  • ：第 10 个正式节点要能回到“同一生成器状态可重放同一轨迹，随机性只影响已声明的时间或误差边界。”，并给出成功输入与失败反例。
  • ：第 11 个正式节点要能回到“同一生成器状态可重放同一轨迹，随机性只影响已声明的时间或误差边界。”，并给出成功输入与失败反例。

约束到算法决策

先固定问题，再比较策略

怎样同时记录随机算法的分布、种子、失败概率、期望成本和确定性验证？

问题前提

写出随机的方法的输入域、输出合同、规模和数值范围。

算法决策

只比较能够完整覆盖巧算圆周率——蒲丰投针实验前提的候选策略。

验收证据

保存第3章 · 万变中的不变——随机的最小、边界与对抗输入。

正式节点：随机的方法、巧算圆周率——蒲丰投针实验、迷宫的十字路口、大数据与小数据、随机的时间复杂度、多米诺骨牌上的等差数列、小算的生活费、随机的准确性、从字符串到数字——哈希算法、哈希算法的隐患、贪心+随机——探索最优解

执行轨迹

用同一输入比较正常与失败路径

  1. 01形式化随机的方法的输入与输出
  2. 02选择巧算圆周率——蒲丰投针实验并声明不变量
  3. 03执行迷宫的十字路口并记录成本
  4. 04用贪心+随机——探索最优解核对正确性、终止和资源

必须保持：同一生成器状态可重放同一轨迹，随机性只影响已声明的时间或误差边界。

反例与证据包

让错误策略在最小输入上失败

当前基线满足：同一生成器状态可重放同一轨迹，随机性只影响已声明的时间或误差边界。

小结

本章从随机的方法出发，借蒲丰投针实验理解概率估计，借迷宫的十字路口理解随机游走，借大数据与小数据理解均匀抽样。多米诺骨牌上的等差数列与小算的生活费进一步区分了快速提出结构和统计估计的不确定性。

随机的时间复杂度回答“平均要做多少工作”，随机的准确性回答“答案错的概率与验证边界是什么”。字符串哈希说明从字符串到数字的效率，也暴露哈希算法的隐患。最后，贪心加随机通过多起点扩展探索，但最优性仍需证据，随机不能替代证明。

练习与答案

练习

  1. 问题 1：建立算法合同。 回答“怎样同时记录随机算法的分布、种子、失败概率、期望成本和确定性验证？”，并写出约束、决策、不变量和验收结果。
  1. 问题 2：构造最小反例。 只采用“只记录最终随机结果，不保存生成器、种子、调用顺序和失败判据”，怎样确认失败来自算法而不是实现噪声？
  1. 问题 3：覆盖正式节点。 用一个证据包串联随机的方法、巧算圆周率——蒲丰投针实验、迷宫的十字路口、大数据与小数据、随机的时间复杂度、多米诺骨牌上的等差数列、小算的生活费、随机的准确性、从字符串到数字——哈希算法、哈希算法的隐患、贪心+随机——探索最优解，并解释为什么复杂度更低不必然在给定规模上更快。

名词解释

名词解释

本章出现的专业名词，用大白话再讲一遍。

随机的方法

“第3章 · 万变中的不变——随机”中的正式节点；需要同时说明前提、决策、正确性理由与成本边界。

巧算圆周率——蒲丰投针实验

“第3章 · 万变中的不变——随机”中的正式节点；需要同时说明前提、决策、正确性理由与成本边界。

迷宫的十字路口

“第3章 · 万变中的不变——随机”中的正式节点；需要同时说明前提、决策、正确性理由与成本边界。

大数据与小数据

“第3章 · 万变中的不变——随机”中的正式节点；需要同时说明前提、决策、正确性理由与成本边界。

随机的时间复杂度

“第3章 · 万变中的不变——随机”中的正式节点；需要同时说明前提、决策、正确性理由与成本边界。

多米诺骨牌上的等差数列

“第3章 · 万变中的不变——随机”中的正式节点；需要同时说明前提、决策、正确性理由与成本边界。

小算的生活费

“第3章 · 万变中的不变——随机”中的正式节点；需要同时说明前提、决策、正确性理由与成本边界。

随机的准确性

“第3章 · 万变中的不变——随机”中的正式节点；需要同时说明前提、决策、正确性理由与成本边界。

从字符串到数字——哈希算法

“第3章 · 万变中的不变——随机”中的正式节点；需要同时说明前提、决策、正确性理由与成本边界。

哈希算法的隐患

“第3章 · 万变中的不变——随机”中的正式节点；需要同时说明前提、决策、正确性理由与成本边界。

贪心+随机——探索最优解

“第3章 · 万变中的不变——随机”中的正式节点；需要同时说明前提、决策、正确性理由与成本边界。

资料与写作方式声明

本章以《深入浅出算法竞赛（图解版）》的权威目录界定学习范围，并结合正文列出的技术资料独立重写；不宣称复现原书正文，也不沿用原作表述。

原作版权归作者与出版社所有；本站原创教学结构与表述仅供学习交流。

讨论

评论区加载中…