随机化算法

随机化算法把内部随机位纳入计算过程，用随机选择避开对手精心构造的坏模式，或以少量样本近似巨大空间。分析通常先固定输入，只对内部随机性取概率。因此

不是同一个界：前者允许每条随机带有不同的坏输入，后者则先让同一条随机带面对最坏输入。若还对 $x$ 按某个分布取期望，那是第三种平均输入模型。

期望资源界也不同于高概率资源界。后者应写出尾部事件，例如对每个长度为 $n$ 的合法输入 $x$，

仅有 ${\mathbb{E}}_R[T]\le t(n)$ 不能推出运行时间总在同一量级；它至多通过额外的尾界论证给出某种概率控制。反过来，若每条随机带都有确定性上界，该上界自然也控制期望。报告复杂度时必须同时说清资源单位、是最坏还是期望，以及坏事件如何随 $n$ 或置信参数 $\delta$ 变化。

输入、环境和算法可能各有随机性。此时要说明概率是只对内部随机带 $R$ 取得，还是对输入样本与 $R$ 联合取得；也要说明对手是在随机币产生前固定输入，还是能观察执行后自适应行动。把这些来源都称为“平均情况”会改变保证的量词顺序。

随机快速排序对任意固定数组随机选枢轴，无论如何选择都输出正确排序，而内部随机性使其期望时间为 $O(n\log n)$，因而是 Las Vegas 算法。这个期望界不意味着每次运行都在 $O(n\log n)$ 内结束；若声称高概率时间界，还必须说明失败概率如何随 $n$ 衰减。

Miller–Rabin 素性测试在标准使用方向下不会把素数判为合数，却可能把合数误判为素数，是单侧 Monte Carlo 算法；独立选取底数并重复试验可以乘法地压低误判率。“实验十次都成功”本身不是概率证明；保证必须量化所有合法输入、随机源和坏事件。工程中以伪随机生成器代替真随机时，安全性和独立性保证取决于对手能否预测种子；固定种子只提供可复现性，不会自动产生输入无关的确定性最坏界。

算法正确性公理库算法正确性Algorithm correctness · Partial and total correctness所有合法执行都符合规格，并在完全正确时保证终止。与概率公理公理库Kolmogorov 概率公理Kolmogorov axioms · Probability axioms把概率定义为样本空间上总质量为一的可数可加测度。共同组织这类保证。随机性可以影响输出、运行时间或内部表示；分析时应为关心的量分别定义随机变量和坏事件，不能只贴上“随机算法”标签。独立重复可借助概率放大公理库概率放大Probability amplification · Error reduction独立重复并多数表决可把有界错误概率指数降低。降低错误，但前提是单次试验的错误结构、独立性和聚合规则确实支持该结论。

对手若在随机比特揭示前固定全部输入，通常称为 oblivious；若能依据已经观察到的结果选择后续请求，则是 adaptive。只对前者成立的期望或高概率界不能直接用于后者。类似地，估计量的数值误差、决策算法输出错误以及超出运行时间预算是三个不同坏事件，即使它们都用概率上界描述，也应分别命名和量化。