随机化算法：当运气成为武器

在算法的世界里，确定性一直被视为美德。给定相同的输入，程序总是产生相同的输出——这是我们从第一天学编程就被灌输的信条。然而，当我们引入一个看似荒谬的元素——掷硬币——许多困难问题突然变得出人意料地简单。

这不是偷懒，也不是碰运气。随机化算法（Randomized Algorithm）是一种严肃的、有数学保证的算法设计范式。它的核心思想是：让算法做出随机选择，用概率论来保证整体性能。

考虑一个直觉：如果一个确定性算法要防御所有可能的最坏情况输入，它必须”小心翼翼”地运行。但如果算法可以掷硬币，那么没有任何对手能构造出针对所有随机选择都最坏的输入。随机性打破了对手与算法之间的信息对称。

本文将深入探讨随机化算法的理论基础与实际应用，从基本分类到经典算法，从分析工具到工程实践。

一、Las Vegas 与 Monte Carlo：两大流派

随机化算法按其输出保证的不同，分为两大类。

1.1 Las Vegas 算法

Las Vegas 算法的特征是：结果总是正确的，但运行时间是随机变量。

Las Vegas 算法 L:
  repeat:
    随机选择策略 s
    运行确定性子程序 D(input, s)
    if D 输出了正确结果:
      return 结果
  // 循环直到找到正确结果

经典例子：

随机化快速排序：无论怎么选 pivot，排序结果都是正确的。只是不同的 pivot 选择导致不同的运行时间。期望 O(n log n)，最坏 O(n^2)，但最坏情况发生的概率极低。
随机化快速选择（QuickSelect）：总能找到第 k 小的元素，期望 O(n)。
Treap 的插入操作：随机优先级保证了期望 O(log n) 的树高（参见第 18 篇）。

1.2 Monte Carlo 算法

Monte Carlo 算法的特征是：运行时间是确定的（或有确定上界），但结果可能错误。

Monte Carlo 算法 M:
  随机选择策略 s
  运行确定性子程序 D(input, s)
  return D 的输出  // 可能正确，也可能错误

根据错误类型，Monte Carlo 算法又分为：

单边错误（one-sided error）：如果输出 YES 则一定正确，如果输出 NO 则可能错误（或反过来）。
双边错误（two-sided error）：YES 和 NO 都可能错误，但正确概率 > 1/2。

经典例子：

Miller-Rabin 素性测试：如果说”合数”则一定对，如果说”素数”则有小概率错误。单边错误。
Schwartz-Zippel 多项式恒等性检验：如果说”不恒等”则一定对。单边错误。
Karger 最小割：单次运行可能给出非最小割。通过重复降低错误概率。

1.3 两者的互相转换

Las Vegas → Monte Carlo：

如果有一个 Las Vegas 算法 L，期望运行时间为 T，我们可以把它变成 Monte Carlo 算法：运行 L 最多 2T 时间，如果没结束就输出”失败”。由 Markov 不等式，失败概率 ≤ 1/2。

// Las Vegas -> Monte Carlo 转换
result_t las_vegas_to_monte_carlo(input_t input, int time_limit) {
    // 运行 Las Vegas 算法，但限制时间
    start_timer();
    result_t result = run_las_vegas(input);
    if (elapsed_time() <= time_limit) {
        return result;  // 在时限内完成，结果正确
    }
    return FAILURE;     // 超时，输出失败
}

Monte Carlo → Las Vegas：

如果有一个 Monte Carlo 算法 M（错误概率 ≤ 1/3），并且我们有办法验证结果的正确性，就可以把它变成 Las Vegas 算法：反复运行 M，每次验证结果，直到结果正确。

// Monte Carlo -> Las Vegas 转换（需要验证器）
result_t monte_carlo_to_las_vegas(input_t input) {
    while (1) {
        result_t result = run_monte_carlo(input);
        if (verify(input, result)) {
            return result;  // 验证通过，结果正确
        }
        // 验证失败，重新运行
    }
    // 期望迭代次数：1/(1-error_prob) 次
}

关键限制：Monte Carlo → Las Vegas 的转换要求存在高效的验证器。这并非总是可能的。例如，判断一个数是否为素数——如果 Miller-Rabin 说它是素数（可能错），我们如何”验证”？在 AKS 算法发明之前，这个验证本身就很困难。

1.4 错误概率的放大

Monte Carlo 算法的一个核心性质是：可以通过重复运行来任意降低错误概率。

如果单次错误概率 ≤ 1/3，独立运行 k 次后取多数结果（对于双边错误）或取”任何一次成功”（对于单边错误），错误概率指数下降：

单边错误：k 次都错误的概率 ≤ (1/3)^k
双边错误（多数表决）：由 Chernoff 界，错误概率 ≤ exp(-Ω(k))

这意味着 O(log(1/δ)) 次重复就能将错误概率降到 δ 以下。在实践中，重复 50-100 次就能使错误概率低于宇宙中质子自发衰变的概率。

二、Schwartz-Zippel 引理：多项式的随机检验

2.1 引理陈述

Schwartz-Zippel 引理是随机化算法中最优雅、最实用的工具之一。

引理：设 P(x_1, x_2, …, x_n) 是域 F 上的非零多项式，总度数为 d。设 S 是 F 的一个有限子集。如果 r_1, r_2, …, r_n 从 S 中独立均匀随机选取，则：

Pr[P(r_1, r_2, ..., r_n) = 0] ≤ d / |S|

直觉理解：一个 d 次多项式最多有 d 个零点（一元情况）。在一个大集合 S 中随机选一个点，命中零点的概率不超过 d/|S|。多元情况下，这个界依然成立——这才是引理的深刻之处。

2.2 证明思路

