随机化算法

随机化改变的是算法面对固定输入时的选择方式。一个排列可以让“总选第一个元素作枢轴”反复遇到极端划分，但未必能让“每次从当前元素中均匀选枢轴”也以高概率持续失衡。算法不需要输入天然友好，而是自己控制随机分布，再证明不利选择累计发生的可能性。

这与平均情形分析不同。平均情形分析对输入分布取平均；随机算法分析可以把输入完全固定，只平均内部随机选择。二者也能同时使用，但需要写成两层随机量，不能在证明中悄悄互换。

分析时可以先把所有随机选择收集成一条“随机带” $R$。固定它以后，算法就是确定的执行过程，可以逐步验证循环、递归和输出；随后再计算哪些随机带导致昂贵运行或错误答案。这样，功能不变量和概率估计各自承担明确工作，不会因为流程中出现随机选择就免除正确性证明。

随机快排：答案不随机，代价随机 ​

对互异元素，每轮随机选择枢轴、正确划分并递归的快速排序，无论选到什么枢轴，最终排序结果都正确。若总选到当前最小或最大值，工作量仍可达到 $\mathrm{\Theta }(n^2)$；但这种坏轨迹不会推翻期望 $O(n\log n)$ 的结论。

把元素按最终秩记为 $1,\dots ,n$。秩为 $i<j$ 的两项会直接比较，当且仅当区间 $i,\dots ,j$ 中最先被选作枢轴的是这两个端点之一，概率为 $2/(j-i+1)$。把所有元素对的比较指标相加，得到

这里使用期望的线性性理路期望Expectation · Expected value实值或复值随机变量关于概率测度的 Lebesgue 积分，概括加权平均与总体质量平衡。，不需要假设不同元素对的比较事件相互独立。大量重复值时应使用正确处理相等块的划分方式，不能直接照搬互异秩的这段计数。

Freivalds 检验：少量随机投影检查矩阵乘法 ​

设 $A,B,C$ 是某个域上的 $n\times n$ 矩阵，整数 $n\ge 1$。要检查 $AB=C$，独立均匀选取 $r\in \{0,1{\}}^n$，比较

一次检验只需矩阵—向量乘法，共 $O(n^2)$ 次域运算。若等式真实成立，检验总通过；若 $D=AB-C\ne 0$，选一行中非零的系数 $D_{ij}$。固定 $r$ 的其他坐标后，方程

在 $r_j=0,1$ 两个候选中至多成立一次。因此 $\text{Pr}[Dr=0]\le 1/2$，错误矩阵误通过的概率至多一半。这是单侧错误：拒绝给出确实不相等的证据，通过则带有明确的误接受概率。

例如在实数域上取 $A=B=I_2$，却声称 $C=\mathrm{diag}(1,2)$。四个等可能向量为 $(0,0),(1,0),(0,1),(1,1)$；前两个误通过，后两个检测到第二坐标不符。差异确实存在，但某些投影完全没有观察到它，所以“一次通过”无法成为确定性等式证书。若把差异放到其他位置，证明仍需固定那个非零系数，其余随机坐标的值不影响至多一个候选能消去差异的事实。

这段证明使用精确域运算。$O(n^2)$ 计的是域运算次数；在有理数实现中还要计入分子分母的位长增长。若把等号改为浮点容差比较，还需另外分析舍入和阈值，原来的概率界不会自动覆盖新判定规则。

独立重复与重复同一次实验 ​

对上面的错误矩阵，使用 $k$ 个彼此独立的新向量，并要求每次均通过，误接受概率至多为 $2^{-k}$。反复使用同一个 $r$，或者把同一随机种子重置到同一状态，得到的仍是同一次检验，不能把错误概率继续相乘。

双侧错误通常用多数投票放大。若每轮独立、每轮正确率至少为 $1/2+\gamma$，其中 $0<\gamma \le 1/2$，Hoeffding 界理路Hoeffding 不等式Hoeffding's inequality独立有界随机变量和偏离期望的概率以平方偏差的指数速度衰减。给出整数 $k\ge 1$ 轮多数投票失败概率至多 $e^{-2k{\gamma }^2}$。独立性和正的正确率间隙都承担实际作用，仅说“重复很多次”还没有证明放大。

最坏输入与最坏随机选择 ​

表达式 $\underset{x}{max}{\mathbb{E}}_{R}T(x;R)$ 先固定一个输入，再平均随机性；${\mathbb{E}}_R\underset{x}{max}T(x;R)$ 则允许针对已经出现的随机结果挑选输入，可能更大。例如 $x,R\in \{0,1\}$，$R$ 均匀，当 $x=R$ 时成本为 $M>1$，否则为 $1$。两个表达式分别为 $(M+1)/2$ 与 $M$。量词先后描述不同环境，不能靠形式交换消除差别。

有限期望时间可以转成带失败概率的时间界。取 $0<\delta <1$。若 Las Vegas 算法满足 $\mathbb{E}T(x;R)\le t(x)<\mathrm{\infty }$ 且 $t(x)>0$，运行至预算 $\lceil t(x)/\delta \rceil$ 仍未结束就停止，则 Markov 不等式理路Markov 不等式Markov's inequality非负随机变量超过阈值的概率由其期望除以阈值控制。给出停止失败概率至多 $\delta$。已返回的答案仍正确；对判定问题，超时后返回一个固定布尔答案，就得到时间有界、错误率至多 $\delta$ 的 Monte Carlo 版本。$t(x)=0$ 时非负运行时间几乎必然为零，单独直接处理。执行截断还须有可计算的预算上界，并计入计算该预算的开销。

随机种子有利于复现实验，但复现与概率保证处在不同层次。固定种子后，执行本身已经确定；理论保证针对规定的抽样分布。使用伪随机生成器时，应区分“按数学模型独立抽样”的定理与“具体实现如何近似或实现所需随机性质”的说明。

Moser–Tardos 重采样算法理路Moser–Tardos 重采样算法Moser–Tardos resampling · 算法化局部引理在独立变量模型中局部重采样坏事件，用见证树证明终止与每个事件的期望修复次数。给出另一种 Las Vegas 构造：反复修复当前坏事件，返回时所有约束都满足。它把随机带按变量排成重采样表，用见证树控制期望修复次数；要得到期望时间界，还须计入抽样、收集受影响约束和重新检查的成本。

通用哈希理路通用哈希Universal hashing · Universal hash family从函数族随机选择哈希函数，使任意预先固定的不同键对以至多 1/m 的概率碰撞。通过函数族的碰撞概率控制搜索结构，随机选择通过枢轴质量控制剩余规模，随机检验通过投影避免计算全部结果。三者使用随机性的机制不同；应分别明确抽样对象、坏事件和成本，而不是把“加入随机数”当作效率证明。

随机线性网络编码理路随机线性网络编码Random linear network coding · RLNC通过随机选择局部有限域系数构造多播码，并用满秩概率与多项式零点界量化失败风险。随机选择局部有限域系数，终点通过验秩判断是否收到足够独立信息。其失败概率可由非零行列式多项式的零点界控制；失败可以显式检测并重试，而不是在秩不足时输出未经验证的数据。域大小、网络结构与随机系数分布共同决定概率保证。