随机算法深度

关键词速览

关键词	解释
Las Vegas	必定正确但运行时间随机
Monte Carlo	运行时间确定但可能出错
Karger算法	随机化最小割算法
随机化快速排序	期望O(n log n)排序
概率分析	期望性能的数学分析
PCP定理	概率可检验证明
随机游走	随机过程的图论应用
2-SAT	随机游走求解
随机化在ML	随机梯度下降等
尾界	Chernoff/Hoeffding不等式

摘要

随机算法利用随机性来简化算法设计、提高效率或绕过问题的固有难度。本文系统阐述随机算法的两大范式——Las Vegas算法（保证正确性，运行时间随机）和Monte Carlo算法（确定时间，可能出错），深入分析随机快速排序、Karger最小割算法、随机游走求解2-SAT等经典技术，并探讨PCP定理与计算难度的联系。最后介绍随机化方法在机器学习中的广泛应用，包括随机梯度下降、随机近似和概率编程。

---

1. 随机算法的两种范式

1.1 Las Vegas算法

Las Vegas算法的核心特征：

• 保证正确性：输出必定正确
• 随机运行时间：运行时间依赖随机选择
• 典型应用：快速排序、随机化选择

形式化定义：

$$P(\text{正确})=1,\mathbb{E}[T(n)]=\text{poly}(n)$$

1.2 Monte Carlo算法

Monte Carlo算法的特征：

• 确定运行时间：时间不依赖随机性
• 可能出错：存在失败概率
• 可调精度：通过重复提高成功率

形式化定义：

$$P(\text{正确})\ge 1-ϵ,T(n)=\text{poly}(n,1/ϵ)$$

两类错误：

• 单边错误：只可能返回错误答案（false positive/negative）
• 双边错误：可能返回任意错误

Note

许多NP完全问题存在指数时间的Monte Carlo算法（如素数测试），但在确定型模型下需要指数时间。

1.3 两类算法的对比

特征	Las Vegas	Monte Carlo
正确性	100%	可能失败
运行时间	随机	确定
应用场景	排序、搜索	优化、近似
错误控制	N/A	重复采样

---

2. 随机化快速排序分析

2.1 算法描述

随机化快速排序通过随机选择pivot打破最坏情况：

def randomized_quicksort(A, lo, hi):
    if lo < hi:
        # 随机选择pivot
        pivot_idx = random.randint(lo, hi)
        A[lo], A[pivot_idx] = A[pivot_idx], A[lo]
        
        # 分区
        p = partition(A, lo, hi)
        
        # 递归排序
        randomized_quicksort(A, lo, p - 1)
        randomized_quicksort(A, p + 1, hi)
 
def partition(A, lo, hi):
    pivot = A[hi]  # pivot在随机化后已在lo位置
    i = lo - 1
    
    for j in range(lo, hi):
        if A[j] <= pivot:
            i += 1
            A[i], A[j] = A[j], A[i]
    
    A[i + 1], A[hi] = A[hi], A[i + 1]
    return i + 1

2.2 期望运行时间分析

定理：随机化快速排序的期望运行时间为 $O(n\log n)$。

关键引理：对于大小为 $n$ 的数组，选择第 $k$ 大元素的概率为 $1/n$。

递归方程： 设 $T(n)$ 为期望运行时间，

$$T(n)=\frac{1}{n}\sum _{k=1}^n[T(k-1)+T(n-k)]+\Theta (n)$$

其中 $k$ 是pivot的排名，均匀分布在 $[1,n]$。

证明：观察到左右子问题对称：

$$T(n)=\frac{2}{n}\sum _{k=1}^{n-1}T(k)+\Theta (n)$$

使用归纳法可证明 $T(n)\le cn\log n$（取合适常数 $c$）。

Important

确定型快速排序最坏情况 $O(n^2)$，但随机化后期望始终为 $O(n\log n)$，消除了对输入分布的依赖。

---

3. Karger算法：随机化最小割

3.1 问题定义

Karger算法用于求解最小割问题：

• 输入：无向图 $G=(V,E)$
• 输出：最小容量边割集

3.2 边的随机收缩

def karger_min_cut(G):
    """
    递归边收缩算法
    """
    n = len(G.vertices)
    
    # 终止条件：只剩2个顶点
    if n <= 2:
        return G.cut_value()
    
    # 随机选择一条边
    edge = random.choice(G.edges())
    u, v = edge endpoints
    
    # 收缩边(u, v) -> 合并为超节点 w
    G.contract(u, v, into=w)
    
    # 递归
    return karger_min_cut(G)

收缩操作：将边 $(u,v)$ 的两端合并为一个新顶点，删除产生的自环，保留其他平行边。

3.3 成功概率分析