对变量个数 n 做归纳。基础情形（n=1）显然：一元 d 次多项式最多 d 个根。归纳步骤将 P 按 x_1 展开为 Σx_1^i · Q_i(x_2,…,x_n)，其中 Q_k 非零。先随机选 r_2,…,r_n：

Q_k(r_2,…,r_n) = 0 的概率 ≤ (d-k)/|S|（归纳假设）
否则 P(x_1,r_2,…,r_n) 是非零 k 次一元多项式，零点概率 ≤ k/|S|

总概率 ≤ (d-k)/|S| + k/|S| = d/|S|。

2.3 应用一：矩阵乘法验证

问题：给定三个 n×n 矩阵 A、B、C，验证 AB = C。

确定性方法：直接计算 AB，时间 O(n^3)（朴素算法）或 O(n^2.37)（最优已知）。

Freivalds 随机化算法（1979）：

1. 随机生成向量 r ∈ {0,1}^n
2. 计算 A(Br) - Cr
3. 如果结果为零向量，输出 "AB = C"
4. 否则输出 "AB ≠ C"

时间复杂度：O(n^2)——只需要三次矩阵-向量乘法。

正确性： - 如果 AB = C，则 A(Br) - Cr = (AB - C)r = 0，一定输出正确。 - 如果 AB ≠ C，设 D = AB - C ≠ 0。那么 Dr = 0 的概率是多少？

D 的某一行 d_i 非零。dr = d_1·r_1 + … + d_n·r_n 是 r 的一次多项式。由 Schwartz-Zippel，在 {0,1}^n 中，Pr[d_i · r = 0] ≤ 1/2。

所以单次错误概率 ≤ 1/2。重复 k 次，错误概率 ≤ 1/2^k。

// Freivalds 矩阵乘法验证
// 检验 A * B == C，均为 n x n 矩阵
// 返回 1 表示通过验证，0 表示 AB != C
int freivalds_check(int n, double A[][MAX_N], double B[][MAX_N],
                    double C[][MAX_N], int iterations) {
    double r[MAX_N], Br[MAX_N], ABr[MAX_N], Cr[MAX_N];

    for (int iter = 0; iter < iterations; iter++) {
        // 生成随机向量 r ∈ {0,1}^n
        for (int i = 0; i < n; i++) {
            r[i] = rand() % 2;
        }

        // 计算 Br
        for (int i = 0; i < n; i++) {
            Br[i] = 0;
            for (int j = 0; j < n; j++) {
                Br[i] += B[i][j] * r[j];
            }
        }

        // 计算 A(Br)
        for (int i = 0; i < n; i++) {
            ABr[i] = 0;
            for (int j = 0; j < n; j++) {
                ABr[i] += A[i][j] * Br[j];
            }
        }

        // 计算 Cr
        for (int i = 0; i < n; i++) {
            Cr[i] = 0;
            for (int j = 0; j < n; j++) {
                Cr[i] += C[i][j] * r[j];
            }
        }

        // 检查 ABr == Cr
        for (int i = 0; i < n; i++) {
            if (fabs(ABr[i] - Cr[i]) > 1e-9) {
                return 0;  // 确定 AB != C
            }
        }
    }

    return 1;  // 通过所有轮次，高概率 AB == C
}

2.4 应用二：多项式恒等性检验

问题：给定两个多项式的符号表达式，判断它们是否恒等。

例如：(x+y)(x-y) 和 x^2 - y^2 是否恒等？

直接展开可能导致指数级别的项数。但用 Schwartz-Zippel，只需随机代入一个点检查即可。

1. 令 Q(x_1, ..., x_n) = P_1(x_1, ..., x_n) - P_2(x_1, ..., x_n)
2. 从足够大的集合 S 中随机选取 r_1, ..., r_n
3. 计算 Q(r_1, ..., r_n)
4. 如果为 0，输出 "恒等"；否则输出 "不恒等"

这是典型的 Monte Carlo 单边错误算法：说”不恒等”一定对。

2.5 应用三：完美匹配存在性

Tutte 矩阵：对于图 G = (V, E)，定义 n×n 的反对称矩阵 T，其中 T[i][j] = x_{ij}（形式变量），T[j][i] = -x_{ij}。

Tutte 定理：G 有完美匹配 ⟺ det(T) 不是零多项式。

用 Schwartz-Zippel：随机代入所有 x_{ij}，计算行列式。如果结果非零，则（高概率）存在完美匹配。这给出了一个 O(n^3) 的随机化算法——长期以来，确定性方法需要的时间更多。

三、随机化快速选择（Randomized QuickSelect）

3.1 问题定义

给定一个无序数组 A[0..n-1] 和一个整数 k，找到第 k 小的元素。

3.2 随机化 QuickSelect

// 随机化快速选择：期望 O(n)
int randomized_select(int *arr, int left, int right, int k) {
    if (left == right) {
        return arr[left];
    }

    // 随机选择 pivot
    int pivot_idx = left + rand() % (right - left + 1);
    pivot_idx = partition(arr, left, right, pivot_idx);

    int rank = pivot_idx - left + 1;
    if (k == rank) {
        return arr[pivot_idx];
    } else if (k < rank) {
        return randomized_select(arr, left, pivot_idx - 1, k);
    } else {
        return randomized_select(arr, pivot_idx + 1, right, k - rank);
    }
}

int partition(int *arr, int left, int right, int pivot_idx) {
    int pivot_val = arr[pivot_idx];
    // 把 pivot 移到末尾
    swap(&arr[pivot_idx], &arr[right]);

    int store_idx = left;
    for (int i = left; i < right; i++) {
        if (arr[i] < pivot_val) {
            swap(&arr[store_idx], &arr[i]);
            store_idx++;
        }
    }
    swap(&arr[store_idx], &arr[right]);
    return store_idx;
}

3.3 期望时间分析

设 T(n) 为在 n 个元素中 QuickSelect 的期望比较次数。

