随机化算法是在计算过程中使用随机选择的算法。对于固定输入，不同的随机选择可能产生不同的执行路径、运行时间或输出。因此，其性能与正确性保证以概率来表述，而不只是依靠确定性的界限。随机化可以简化算法设计、降低计算成本，或高效地给出近似答案。它并不一定会导致错误结果：有些随机化算法总能返回正确答案，另一些则允许出现概率受控的错误。(cs.yale.edu)
计算模型与分析
随机化算法可以表示为 (A(x,r))，其中 (x) 是输入，(r) 是一个随机比特序列。一旦二者都确定，计算过程就是确定性的。标准理论模型提供相互独立、无偏的比特；算法可以用这些比特从均匀分布中采样，或构造其他随机选择。概率图灵机为计算复杂性理论中的这一模型提供了形式化描述。(cs.yale.edu)
随机化分析与平均情况分析的关键区别，在于随机性出现的位置。平均情况分析假设输入服从某种分布；随机化分析则可以对每个固定输入都成立，其中概率仅针对算法内部的随机选择计算。因此，一个难以处理的输入未必会使期望性能保证失效。这一区别也要求明确说明：输入的确定是否独立于这些随机选择。(theory.cs.princeton.edu)
运行时间成为一个随机变量 (T(x,r))。期望时间界关注其期望值，例如 (\mathbb{E}_r[T(x,r)])。高概率界则限制执行时间超过某个指定阈值的概率。这是两种不同的保证：仅有较小的期望值，并不能排除偶尔出现很长的执行时间。分析可以分别对运行时间、输出错误和近似质量给出界限。(cs.yale.edu)
拉斯维加斯算法与蒙特卡洛算法
拉斯维加斯算法从不返回错误答案。其运行时间可能取决于随机选择，效率通常用期望值衡量。一种等价的表述是：允许一次有时间上限的尝试报告可识别的失败，然后再进行尝试。随机化排序就是一个常见例子：随机性改变的是计算过程中完成的工作量，而不是结果必须满足的排序要求。(cs.yale.edu)
蒙特卡洛算法保证运行时间有界，但可能以某个指定概率返回错误答案。单侧错误意味着只有一类答案可能出错；双侧错误则允许两类答案都出错。其名称与更广义的蒙特卡洛方法有关，后者通过随机采样来估计各种量。(cs.yale.edu)
这些类别描述的是算法所提供的保证，而不是严格固定的实现类型。可以在达到时间限制后停止一个拉斯维加斯过程，并让它返回默认答案，从而引入出错的可能性。反过来，如果能够高效验证候选结果，反复生成并验证结果就可能得到一个零错误过程；其期望效率取决于成功概率和验证成本。(cs.yale.edu)
代表性算法
随机化快速排序。 快速排序选择一个枢轴，将输入划分为若干部分，再通过递归对这些部分排序。在标准假设下，每次都均匀随机地选择枢轴，可使每个固定输入的期望工作量达到 (O(n\log n))。最坏的一次执行仍可能需要 (O(n^2)) 的工作量。它属于拉斯维加斯算法，因为枢轴的选择不会影响结果的正确性。这些界限使用大O记号来描述渐近时间复杂度。(cs.cmu.edu)
随机收缩。 在图论中，卡格算法通过反复收缩均匀随机选取的边，直至只剩两个超级顶点，来寻找全局最小割。对于具有 (n\geq2) 个顶点的连通无向多重图，单次运行的成功概率至少为 (2/[n(n-1)])。独立重复该过程，并保留找到的最小割，可以提高成功概率。(cs.yale.edu)
随机化矩阵计算。 数值线性代数中的一些方法使用随机采样或投影，为矩阵构造规模更小的表示，称为草图。在这些草图上进行计算，可以近似求解最小二乘问题或进行低秩分解。这类方法的理论保证将计算成本的降低与近似误差及失败概率联系起来。(arxiv.org)
降低错误概率
概率放大通过重复运行来提高可靠性。如果一个判定算法对每个输入的成功概率都至少为 (2/3)，那么独立重复运行该算法并采用多数表决，就能使错误概率随重复次数呈指数下降。因此，重复 (O(\log(1/\delta))) 次就足以将错误概率降至不超过 (\delta)。统计独立性十分重要：重复完全相同的随机执行过程，并不能提供新的证据。(theory.cs.princeton.edu)
如何汇总结果取决于具体问题。多数表决适用于具有双侧错误的判定问题；单侧错误检验则可以采用恰当的接受或拒绝规则。对于随机收缩算法，应保留观察到的最小割，因为生成的每个割都是有效的，只是未必最优。(theory.cs.princeton.edu)
复杂性类与实现
对于判定问题，BPP 表示具有有界双侧错误的多项式时间随机化计算。RP 允许假阴性，但不允许假阳性；coRP 则恰好相反。ZPP 包含能够在期望多项式时间内无错误地求解的问题。这些复杂性类将效率与可靠性的不同组合形式化。(theory.cs.princeton.edu)
去随机化旨在用确定性计算取代随机选择，同时保持计算效率。是否每个 BPP 问题都能在确定性多项式时间内求解，仍是一个核心的未解问题。枚举所有随机比特序列是一种基本的模拟方式，但其成本通常随所用比特数呈指数增长。(people.eecs.berkeley.edu)
实际实现通常通过伪随机数生成器获得随机选择；这种生成器以确定性方式扩展一个初始状态。在生成器条件兼容的情况下，重复使用同一种子有助于实现可复现性，不过软件版本和执行细节也可能影响结果。在统计上有用，并不意味着适用于密码学：普通伪随机数生成器可能是可预测的，不能替代密码学安全的随机性来源。(docs.python.org)
参考来源
- Notes on Randomized Algorithmscs.yale.edu
- Randomized Computationtheory.cs.princeton.edu
- Chapter 7: Randomized Algorithmscs.cmu.edu
- RandomizedAlgorithmscs.yale.edu
- Randomized algorithms for matrices and dataarxiv.org
- 895 Randomness and Computationpeople.csail.mit.edu
- random — Generate pseudo-random numbersdocs.python.org