核心引理：若最小割大小为 $k$，则每次随机收缩保留最小割的概率至少为 $(n-2)/(n-1)\cdot (n-3)/(n-2)\cdots 2/3=2/(n(n-1))$。

证明：设图有 $n$ 个顶点，最小割有 $k$ 条边。

第1次收缩时，选到割中边的概率 $\le k/|E|\le k/(kn/2)=2/n$。

因此，第1次收缩不割断最小割的概率 $\ge 1-2/n=(n-2)/n$。

归纳可得，整个递归过程不割断最小割的概率至少为：

$$\prod _{i=2}^{n-1}\frac{n-i}{n-i+1}=\frac{2}{n(n-1)}$$

3.4 重复提升成功率

单次成功率 $p=\frac{2}{n(n-1)}$ 极低。

重复策略：运行 $N=\frac{n(n-1)}{2}\cdot \ln n$ 次取最小值。

失败概率：

$$P(\text{全部失败})\le {\left(1-\frac{2}{n(n-1)}\right)}^N\le e^{-2\ln n}=n^{-2}$$

总运行时间：$O(n^2\log n)$（因为每次迭代 $O(n)$）。

---

4. 随机游走与2-SAT

4.1 2-SAT问题

2-SAT是布尔可满足性的特例：每个子句恰好包含2个文字。

问题形式化：

$$\varphi =\underset{i=1}{\overset{m}{\bigwedge }}(l_{i1}\vee l_{i2})$$

判断是否存在赋值使 $\varphi$ 为真。

4.2 随机游走算法

def random_walk_2sat(phi, n):
    """
    随机游走求解2-SAT
    """
    assignment = random_assignment(n)  # 随机初始化
    
    for i in range(2 * n * n):  # 足够多次尝试
        if is_satisfying(assignment, phi):
            return assignment  # 成功
        
        # 找到第一个未满足的子句
        clause = find_unsatisfied_clause(assignment, phi)
        # 随机翻转其中一个变量的值
        var = random.choice([clause[0].var, clause[1].var])
        assignment.flip(var)
    
    return None  # 可能无解

4.3 期望运行时间分析

Papadimitriou定理：若公式可满足，则随机游走在 $O(m^2)$ 期望步数内找到解。

直觉：在可满足的情况下，算法逐步向”满意赋值”移动。

定义霍恩子句图，可构造马尔可夫链，其混合时间给出算法收敛速度。

Example

考虑一个可满足的2-SAT实例。随机游走每次翻转使某个子句满足的变量，期望上会向某个固定点（真赋值）漂移。

---

5. PCP定理

5.1 PCP的定义

PCP定理（概率可检验证明）是计算复杂度的里程碑：

$$NP=PCP(\log n,O(1))$$

解释：NP中的问题存在多项式时间可验证的证明，但验证者只读取 $O(1)$ 个随机选择的比特。

5.2 PCP与近似难度的联系

PCP定理的直接推论：存在优化问题，其最优值难以近似。

Max-3SAT的PCP：

• NP语言可归约为Max-3SAT的某个参数版本
• 最大化满足的子句数
• 区分”完全可满足”和”最多满足99%“是NP难的

PCP重构引理：

$$\exists \text{常数 }ϵ>0:\text{Max-3SAT-Sub}\in NPC(ϵ)$$

这意味着即使 $1-ϵ$ 近似也是NP难的。

5.3 PCP在密码学中的应用

零知识证明（Zero-Knowledge Proof）基于PCP框架：

组件	作用
证明者	生成PCP证明
验证者	随机查询少量位置
零知识	未查询位置的信息不泄露

---

6. Chernoff/Hoeffding不等式

6.1 Chernoff界

Chernoff不等式是分析随机算法的基础工具：

定理（Chernoff界）：设 $X_1,...,X_n$ 为独立随机变量，$0\le X_i\le 1$，$X=\sum X_i$，$\mu =\mathbb{E}[X]$。则对任意 $\delta >0$：

$$P(X>(1+\delta )\mu )\le {\left(\frac{e^{\delta }}{(1+\delta {)}^{1+\delta }}\right)}^{\mu }$$

常用形式：对 $ϵ>0$，

$$P(|X-\mu |>ϵ\mu )\le 2e^{-\mu {ϵ}^2/3}$$

6.2 Hoeffding不等式

Hoeffding不等式是Chernoff界的连续扩展：

设 $X_1,...,X_n$ 为独立有界随机变量，$a_i\le X_i\le b_i$，则对任意 $t>0$：

$$P\left(\left|\sum _{i=1}^n(X_i-\mathbb{E}[X_i])\right|>t\right)\le 2\exp \left(-\frac{2t^2}{{\sum }_{i=1}^n(b_i-a_i{)}^2}\right)$$