如果 pivot 的秩为 i（第 i 小），则： - 如果 k = i，结束。 - 如果 k < i，递归到大小为 i-1 的子问题。 - 如果 k > i，递归到大小为 n-i 的子问题。

最坏情况是 k = 1（找最小值），此时：

T(n) ≤ n + (1/n) Σ_{i=1}^{n} T(max(i-1, n-i))
     ≤ n + (2/n) Σ_{i=n/2}^{n} T(i)

解这个递推，得到 T(n) ≤ 4n = O(n)。

更精确的分析：对于找中位数，期望比较次数约为 (2 + 2ln2)n ≈ 3.39n。

3.4 与确定性 Median-of-Medians 的对比

Blum、Floyd、Pratt、Rivest 和 Tarjan（1973）给出了确定性 O(n) 的选择算法——Median of Medians（BFPRT 算法）：

1. 将数组分成 n/5 组，每组 5 个元素
2. 找到每组的中位数（常数时间）
3. 递归找这些中位数的中位数 m
4. 用 m 作为 pivot 进行 partition
5. 递归到相应的子问题

m 保证了至少 3n/10 的元素在每一边，所以递推为：

T(n) ≤ T(n/5) + T(7n/10) + O(n)

这给出 T(n) = O(n)，但常数因子很大（约 20-40 次比较）。

3.5 工程中为何偏爱随机化版本

对比维度	随机化 QuickSelect	确定性 BFPRT
期望比较次数	~3.4n	~20-40n
最坏情况	O(n^2)（概率极低）	O(n)（严格保证）
缓存友好性	好（顺序访问）	差（分组+递归开销）
实现复杂度	简单	复杂
实际运行时间	快	慢 2-5 倍
可被对手攻击	不能（随机化）	不能（确定性）

结论：在绝大多数工程场景中，随机化 QuickSelect 是首选。除非在对延迟有严格最坏情况保证的实时系统中，才考虑 BFPRT。

C++ STL 的 std::nth_element 早期使用 introselect（随机化 + 退化时切换到 BFPRT），但实际上 BFPRT 分支几乎不会被触发。

四、Karger 最小割算法

4.1 最小割问题

给定无向图 G = (V, E)，找到一个边集 C ⊆ E，使得删除 C 后图不连通，且 |C| 最小。

确定性算法：运行 n-1 次最大流（每次固定一个源点，枚举汇点），由最大流-最小割定理得到最小割。时间复杂度 O(n · maxflow)。用 Stoer-Wagner 算法可以做到 O(nm + n^2 log n)。

Karger（1993）的随机收缩算法令人惊叹地简单。

4.2 随机收缩算法

Karger-Contract(G):
  while |V| > 2:
    均匀随机选一条边 (u, v)
    收缩 (u, v)：将 u 和 v 合并为一个超级节点
                  删除 u-v 之间的所有边（自环）
                  保留所有多重边
  return 剩余两个超级节点之间的边数

关键操作——边的收缩：

当我们收缩边 (u, v) 时： 1. 创建新节点 w 代表 {u, v} 的合并 2. 对于所有与 u 或 v 相邻的节点 x（x ≠ u, x ≠ v），将边 (u,x) 和 (v,x) 都变为 (w,x) 3. 删除 u 和 v 之间的所有边（自环） 4. 图中可能出现多重边，必须保留

4.3 成功概率分析

定理：Karger 单次收缩算法输出最小割的概率 ≥ 2/(n(n-1)) ≥ 2/n^2。

证明：

设最小割大小为 k。

关键观察：图中每个节点的度数 ≥ k（否则单个节点和其余节点之间的割 < k，矛盾）。因此图中边数 m ≥ nk/2。

第一步收缩：一条随机边属于最小割的概率 ≤ k/m ≤ k/(nk/2) = 2/n。所以不切到最小割的概率 ≥ 1 - 2/n = (n-2)/n。

第二步收缩：图缩小到 n-1 个节点，最小割仍为 k（只要第一步没切到它）。同理不切到的概率 ≥ 1 - 2/(n-1) = (n-3)/(n-1)。

以此类推，第 i 步不切到的概率 ≥ (n-2-i)/(n-i)。

总成功概率：

P ≥ ∏_{i=0}^{n-3} (n-2-i)/(n-i)
  = (n-2)/n · (n-3)/(n-1) · (n-4)/(n-2) · ... · 1/3
  = 2/(n(n-1))
  ≥ 2/n²

这是一个望远镜求积（telescoping product），大部分项互消。

4.4 重复策略

单次成功概率 ≥ 2/n^2。重复 t = n^2/2 · ln(n) 次，取最小值：

P(所有 t 次都失败) ≤ (1 - 2/n²)^t
                    ≤ e^{-2t/n²}
                    = e^{-ln(n)}
                    = 1/n

所以以概率 ≥ 1 - 1/n 找到最小割。

每次收缩需要 O(n^2) 时间（选边 + 收缩），总共 n-2 次收缩，所以单次运行 O(n^2)。重复 O(n^2 log n) 次，总时间 O(n^4 log n)。

4.5 Karger-Stein 改进

Karger-Stein（1996）的核心观察：前期的收缩步骤很安全（因为节点多，切到最小割的概率低），后期才危险。

改进策略：

Karger-Stein(G):
  if |V| ≤ 6:
    用暴力方法找最小割
    return min_cut
  t = ceil(|V| / sqrt(2) + 1)
  G1 = Contract(G, t)   // 收缩到 t 个节点
  G2 = Contract(G, t)   // 独立再做一次收缩到 t 个节点
  return min(Karger-Stein(G1), Karger-Stein(G2))

每次收缩到 n/√2 个节点时的成功概率 ≥ 1/2。然后分两个独立分支递归，至少一个分支成功的概率足够高。

