随机化算法

随机化算法在执行过程中进行随机选择，以提高效率、简化性或鲁棒性，其性能和正确性以概率保证而非最坏情况确定性来表达。

Definition

随机化算法是一种利用随机比特源做出部分决策的算法，因此其运行时间、输出或两者都是随机变量，通过它们的期望或概率分布进行分析。

Scope

本主题涵盖将随机性作为计算资源的算法：拉斯维加斯模型（始终正确，随机运行时间）和蒙特卡洛模型（固定运行时间，有界错误概率），典型示例包括随机快速排序、随机选择、素性测试以及跳表等随机数据结构，以及用于分析它们的概率分析工具（期望、方差、尾部和集中不等式）。

Core questions

• 引入随机性如何能使算法比任何已知的确定性算法更快或更简单？
• 拉斯维加斯算法和蒙特卡洛算法之间有什么区别？
• 如何分析预期运行时间或错误概率？
• 集中不等式如何限制不良结果的发生概率？
• 蒙特卡洛算法的错误如何通过重复来减少？

Key concepts

• 随机比特作为资源
• 拉斯维加斯算法
• 蒙特卡洛算法
• 预期运行时间
• 错误概率和放大
• 集中不等式
• 随机快速排序
• 跳表

Key theories

拉斯维加斯与蒙特卡洛

拉斯维加斯算法总是产生正确结果，但运行时间是随机的（通过期望分析），而蒙特卡洛算法在固定时间内运行，但可能以有界概率产生不正确结果，重复可以缩小此概率。

概率素性测试

Miller-Rabin等随机测试通过检查随机证据，以高置信度在多项式时间内证明素性；复合数会被大多数证据揭示，因此重复试验可使错误概率变得可忽略不计。

Clinical relevance

随机化算法被广泛应用：Miller-Rabin素性测试是公钥密码学的基础；随机哈希和负载均衡保持分布式系统的高效运行；随机快速排序和快速选择提供了稳健的预期性能；随机抽样和草图技术使得处理海量数据流成为可能。

History

概率算法在20世纪70年代随着Solovay-Strassen和Miller-Rabin素性测试的出现而崭露头角，使随机性成为一种受人尊敬的计算工具。20世纪80年代和90年代见证了随机数据结构（跳表、treap）、随机图算法和几何算法，以及Motwani和Raghavan于1995年出版的教科书中所编纂的系统理论。

Key figures

• Michael Rabin
• Robert Solovay
• Volker Strassen
• Rajeev Motwani
• Prabhakar Raghavan

Seminal works

• motwani1995
• rabin1980
• cormen2009

Frequently asked questions

如果蒙特卡洛算法可能出错，如何信任它？

它的错误概率是有界的且已知，对于单边错误算法，通过使用独立的随机性多次运行算法，可以使其任意小。经过足够的重复后，错误答案的几率远小于硬件故障的几率。

为什么随机快速排序优于确定性快速排序？

确定性快速排序在对抗性或已排序的输入上，由于糟糕的枢轴选择，可能会达到其O(n平方)的最坏情况。随机选择枢轴使得无论输入如何，这种最坏情况都极不可能发生，从而在每个输入上都提供预期的O(n log n)性能。