6.3 应用示例：负载均衡

应用：$n$ 个作业随机分配到 $m$ 台机器，负载浓度不等式的直接应用。

设每台机器期望负载为 $n/m$，则实际负载偏离超过 $ϵn/m$ 的概率指数小。

---

7. 随机化在机器学习中的应用

7.1 随机梯度下降（SGD）

随机梯度下降是深度学习的基础优化算法：

def sgd(model, data, lr=0.01):
    for epoch in range(num_epochs):
        random.shuffle(data)
        for x, y in data:
            # 计算随机梯度（仅用一个样本）
            grad = compute_gradient(model, x, y)
            model.weights -= lr * grad

收敛性：使用适当学习率调度，SGD以 $O(1/\sqrt{T})$ 速率收敛到最优解（在非凸情况下到静止点）。

7.2 随机近似

坐标下降法：随机选择要更新的坐标。

随机坐标下降：

def random_coordinate_descent(f, x, alpha):
    n = len(x)
    for _ in range(iterations):
        i = random.randint(0, n-1)  # 随机选坐标
        # 在第i个坐标上优化
        x[i] -= alpha * partial_derivative(f, x, i)
    return x

收敛速度：期望收敛率 $O(1/T)$（强凸函数）。

7.3 随机森林与Bagging

Bagging（Bootstrap Aggregating）：

def bagging(train_data, num_trees):
    trees = []
    for _ in range(num_trees):
        # Bootstrap采样
        bootstrap_sample = resample(train_data)
        tree = train_decision_tree(bootstrap_sample)
        trees.append(tree)
    
    return lambda x: vote(trees, x)  # 集成预测

随机森林：在Bagging基础上，每次分裂时随机选择特征子集。

7.4 变分推断

概率机器学习使用随机化进行近似推断：

方法	思想
蒙特卡洛采样	从后验直接采样
变分推断	用简单分布近似复杂后验
MCMC	马尔可夫链混合到后验

---

8. 随机化算法设计技术

8.1 随机化vs确定性选择

技术1：随机抽样避免最坏情况

• 快速排序的随机pivot
• 选择算法的随机采样
• 图算法的随机起点

技术2：随机扰动打破对称性

• 分布式系统的随机退避
• 博弈论中的混合策略

技术3：概率放大

• 从Monte Carlo算法的常数错误率放大到任意小
• 重复独立运行 $k$ 次，错误率降至 ${ϵ}^k$

8.2 脱散技术（Derandomization）

确定性算法可以在不损失效率的情况下消除随机性：

方法1：条件期望 利用期望的线性性质，选择使条件期望最大的分支。

方法2：$ϵ$-网与$ϵ$-样本 构造确定性的小样本集以近似随机选择的效果。

方法3：局部屋历法 枚举所有随机种子而非使用真随机数。

---

9. 复杂性类的随机化视角

9.1 BPP类

BPP（Bounded-error Probabilistic Polynomial time）：

$$BPP=\{L:\exists \text{多项式时间随机算法 }\mathcal{A},P(\mathcal{A}(x)=1_{x\in L})\ge 2/3\}$$

开放问题：$BPP=P$？大多数研究者相信随机性可以被消除。

9.2 RP与co-RP

• RP（Randomized Polynomial time）：单面错误（只假阳性）
• co-RP：只假阴性
• $RP\subseteq BPP\subseteq PP$

9.3 随机电路

若 $BPP\ne P$，则需要超多项式大的随机电路才能模拟随机算法。

---

10. 算法性能总结

算法	类型	期望时间	成功率
随机快速排序	Las Vegas	$O(n\log n)$	100%
随机选择	Las Vegas	$O(n)$	100%
Karger最小割	Monte Carlo	$O(n^2\log n)$	$1-1/n^2$
随机游走2-SAT	Monte Carlo	$O(m^2)$	$>0$ 时 $100\%$
Miller-Rabin素数测试	Monte Carlo	$O({\log }^{3}n)$	单次 $1/4$

---

参考来源

1. Motwani, R., & Raghavan, P. (1995). Randomized Algorithms. Cambridge University Press.
2. Karger, D. R. (1994). Random Sampling in Graph Optimization. SIAM Journal on Computing.
3. Arora, S., & Barak, B. (2009). Computational Complexity: A Modern Approach. Cambridge University Press.
4. Mitzenmacher, M., & Upfal, E. (2005). Probability and Computing. Cambridge University Press.
5. Chernoff, H. (1952). A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the Sum of Observations. AMS.

---

相关文档

• 计算复杂性理论深度 - BPP与随机复杂性
• 近似算法详解 - PCP与近似硬度
• 组合优化深度指南 - 组合优化的确定型方法
• 在线算法详解 - 随机化在线算法