递推分析：

T(n) = 2T(n/√2) + O(n²)

递归深度 O(log n)，每层 O(n^2) 工作，分支数 2^{O(log n)} = n^{O(1)}。精确分析给出 T(n) = O(n^2 log^3 n)。

这是一个巨大的改进：从 O(n^4 log n) 到 O(n^2 log^3 n)。

4.6 Karger 最小割的 C 实现

使用并查集实现收缩操作，基于随机排列避免 rejection sampling 的效率问题：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

#define MAX_VERTICES 500
#define MAX_EDGES 50000

typedef struct { int u, v; } Edge;

typedef struct {
    int n, m;
    Edge edges[MAX_EDGES];
    int parent[MAX_VERTICES];
    int rank_uf[MAX_VERTICES];
} Graph;

int find(Graph *g, int x) {
    while (g->parent[x] != x) {
        g->parent[x] = g->parent[g->parent[x]];
        x = g->parent[x];
    }
    return x;
}

void unite(Graph *g, int x, int y) {
    int rx = find(g, x), ry = find(g, y);
    if (rx == ry) return;
    if (g->rank_uf[rx] < g->rank_uf[ry]) g->parent[rx] = ry;
    else if (g->rank_uf[rx] > g->rank_uf[ry]) g->parent[ry] = rx;
    else { g->parent[ry] = rx; g->rank_uf[rx]++; }
    g->n--;
}

void init_graph(Graph *g, int n) {
    g->n = n; g->m = 0;
    for (int i = 0; i < n; i++) { g->parent[i] = i; g->rank_uf[i] = 0; }
}

void add_edge(Graph *g, int u, int v) {
    g->edges[g->m++] = (Edge){u, v};
}

// 基于随机排列的单次收缩：O(m·α(n))
int karger_single_run(Graph *g_orig) {
    Graph g;
    memcpy(&g, g_orig, sizeof(Graph));

    // Fisher-Yates 随机排列所有边
    for (int i = g.m - 1; i > 0; i--) {
        int j = rand() % (i + 1);
        Edge tmp = g.edges[i]; g.edges[i] = g.edges[j]; g.edges[j] = tmp;
    }

    // 按排列顺序收缩非自环边
    for (int p = 0; g.n > 2 && p < g.m; p++) {
        int u = find(&g, g.edges[p].u), v = find(&g, g.edges[p].v);
        if (u != v) unite(&g, u, v);
    }

    int cut = 0;
    for (int i = 0; i < g.m; i++)
        if (find(&g, g.edges[i].u) != find(&g, g.edges[i].v)) cut++;
    return cut;
}

int karger_min_cut(Graph *g, int repetitions) {
    int min_cut = INT_MAX;
    for (int i = 0; i < repetitions; i++) {
        int cut = karger_single_run(g);
        if (cut < min_cut) min_cut = cut;
    }
    return min_cut;
}

相比朴素的 rejection sampling（随机选边，自环则重选），随机排列法避免了后期大量自环导致的效率退化。单次运行严格 O(m · α(n))，其中 α 是逆 Ackermann 函数。

五、Miller-Rabin 素性测试

Miller-Rabin 是随机化算法在数论中最成功的应用之一。这个算法在第 100 篇中已有详细讨论，这里从随机化算法的角度做一个总结。

5.1 费马小定理与伪素数

费马小定理：若 p 为素数，则对所有 1 ≤ a < p，a^{p-1} ≡ 1 (mod p)。

反过来，如果存在 a 使得 a^{n-1} ≢ 1 (mod n)，则 n 一定是合数。这个 a 被称为费马证人（Fermat witness）。

问题：有些合数 n 对所有 gcd(a,n) = 1 的 a 都满足费马小定理——Carmichael 数（如 561 = 3 × 11 × 17）。

5.2 Miller-Rabin 的改进

将 n-1 写成 2^s · d 的形式（d 为奇数）。如果 n 是素数，则对任意 a：

要么 a^d ≡ 1 (mod n)，要么存在 r ∈ {0, 1, …, s-1} 使得 a^{2r · d} ≡ -1 (mod n)。

// Miller-Rabin 素性测试
// 返回 1 表示"可能是素数"，0 表示"一定是合数"
typedef unsigned long long u64;

u64 mulmod(u64 a, u64 b, u64 m) {
    return (__uint128_t)a * b % m;
}

u64 powmod(u64 base, u64 exp, u64 mod) {
    u64 result = 1;
    base %= mod;
    while (exp > 0) {
        if (exp & 1)
            result = mulmod(result, base, mod);
        exp >>= 1;
        base = mulmod(base, base, mod);
    }
    return result;
}

int miller_rabin_witness(u64 a, u64 d, u64 n, int s) {
    u64 x = powmod(a, d, n);

    if (x == 1 || x == n - 1)
        return 0;  // 不是证人，n 可能是素数

    for (int r = 1; r < s; r++) {
        x = mulmod(x, x, n);
        if (x == n - 1)
            return 0;  // 不是证人
    }

    return 1;  // 是证人，n 一定是合数
}

int is_probable_prime(u64 n, int iterations) {
    if (n < 2) return 0;
    if (n == 2 || n == 3) return 1;
    if (n % 2 == 0) return 0;

    // 将 n-1 写成 2^s * d
    u64 d = n - 1;
    int s = 0;
    while (d % 2 == 0) {
        d /= 2;
        s++;
    }

    // 对于 n < 3,317,044,064,679,887,385,961,981，
    // 使用固定的前若干个素数作为基底即可确定性判断
    u64 deterministic_bases[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37};
    int num_bases = sizeof(deterministic_bases) / sizeof(deterministic_bases[0]);

    for (int i = 0; i < num_bases && i < iterations; i++) {
        u64 a = deterministic_bases[i];
        if (a >= n) continue;
        if (miller_rabin_witness(a, d, n, s)) {
            return 0;  // 一定是合数
        }
    }

    return 1;  // 高概率是素数
}

5.3 从随机化角度看 Miller-Rabin

Miller-Rabin 是典型的 Monte Carlo 单边错误算法：

如果输出”合数”，则 100% 正确（找到了证人）。
如果输出”素数”，可能错误。

单次测试的错误概率 ≤ 1/4（Rabin 证明了至少 3/4 的基底是证人）。k 次独立测试后，错误概率 ≤ (1/4)^k。

在实践中，对于 64 位整数，使用特定的 12 个基底可以实现确定性判断——这是一种”去随机化”。

六、分布式系统中的随机化

随机化在分布式计算中扮演着不可替代的角色。事实上，有些分布式问题被证明不存在确定性解（如异步共识），但随机化算法可以解决它们。

6.1 共识算法中的随机化：Ben-Or 协议

FLP 不可能性定理（1985）：在异步系统中，即使只有一个进程可能崩溃，也不存在能保证终止的确定性共识算法。

Ben-Or（1983）的随机化共识协议绕过了这个不可能性：

Ben-Or 协议（进程 i，输入 v_i）：
  r = 1  // 轮次
  while true:
    // 第一阶段：广播自己的值
    广播 (PROPOSE, r, v_i)
    等待收到 n-f 个 PROPOSE 消息
    if 收到的某个值 v 出现 > n/2 次:
      广播 (DECIDE, r, v)
    else:
      广播 (DECIDE, r, ?)  // 不确定

    // 第二阶段：尝试决定
    等待收到 n-f 个 DECIDE 消息
    if 收到的某个值 v（非 ?）出现 > f 次:
      v_i = v
      if v 出现 > n/2 次:
        输出 v 并终止
    else:
      v_i = 随机选 0 或 1  // 关键的随机化步骤

    r = r + 1

当进程无法从其他进程获得足够信息来做决定时，它随机选择一个值。这打破了可能的活锁。

期望轮数：O(2^n)（指数级），但对于恒定数量的故障，更优的随机化协议可以做到期望常数轮。

6.2 负载均衡：Power of Two Choices

问题：n 个球（任务）投入 n 个桶（服务器），如何最小化最大负载？

完全随机：每个球随机选一个桶。最大负载为 Θ(log n / log log n)。

Power of Two Choices：每个球随机选两个桶，放入负载较轻的那个。最大负载降为 O(log log n)。

Power of Two Choices:
  for each ball:
    i = 随机选桶
    j = 随机选桶（j ≠ i）
    将球放入 load[i] < load[j] ? i : j

这是一个指数级的改进，只需要一点额外的随机性（选两个而不是一个）。

直觉：当负载为 k 的桶数量为 n/e^k 时（完全随机的稳态），两个桶都负载 ≥ k 的概率为 (1/e^k)2 = 1/e^{2k}。这个双指数衰减导致了 O(log log n) 的最大负载。

这个结果在实际负载均衡系统中被广泛使用，例如： - Nginx 的 least_conn 策略的随机化变体 - 微服务框架中的”两次随机选择”负载均衡策略

6.3 指数退避

指数退避（Exponential Backoff）是分布式系统中最常见的随机化技术之一。当多个客户端竞争同一个资源时：

指数退避:
  for attempt = 1, 2, 3, ...:
    尝试获取资源
    if 成功:
      break
    等待 random(0, 2^attempt) 的时间

通过随机化等待时间，避免了所有客户端同步重试导致的”惊群效应”。

关于指数退避的详细分析，参见第 73 篇的讨论。

6.4 一致性哈希与虚拟节点

一致性哈希（Consistent Hashing）利用随机哈希函数将键和节点映射到环上。每个节点创建 O(log n) 个虚拟节点（随机位置），保证了负载的均匀分布。

当一个节点加入或离开时，只有 O(1/n) 比例的键需要重新映射——这远优于传统哈希的 O(1) 比例。

七、去随机化（Derandomization）

随机化算法虽然强大，但有时我们需要确定性保证。去随机化是将随机化算法转换为确定性算法的技术。

7.1 条件期望法

条件期望法（Method of Conditional Expectations）是最经典的去随机化技术。

基本思想：如果随机变量 X 的期望 E[X] ≤ c，那么存在某个特定的选择使得 X ≤ c。条件期望法通过逐步固定随机选择，确保每一步都维持这个保证。

例子——MAX-CUT 问题：

给定无向图 G，找一个割使得跨越割的边数最大。

随机化算法：每个节点独立地以 1/2 概率放入 S 或 T。

对于每条边 (u,v)：
  Pr[(u,v) 被割] = 1/2（u 和 v 在不同侧的概率）

期望割大小 = m/2

去随机化：逐个处理节点，每次选择使条件期望不减的一边。

// MAX-CUT 的条件期望法去随机化
void derandomized_max_cut(int n, int m, int edges[][2], int *side) {
    // side[i] = 0 或 1，表示节点 i 在哪一侧

    for (int v = 0; v < n; v++) {
        // 计算将 v 放入 0 侧和 1 侧的条件期望
        int cut_if_0 = 0, cut_if_1 = 0;

        for (int e = 0; e < m; e++) {
            int u = edges[e][0], w = edges[e][1];

            if (u == v || w == v) {
                int other = (u == v) ? w : u;
                if (other < v) {
                    // other 已经被分配了
                    if (side[other] != 0) cut_if_0++;  // v=0, other!=0 -> 被割
                    if (side[other] != 1) cut_if_1++;  // v=1, other!=1 -> 被割
                } else {
                    // other 尚未分配，贡献期望 1/2
                    // 两种选择的贡献相同，无需区分
                }
            }
        }

        // 选择使条件期望更大的一侧
        side[v] = (cut_if_1 >= cut_if_0) ? 1 : 0;
    }
}

这给出了一个确定性的、保证割 ≥ m/2 的算法，时间 O(nm)。

7.2 成对独立性与 k-wise 独立性

很多随机化算法并不需要完全独立的随机比特，只需要有限独立性。

成对独立（pairwise independent）：任意两个随机变量独立，但三个可能不独立。
k-wise 独立：任意 k 个随机变量独立。

用 O(k log n) 个真随机比特可以生成 n 个 k-wise 独立的随机变量。当 k 很小时（如 k=2 或 k=4），随机比特的数量大幅减少。

这种有限独立性对很多应用已经足够：

Schwartz-Zippel 只需要成对独立（对某些特殊情况）。
很多哈希分析只需要 O(1)-wise 独立。
Universal hashing 只需要成对独立。

7.3 伪随机生成器

如果一个函数 G: {0,1}^s → {0,1}^n（s << n）的输出对某类算法”看起来像”真随机，那么 G 是该类算法的伪随机生成器。

Nisan-Wigderson 构造：在某些复杂度假设下，可以用 O(log n) 个真随机比特”骗过”所有多项式时间算法。这意味着 BPP = P（如果这些假设成立）。

这是去随机化理论的终极目标：证明随机性在多项式时间计算中是不必要的。虽然这至今未被完全证明，但绝大多数复杂度理论家相信 BPP = P。

八、Chernoff 界与 Union Bound

分析随机化算法需要精确的概率尾界。Chernoff 界和 union bound 是两个最基本的工具。

8.1 Chernoff 界

设 X_1, X_2, …, X_n 是独立的 {0,1} 随机变量，X = ΣX_i，μ = E[X]。

上尾：对于 δ > 0：

Pr[X ≥ (1+δ)μ] ≤ (e^δ / (1+δ)^{1+δ})^μ

常用简化形式：

Pr[X ≥ (1+δ)μ] ≤ exp(-μδ²/3)    （0 < δ ≤ 1）
Pr[X ≥ (1+δ)μ] ≤ exp(-μδ/3)     （δ > 1）

下尾：对于 0 < δ < 1：

Pr[X ≤ (1-δ)μ] ≤ exp(-μδ²/2)

8.2 Chernoff 界的应用示例

随机化负载均衡：n 个球投入 n 个桶，每个桶的期望负载 μ = 1。

Pr[某个桶的负载 ≥ c·log(n)/log(log(n))] ≤ 1/n²

对所有 n 个桶取 union bound：

Pr[最大负载 ≥ c·log(n)/log(log(n))] ≤ n · 1/n² = 1/n

这就是为什么完全随机投球的最大负载是 Θ(log n / log log n)。

8.3 Union Bound（Boole 不等式）

对于任意事件 A_1, A_2, …, A_n：

Pr[A_1 ∪ A_2 ∪ ... ∪ A_n] ≤ Σ Pr[A_i]

虽然看起来粗糙，但在与 Chernoff 界结合时非常有效。

典型用法：证明”没有坏事发生”。如果有 n 个可能的坏事件，每个的概率 ≤ 1/n^2，则所有坏事件都不发生的概率 ≥ 1 - n · 1/n^2 = 1 - 1/n。

8.4 Chernoff 界的证明思路

使用矩母函数（Moment Generating Function）方法：

Pr[X ≥ a] = Pr[e^{tX} ≥ e^{ta}]          （t > 0，单调性）
           ≤ E[e^{tX}] / e^{ta}            （Markov 不等式）
           = ∏ E[e^{tX_i}] / e^{ta}        （独立性）

对每个 E[e^{tX_i}] 用 e^x ≤ 1 + x(e-1)（当 x ∈ {0,1}）来上界，然后对 t 取最优。

8.5 实际应用模板

在分析随机化算法时，一个常见的模板是：

1. 定义"坏事件" B_1, B_2, ..., B_k
2. 用 Chernoff 界证明每个 Pr[B_i] ≤ very_small
3. 用 union bound 证明 Pr[∪B_i] ≤ still_small
4. 结论：以高概率，所有坏事件都不发生

“高概率”（with high probability, w.h.p.）通常指概率 ≥ 1 - 1/n^c，其中 c 是可以通过调参来增大的常数。

九、完整实现：整合测试驱动

将前面各节的 Freivalds 验证和 Karger 最小割整合为一个可编译运行的测试程序。核心算法实现参见第二节和第四节，这里给出驱动代码和测试用例。

/* randomized_algo_demo.c
 * 编译：gcc -O2 -o demo randomized_algo_demo.c -lm
 * 包含：Freivalds 矩阵验证（第二节）+ Karger 最小割（第四节）
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <math.h>
#include <limits.h>

/* ---- Freivalds 矩阵乘法验证 ---- */
#define MAX_N 200

void mat_mul(int n, double A[][MAX_N], double B[][MAX_N], double C[][MAX_N]) {
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++) {
            C[i][j] = 0;
            for (int k = 0; k < n; k++)
                C[i][j] += A[i][k] * B[k][j];
        }
}

void mat_vec(int n, double M[][MAX_N], double *v, double *out) {
    for (int i = 0; i < n; i++) {
        out[i] = 0;
        for (int j = 0; j < n; j++)
            out[i] += M[i][j] * v[j];
    }
}

int freivalds_verify(int n, double A[][MAX_N], double B[][MAX_N],
                     double C[][MAX_N], int rounds) {
    double r[MAX_N], Br[MAX_N], ABr[MAX_N], Cr[MAX_N];
    for (int t = 0; t < rounds; t++) {
        for (int i = 0; i < n; i++) r[i] = rand() % 2;
        mat_vec(n, B, r, Br);
        mat_vec(n, A, Br, ABr);
        mat_vec(n, C, r, Cr);
        for (int i = 0; i < n; i++)
            if (fabs(ABr[i] - Cr[i]) > 1e-9) return 0;
    }
    return 1;
}

/* ---- Karger 最小割 ---- */
#define KMAX_V 500
#define KMAX_E 50000

typedef struct { int u, v; } KEdge;
typedef struct {
    int n, m;
    KEdge edges[KMAX_E];
    int par[KMAX_V], rnk[KMAX_V];
} KGraph;

int kfind(KGraph *g, int x) {
    while (g->par[x] != x) { g->par[x] = g->par[g->par[x]]; x = g->par[x]; }
    return x;
}

void kunite(KGraph *g, int x, int y) {
    int rx = kfind(g, x), ry = kfind(g, y);
    if (rx == ry) return;
    if (g->rnk[rx] < g->rnk[ry]) g->par[rx] = ry;
    else if (g->rnk[rx] > g->rnk[ry]) g->par[ry] = rx;
    else { g->par[ry] = rx; g->rnk[rx]++; }
    g->n--;
}

void kinit(KGraph *g, int n) {
    g->n = n; g->m = 0;
    for (int i = 0; i < n; i++) { g->par[i] = i; g->rnk[i] = 0; }
}

void kadd(KGraph *g, int u, int v) {
    g->edges[g->m++] = (KEdge){u, v};
}

int karger_once(KGraph *orig) {
    KGraph g; memcpy(&g, orig, sizeof(KGraph));
    for (int i = g.m - 1; i > 0; i--) {
        int j = rand() % (i + 1);
        KEdge t = g.edges[i]; g.edges[i] = g.edges[j]; g.edges[j] = t;
    }
    for (int p = 0; g.n > 2 && p < g.m; p++) {
        int u = kfind(&g, g.edges[p].u), v = kfind(&g, g.edges[p].v);
        if (u != v) kunite(&g, u, v);
    }
    int cut = 0;
    for (int i = 0; i < g.m; i++)
        if (kfind(&g, g.edges[i].u) != kfind(&g, g.edges[i].v)) cut++;
    return cut;
}

int karger_mincut(KGraph *g, int reps) {
    int best = INT_MAX;
    for (int i = 0; i < reps; i++) {
        int c = karger_once(g);
        if (c < best) best = c;
    }
    return best;
}

/* ---- 测试 ---- */
int main(void) {
    srand((unsigned)time(NULL));

    /* Freivalds 测试 */
    printf("=== Freivalds 矩阵乘法验证 ===\n");
    int n = 4;
    double A[MAX_N][MAX_N] = {{1,2,3,4},{5,6,7,8},{9,10,11,12},{13,14,15,16}};
    double B[MAX_N][MAX_N] = {{1,0,0,0},{0,1,0,0},{0,0,1,0},{0,0,0,1}};
    double C[MAX_N][MAX_N];
    mat_mul(n, A, B, C);
    printf("A*I == A*I ? %s\n", freivalds_verify(n, A, B, C, 20) ? "通过" : "失败");
    C[0][0] += 1.0;
    printf("A*I == (A*I+扰动) ? %s\n",
           freivalds_verify(n, A, B, C, 20) ? "误报" : "检测到不等");

    /* Karger 测试：K4 完全图，最小割 = 3 */
    printf("\n=== Karger 最小割 ===\n");
    KGraph g; kinit(&g, 4);
    kadd(&g,0,1); kadd(&g,0,2); kadd(&g,0,3);
    kadd(&g,1,2); kadd(&g,1,3); kadd(&g,2,3);
    printf("K4 最小割: %d（期望 3）\n", karger_mincut(&g, 48));

    /* 含桥图，最小割 = 1 */
    KGraph g2; kinit(&g2, 6);
    kadd(&g2,0,1); kadd(&g2,1,4); kadd(&g2,0,4);
    kadd(&g2,1,2); // 桥
    kadd(&g2,2,3); kadd(&g2,2,5); kadd(&g2,3,5);
    printf("含桥图最小割: %d（期望 1）\n", karger_mincut(&g2, 180));

    return 0;
}

十、工程实践中的陷阱

10.1 随机数生成器的选择

场景	推荐 PRNG	原因
算法竞赛/原型	rand()、mt19937	简单快速，足够用
生产环境算法	xoshiro256**、PCG	统计质量好，速度快
密码学相关	/dev/urandom、CSPRNG	安全性要求
需要可重现	任意，固定种子	调试方便
分布式系统	独立种子或中央种子	避免相关性

10.2 常见陷阱

陷阱	说明	后果
rand() % n 的偏差	当 RAND_MAX 不是 n 的倍数时有偏差	均匀性被破坏
忘记设置随机种子	每次运行相同的”随机”序列	退化为确定性最坏情况
多线程共享 PRNG	竞态条件或锁竞争	性能下降或结果错误
用 time(NULL) 做种子	同一秒内启动的多个进程种子相同	相关性导致算法失效
浮点精度问题	随机化算法中比较相等性	误判，尤其在 Schwartz-Zippel 中
不够多的重复次数	理论需要 O(n^2 log n) 但实践中偷工减料	错误概率超出预期

10.3 rand() % n 的偏差修正

// 有偏差的实现
int biased_random(int n) {
    return rand() % n;  // 当 RAND_MAX+1 不是 n 的倍数时有偏差
}

// 无偏差的实现（rejection sampling）
int uniform_random(int n) {
    int limit = RAND_MAX - (RAND_MAX % n);
    int r;
    do {
        r = rand();
    } while (r >= limit);
    return r % n;
}

10.4 线程安全的 PRNG

#include <pthread.h>

// 每个线程维护独立的 PRNG 状态
typedef struct {
    uint64_t state;
} ThreadRNG;

// SplitMix64：简单高效的 PRNG
uint64_t splitmix64_next(ThreadRNG *rng) {
    uint64_t z = (rng->state += 0x9e3779b97f4a7c15ULL);
    z = (z ^ (z >> 30)) * 0xbf58476d1ce4e5b9ULL;
    z = (z ^ (z >> 27)) * 0x94d049bb133111ebULL;
    return z ^ (z >> 31);
}

// 初始化：每个线程用不同的种子
void init_thread_rng(ThreadRNG *rng, int thread_id) {
    rng->state = (uint64_t)time(NULL) ^ ((uint64_t)thread_id << 32);
}

十一、随机化算法的哲学与个人思考

11.1 随机化不是偷懒

初学者常有一个误解：随机化算法是”碰运气”。事实恰恰相反。随机化算法的正确性分析往往比确定性算法更精细、更深刻。

我的理解是：确定性算法是”积极防御”——主动避开所有陷阱。随机化算法是”概率免疫”——不试图避开陷阱，而是证明掉入陷阱的概率极低。

这就像疫苗：不是让你永远不接触病毒，而是让你接触后不会生病的概率极高。

11.2 随机性是一种资源

在计算复杂度理论中，随机性被视为一种计算资源，就像时间和空间一样。BPP（有界错误概率多项式时间）是否等于 P，是理论计算机科学最重要的开放问题之一。

目前的主流猜想是 BPP = P，即随机性不能提供本质上的计算能力。但即使如此，随机性在实践中仍然极其有用：

它让算法更简单：随机化快速排序 vs 确定性 O(n log n) 排序。
它让算法更快：Karger 的实现比确定性最小割简洁得多。
它让分布式系统可行：没有随机性，异步共识不可能。

11.3 对抗性与平均情况

随机化算法的一个深刻优势：对手无法构造最坏情况输入。

对于确定性算法，如果对手知道算法的代码，就可以精心构造一个输入使算法最慢。但对于随机化算法，即使对手知道算法的代码，由于随机选择是在运行时做出的，对手无法预测。

这在安全性场景中尤为重要——哈希表的随机化种子就是一个例子。

11.4 我的工程准则

经过多年实践，我对随机化算法的使用有以下准则：

能用随机化就用随机化：除非有严格的最坏情况要求（如实时系统），随机化版本几乎总是更简单、更快。
不要低估错误概率：2^{-100} 的错误概率比硬件故障低得多。在实践中，与其担心 Miller-Rabin 的错误概率，不如担心宇宙射线翻转内存位。
警惕伪随机数质量：算法的正确性依赖于随机数的质量。劣质 PRNG 可能导致意想不到的相关性。在生产环境中，至少使用 PCG 或 xoshiro 系列。
可重现性很重要：总是记录随机种子。当出现 bug 时，能用相同的种子复现问题是无价的。
重复次数要有理论依据：不要拍脑袋决定”重复 100 次够了”。做一下概率计算，确保错误概率符合需求。

十二、总结与展望

随机化算法是算法设计者工具箱中最锋利的武器之一。本文覆盖了以下内容：

主题	核心要点
Las Vegas vs Monte Carlo	前者结果正确时间随机，后者时间确定结果可能错误
Schwartz-Zippel 引理	多项式零点概率 ≤ d/\|S\|，应用广泛
随机化 QuickSelect	期望 O(n)，比确定性 BFPRT 快 5 倍以上
Karger 最小割	随机收缩，成功概率 ≥ 2/n^2，Karger-Stein 改进到 O(n^2 log^3 n)
Miller-Rabin	单边错误 Monte Carlo，实践中几乎完美
分布式随机化	Ben-Or 共识、Power of Two Choices、指数退避
去随机化	条件期望法、有限独立性
分析工具	Chernoff 界 + Union Bound

随机化算法的发展远未结束。近年来的前沿方向包括：

量子随机化：量子计算天然提供真随机性。Grover 搜索和 Shor 算法可以被视为”量子随机化算法”。
差分隐私：在数据上添加随机噪声以保护隐私，同时保持统计有效性。本质上是一种随机化技术。
随机化数值线性代数：用随机投影进行矩阵分解（Randomized SVD），在大数据场景中大放异彩。
随机化数据结构：Count-Min Sketch、HyperLogLog 等概率数据结构，在流式计算中不可或缺。

记住：当你面对一个看起来很难的问题时，试着掷一枚硬币。

参考文献

Motwani, R., & Raghavan, P. (1995). Randomized Algorithms. Cambridge University Press.
Mitzenmacher, M., & Upfal, E. (2017). Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis. Cambridge University Press.
Karger, D. R. (1993). Global min-cuts in RNC, and other ramifications of a simple min-cut algorithm. SODA.
Karger, D. R., & Stein, C. (1996). A new approach to the minimum cut problem. Journal of the ACM, 43(4), 601-640.
Schwartz, J. T. (1980). Fast probabilistic algorithms for verification of polynomial identities. Journal of the ACM, 27(4), 701-717.
Freivalds, R. (1979). Fast probabilistic algorithms. MFCS, Lecture Notes in Computer Science, vol. 74.
Miller, G. L. (1976). Riemann’s hypothesis and tests for primality. Journal of Computer and System Sciences, 13(3), 300-317.
Rabin, M. O. (1980). Probabilistic algorithm for testing primality. Journal of Number Theory, 12(1), 128-138.
Ben-Or, M. (1983). Another advantage of free choice: Completely asynchronous agreement protocols. PODC.
Mitzenmacher, M. (2001). The power of two choices in randomized load balancing. IEEE Transactions on Parallel and Distributed Systems, 12(10), 1094-1104.

算法系列导航：上一篇：SIMD 算法设计模式 | 下一篇：竞争分析与在线算法

相关阅读：Treap 与跳表 | 最近点对与随机化几何算法

目录