随机化技巧

概述

前置知识：随机函数 和 概率初步

本文将对 OI/ICPC 中的随机化相关技巧做一个简单的分类，并对每个分类予以介绍。本文也将介绍一些在 OI/ICPC 中很少使用，但与 OI/ICPC 在风格等方面较为贴近的方法，这些内容前将用 (*) 标注。

这一分类并不代表广泛共识，也必定不能囊括所有可能性，因此仅供参考。

记号和约定：

  • \mathrm{Pr}[A] 表示事件 A 发生的概率。
  • \mathrm{E}[X] 表示随机变量 X 的期望。
  • 赋值号 := 表示引入新的量，例如 Y:=1926 表示引入值为 1926 的量 Y 。

用随机集合覆盖目标元素

庞大的解空间中有一个（或多个）解是我们想要的。我们可以尝试进行多次撒网，只要有一次能够网住目标解就能成功。

例：三部图的判定

问题

给定一张 n 个结点、 m 条边的简单无向图，用 RGB 三种颜色给每个结点染色 满足任意一对邻居都不同色，或者报告无解。

对每个点 v ，从 \{R,G,B\} 中等概率独立随机地选一种颜色 C_v ，并钦定 v 不 被染成 C_v 。最优解恰好符合这些限制的概率，显然是 \big(\frac 23\big)^n 。

在这些限制下，对于一对邻居 (u,v) ，“ u,v 不同色”的要求等价于以下这条“推出”关系：

  • 对于所有异于 C_u,C_v 的颜色 X ，若 u 被染成 X ，则 v 被染成 \{R,G,B\}\setminus\{X,C_v\} 。

于是我们可以对每个 v 设置布尔变量 B_v ，其取值表示 v 被染成两种剩余的颜色中的哪一种。借助 2-SAT 模型即可以 O(n+m) 的复杂度解决这个问题。

这样做，单次的正确率是 \big(\frac 23\big)^n 。将算法重复运行 -\big(\frac 32\big)^n\log \epsilon 次，只要有一次得到解就输出，这样即可保证 1-\epsilon 的正确率。（详见后文中“自然常数的使用”和“抽奖问题”）

回顾：本题中“解空间”就是集合 \{R,G,B\}^n ，我们每次通过随机施加限制来在一个缩小的范围内搜寻“目标解”——即合法的染色方案。

例：CodeChef SELEDGE

简要题意

给定一张点、边都有非负权值的无向图，找到一个大小 \leq K 的边集合 S ，以最大化与 S 相连的点的权值和减去 S 的边权和。一个点的权值只被计算一次。

观察：如果选出的边中有三条边构成一条链，则删掉中间的那条一定不劣；如果选出的边中有若干条构成环，则删掉任何一条一定不劣。

推论：最优解选出的边集，一定构成若干个不相交的菊花图（即直径不超过 2 的树）。

推论：最优解选出的边集，一定构成一张二分图。

我们对每个点等概率独立随机地染上黑白两种颜色之一，并要求这一染色方案，恰好也是最优解所对应的二分图的黑白染色方案。

尝试计算最优解符合这一要求的概率：

  • 考虑一张 n 个点的菊花图，显然它有 2 种染色方案，所以它被染对颜色的概率是 \dfrac 2{2^n}=2^{1-n} 。
  • 假设最优解中每个菊花的结点数分别为 a_1,\cdots,a_l ，则一定有 (a_1-1)+\cdots+(a_l-1)\leq K ，其中 K 表示最多能够选出的边数。
  • 从而所有菊花都被染对颜色的概率是 2^{1-a_1}\cdots 2^{1-a_l}\geq 2^{-K} 。

在上述要求下，尝试建立费用流模型计算最优答案：

  • 建立二分图，白点在左侧并与 S 相连，黑点在右侧并与 T 相连。
    • 对于白点 v ，从 S 向它连一条容量为 1、费用为 -A_v 的边，和一条容量为 \infty 、费用为 0 的边。
    • 对于黑点 v ，从它向 T 连一条容量为 1、费用为 -A_v 的边，和一条容量为 \infty 、费用为 0 的边。
  • 对于原图中的边 (u,v,B) 满足 u 为白色、 v 为黑色，连一条从 u 到 v 的边，容量为 1，费用为 B 。
  • 在该图中限制流量不超过 K ，则最小费用的相反数就是答案。

用 SPFA 费用流求解的话，复杂度是 O\big(K^2(n+m)\big) ，证明：

  • 首先，显然 SPFA 的运行次数 \leq K 。
  • 然后，在一次 SPFA 中，任何一个结点至多入队 O(K) 次。这是因为：
    • 任意时刻有流量的边不会超过 3K 条，否则就意味着在原图中选了超过 K 条边。
    • 对于任何一条长为 L 的增广路，其中至少有 \dfrac L2-2 条边是某条有流量的边的反向边，因为正向边都是从图的左侧指向右侧，只有这些反向边才会从右侧指向左侧。
    • 综合以上两条，得到任意一条增广路的长度不超过 6K+4 。
  • 综上，复杂度是 O\big(K^2(n+m)\big) 。

和上一题类似，我们需要把整个过程重复 -2^K \log\epsilon 次以得到 1-\epsilon 的正确率。总复杂度 O\big(2^KK^2(n+m)\cdot -\log\epsilon\big) 。

用随机元素命中目标集合

我们需要确定一个集合中的任意一个元素，为此我们随机选取元素，以期能够恰好命中这一集合。

例：Gym 101550I

简要题意

有一张图形如：两条平行的链，加上连接两链的两条平行边。给定这张图上的若干条简单路径（每条路径表示一次通话），请你选择尽量少的边放置窃听器，以使得每条给定的路径上都有至少一个窃听器。

整张图可以拆分为一个环加上四条从环伸出去的链。对于这四条链中的任何一条（记作 C ），考虑在这条链上如何放置窃听器，容易通过贪心算法得到满足以下条件的方案：

  • 在拦截所有 C 内部进行的通话的前提下，用的窃听器数量最少。
  • 在上一条的前提下，使得 C 上的窃听器离环的最短距离尽可能小。
    • 作这一要求的目的是尽可能地拦截恰有一个端点在 C 内部的通话。

接着考虑链与环相接处的共计 4 条边，我们暴力枚举这些边上有没有放窃听器。显然，如果想要拦截跨越链和环的通话，在这 4 条边上放窃听器一定是最优的。现在，我们可以把通话线路分为以下几种：

  1. 完全在链上的通话线路。这些线路一定已经被拦截，故可以忽略。
  2. 跨越链和环，且已经被拦截的通话线路。它们可以忽略。
  3. 跨越链和环，且未被拦截的通话线路。我们可以直接截掉它在链上的部分（因为链上的窃听器放置方案已经固定了），只保留环上的部分。
  4. 完全在环上的通话线路。

至此，问题转化成了环上的问题。

设最优解中在环上的边集 S 上放置了窃听器，如果我们已经确定了 S 中的任何一个元素 e ，就可以：

  • 先在 e 处断环为链。
  • 然后从 e 开始贪心，不断找到下一个放置窃听器的边。注意到如果经过合适的预处理，贪心的每一步可以做到 O(1) 的复杂度。
  • 从而以 O(|S|) 的复杂度解决问题。

我们考虑随机选取环上的一条边 e' ，并钦定 e'\in S 再执行上述过程，重复多次取最优。

分析单次复杂度：

  • 观察：记 S' 表示所有选取了 e' 的方案中的最优解，则 |S'|\leq |S|+1 。
  • 从而单次复杂度 O(|S'|)=O(|S|) 。

分析正确率：

  • 显然单次正确率 \dfrac {|S|}n ，其中 n 表示环长。
  • 所以需要重复 -\dfrac n{|S|}\log\epsilon 次以得到 1-\epsilon 的正确率。

综上，该算法的复杂度 O\big(|S|\cdot -\dfrac n{|S|}\log\epsilon\big)=O(-n\log\epsilon) 。

例：CSES 1685 New Flight Routes

简要题意

给定一张有向图，请你加最少的边使得该图强连通，需 输出方案。

先对原图进行强连通缩点。我们的目标显然是使每个汇点能到达每个源点。

不难证明，我们一定只会从汇点到源点连边，因为任何其他的连边，都能对应上一条不弱于它的、从汇点到源点的连边。

我们的一个核心操作是，取汇点 t 和源点 s （它们不必在同一个弱连通分量里），连边 t\to s 以 使得 s 和 t 都不再是汇点或源点（记作目标 I）。理想情况下这种操作每次能减少一个汇点和一个源点，那我们不断操作直到只剩一个汇点或只剩一个源点，而这样的情形就很平凡了。由此，我们猜测答案是源点个数与汇点个数的较大值。

不难发现，上述操作能够达到目标 I 的充要条件是： t 拥有 s 以外的前驱、且 s 拥有 t 以外的后继。可以证明（等会会给出证明），对于任意一张有着至少两个源点和至少两个汇点的 DAG，都存在这样的 (s,t) ；但存在性的结论无法帮助我们构造方案，还需做其他分析。

  • 有了这个充要条件还难以直接得到算法，主要的原因是连边 t\to s 后可能影响其他 (s',t') 二元组的合法性，这个比较难处理。

注意到我们关于源汇点间的关系知之甚少（甚至连快速查询一对 s-t 间是否可达都需要 dfs + bitset 预处理，而时限并不允许这么做），这提示我们需要某种非常一般和强大的性质。

观察：不满足目标 I 的 (s,t) 至多有 n+m-1 对，其中 n 表示源点个数， m 表示汇点个数。

  • 理由：对于每一对这样的 (s,t) ，若把它看成 s,t 间的一条边，则所有这些边构成的图形如若干条不相交的链，于是边数不超过点数减一。
  • 作出这一观察的动机是，要想将存在性结论应用于算法，前置步骤往往是把定性的结果加强为定量的结果。

推论：等概率随机选取 (s,t) ，满足前述要求的概率 \geq \dfrac {(n-1)(m-1)}{nm} 。

  • 注意到这个结论严格强于先前给出的存在性结论。

推论：等概率独立随机地连续选取 \dfrac {\min(n,m)}2 对不含公共元素的 (s,t) ，并对它们 依次 操作（即连边 t\to s ），则这些操作全部满足目标 I 的概率 \geq \dfrac 14 。

  • 理由：
\begin{aligned} &\phantom{=\ }\dfrac {(n-1)(m-1)}{nm}\cdot\dfrac{(n-2)(m-2)}{(n-1)(m-1)}\cdots\dfrac{(n-k)(m-k)}{(n-k+1)(m-k+1)}\\ &=\dfrac{(n-k)(m-k)}{nm}\\ &\geq \dfrac 14 \end{aligned}

而连续选完 k 对 (s,t) 后判断它们是否全部满足目标 I 很简单，只要再跑一遍强连通缩点，判断一下 n,m 是否都减小了 k 即可。注意到若每次减少 k=\dfrac{\min(n,m)}2 ，则 \min(n,m) 必在 O\big(\log(n+m)\big) 轮内变成 1，也就转化到了平凡的情况。

算法伪代码 
while(n>1 and m>1):
    randomly choose k=min(n,m)/2 pairs (s,t)
    add edge t->s for all these pairs
    if new_n>n-k or new_m>m-k:
        roll_back()
solve_trivial()

复杂度 O\big((|V|+|E|) \log |V|\big) 。

回顾：我们需要确定任意一对能够实现目标 I 的二元组 (s,t) ，为此我们随机选择 (s,t) 。

用随机化获得随机数据的性质

如果一道题的数据随机生成，我们可能可以利用随机数据的性质解决它。而在有些情况下，即使数据并非随机生成，我们也可以通过随机化来给其赋予随机数据的某些特性，从而帮助解决问题。

例：随机增量法

随机生成的元素序列可能具有“前缀最优解变化次数期望下很小”等性质，而随机增量法就通过随机打乱输入的序列来获得这些性质。

详见 随机增量法。

例：TopCoder MagicMolecule 随机化解法

简要题意

给定一张 n 个点、带点权的无向图，在其中所有大小不小于 \dfrac {2n}3 的团中，找到点权和最大的那个。

n\leq 50

不难想到折半搜索。把点集均匀分成左右两半 V_L,V_R （大小都为 \dfrac n2 ），计算数组 f_{L,k} 表示点集 L\subseteq V_L 中的所有 \geq k 元团的最大权值和。接着我们枚举右半边的每个团 C_R ，算出左半边有哪些点与 C_R 中的所有点相连（这个点集记作 N_L ），并用 f_{N_L,\frac 23 n-|C_R|}+\textit{value}(C_R) 更新答案。

  • 注意到可以 O(1) 转移每一个 f_{L,k} 。具体地说，取 d 为 L 中的任意一个元素，然后分类讨论：
    • 假设最优解中 d 不在团中，则从 f_{L\setminus \{d\},k} 转移而来。
    • 假设最优解中 d 在团中，则从 f_{L\cap N(d),k}+\textit{value}(d) 转移而来，其中 N(d) 表示 d 的邻居集合。
    • 别忘了还要用 f_{L,k+1} 来更新 f_{L,k} 。

这个解法会超时。尝试优化：

  • 平分点集时均匀随机地划分。这样的话，最优解的点集 C_{res} 以可观的概率也被恰好平分（即 |C_{res}\cap V_L|=|C_{res}\cap V_R| ）。
    • 当然， |C_{res}| 可能是奇数。简单起见，这里假设它是偶数；奇数的情况对解法没有本质改变。
    • 实验发现，随机尝试约 20 次就能以很大概率有至少一次满足该性质。也就是说，如果我们的算法依赖于“ C_{res} 被平分”这一性质，则将算法重复执行 20 次取最优，同样也能保证以很大概率得到正确答案。
  • 有了这一性质，我们就可以直接钦定左侧团 L 、右侧团 C_R 的大小都 \geq \dfrac n3 。这会对复杂度带来两处改进：
    • f 可以省掉记录大小的维度。
    • 因为只需考虑大小 \geq \dfrac n3 的团，所以需要考虑的左侧团 L 和 右侧团 C_R 的数量也大大减少至约 1.8\cdot 10^6 。
  • 现在的瓶颈变成了求单侧的某一子集的权值和，因为这需要 O\big(2^{|V_L|}+2^{|V_R|}\big) 的预处理。
    • 解决方案：在 V_L,V_R 内部再次折半；当查询一个子集的权值和时，将这个子集分成左右两半查询，再把答案相加。
  • 这样即可通过本题。

回顾：一个随机的集合有着“在划分出的两半的数量差距不会太悬殊”这一性质，而我们通过随机划分获取了这个性质。

随机化用于哈希

例：UOJ #207 共价大爷游长沙

简要题意

维护一棵动态变化的树，和一个动态变化的结点二元组集合。你需要支持：

  • 删边、加边。保证得到的还是一棵树。
  • 加入/删除某个结点二元组。
  • 给定一条边 e ，判断是否对于集合中的每个结点二元组 (s,t) ， e 都在 s,t 间的简单路径上。

对图中的每条边 e ，我们定义集合 S_e 表示经过该边的关键路径（即题中的 (a,b) ）集合。考虑对每条边动态维护集合 S_e 的哈希值，这样就能轻松判定 S_e 是否等于全集（即 e 是否是“必经之路”）。

哈希的方式是，对每个 (a,b) 赋予 2^{64} 以内的随机非负整数 H_{(a,b)} ，然后一个集合的哈希值就是其中元素的 H 值的异或和。

这样的话，任何一个固定的集合的哈希值一定服从 R:=\big\{0,1,\cdots,2^{64}-1\big\} 上的均匀分布（换句话说，哈希值的取值范围为 R ，且取每一个值的概率相等）。这是因为：

  1. 单个 H_{(a,b)} 显然服从均匀分布。
  2. 两个独立且服从 R 上的均匀分布的随机变量的异或和，一定也服从 R 上的均匀分布。自证不难。

从而该算法的正确率是有保障的。

至于如何维护这个哈希值，使用 LCT 即可。

例：CodeChef PANIC 及其错误率分析

本题的大致解法：

  1. 可以证明1 S(N) 服从一个关于 N 的 O(K) 阶线性递推式。
  2. 用 BM 算法求出该递推式。
  3. 借助递推式，用凯莱哈密顿定理计算出 S(N) 。

这里仅关注第二部分，即如何求一个矩阵序列的递推式。所以我们只需考虑下述问题：

问题

给定一个矩阵序列，该序列在模 P:=998244353 意义下服从一个齐次线性递推式（递推式中的数乘和加法运算定义为矩阵的数乘和加法），求出最短递推式。

如果一系列矩阵服从一个递推式 F ，那么它的每一位也一定服从 F 。然而，如果对某一位求出最短递推式 F' ，则 F' 可能会比 F 更短，从而产生问题。

解决方案：给矩阵的每一位 (i,j) 赋予一个 <P 的随机权值 x_{i,j} ，然后对于序列中每个矩阵计算其所有位的加权和模 P 的结果，再把每个矩阵算出的这个数连成一个数列，最后我们对所得数列运行 BM 算法。

错误率分析：

  • 假设上述做法求得了不同于 F （且显然也不长于 F ）的 l 阶递推式 F' 。
  • 因为矩阵序列不服从 F' ，所以一定存在矩阵中的某个位置 (i,j) ，满足该位置对应的数列 S_{i,j} 在某个 N 处不服从 F' 。也就是说：
S(N)_{i,j}-F'_1S(N-1)_{i,j}-\cdots-F'_lS(N-l)_{i,j}\not\equiv 0\pmod {P}
  • 假设 (i,j) 是唯一的不服从的位置，则一定有：
T_{i,j}:=\Big(x_{i,j}\cdot\big(S(N)_{i,j}-F'_1S(N-1)_{i,j}-\cdots-F'_lS(N-l)_{i,j}\big)\bmod P\Big)=0
  • 显然这仅当 x_{i,j}=0 时才成立，概率 P^{-1} 。
  • 如果有多个不服从的位置呢？
    • 对每个这样的位置 (i,j) ，易证 T_{i,j} 服从 R:=\{0,1,\cdots,P-1\} 上的均匀分布。
    • 若干个互相独立的、服从 R 上的均匀分布的随机变量，它们在模意义下的和，依然服从 R 上的均匀分布。自证不难。
    • 从而这种情况下的错误率也是 P^{-1} 。

例：UOJ #552 同构判定鸭 及其错误率分析

简要题意

给定两张边权为小写字母的有向图 G_0,G_1 ，你要对这两张图分别算出「所有路径对应的字符串构成的多重集」（可能是无穷集），并判断这两个多重集是否相等。如果不相等，你要给出一个最短的串，满足它在两个多重集中的出现次数不相等。

令 f_{K,i,j} 表示图 G_K 中从点 i 开始的所有长为 j 的路径，这些路径对应的所有字符串构成的多重集的哈希值。按照 j 升序考虑每个状态，转移时枚举 i 的出边并钦定该边为路径上的第一条边。

要判断是否存在长度 =L 的坏串，只需把 \{f_{0,*,L}\} 和 \{f_{1,*,L}\} 各自“整合”起来再比较即可（通配符 * 这里表示每一个结点，例如 \{f_{0,*,L}\} 表示全体 f_{0,i,L} 构成的集合，其中 i 取遍所有结点）。官方题解2中证明了最短坏串（如果存在的话）长度一定不超过 n_1+n_2 ，所以这个解法的复杂度是可靠的。

接下来考虑具体的哈希方式。注意到常规的哈希方法——即把串 a_1a_2\cdots a_k 映射到 \big(a_1+Pa_2+P^2a_3+\cdots+P^{k-1}a_k\big)\bmod Q 上、再把多重集的哈希值定为其中元素的哈希值之和模 Q ——在这里是行不通的。一个反例是，集合 {"ab","cd"} 与集合 {"cb","ad"} 的哈希值是一样的，不论 P,Q 如何取值。

上述做法的问题在于，一个串的哈希值是一个和式，从而其中的每一项可以拆出来并重组。为避免这一问题，我们考虑把哈希值改为一个连乘式。此外，乘法交换律会使得不同的位不可区分，为避免这一点我们要为不同的位赋予不同的权值。

对每一个二元组 (c,j) （其中 c 为字符， j 为整数表示 c 在某个串中的第几位）我们都预先生成一个随机数 x_{c,j} 。然后我们把串 a_1a_2\cdots a_k 映射到 x_{a_1,1}x_{a_2,2}\cdots x_{a_k,k}\bmod Q 上（其中 Q 为 随机选取 的质数）、再把多重集的哈希值定为其中元素的哈希值之和模 Q 。接下来分析它的错误率。

(*)Schwartz-Zippel 引理

令 f\in F[z_1,\cdots,z_k] 为域 F 上的 k 元 d 次非零多项式，令 S 为 F 的有限子集，则至多有 d\cdot |S|^{k-1} 组 (z_1,\cdots,z_k)\in S^k 满足 f(z_1,\cdots,z_k)=0 。

如果你不知道域是什么

你只需记得这两样东西都是域：

  1. 模质数的剩余系，以及其上的各种运算。
  2. 实数集，以及其上的各种运算。

推论：若 z_1,\cdots,z_k 都在 S 中等概率独立随机选取，则 \mathrm{Pr}\big[f(z_1,\cdots,z_k)=0\big]\leq \dfrac d{|S|} 。

记 F 为模 Q 的剩余系所对应的域，则对于一个 L\leq n_1+n_2 ， \sum\limits_i f_{0,i,L} 和 \sum\limits_i f_{1,i,L} 就分别对应着一个 F 上关于变元集合 \{x_{*,*}\} 的 L 次多元多项式，不妨将这两个多项式记为 P_0,P_1 。

假如两个不同的字符串多重集的哈希值相同，则有两种可能：

  1. P_0\equiv P_1\pmod {Q} ，即 P_0,P_1 的每一项系数在模 Q 意义下都对应相等。
  2. P_0\not\equiv P_1\pmod {Q}, P_0(x_{*,*})\equiv P_1(x_{*,*})\pmod {Q} ，即 P_0,P_1 虽然不恒等，但我们选取的这一组 \{x_{*,*}\} 恰好使得它们在此处的点值相等。

分析前者发生的概率：

  • 观察：对于任意的 A\neq B; A,B\leq N 和随机选取的质数 Q\leq Q_{max} ，一定有：
\mathrm{Pr}\big[A\equiv B\pmod {Q}\big]=O\Big(\dfrac{\log N \log Q_{max}}{Q_{max}}\Big)
  • 这是因为：使 A\equiv B 成立的 Q 一定满足 Q\big|(A-B) ，这样的 Q 有 \omega(A-B)\leq \log_2 N 个；而由质数定理， Q_{max} 以内不同的质数又有 \Theta\Big(\dfrac {Q_{max}}{\log Q_{max}}\Big) 个。将两者相除即可得到上式。
  • 在上述观察中取 A,B （满足 A\neq B ）为某一特定项在 P_0,P_1 中的系数（也就等于该项对应的串在 G_0,G_1 中的出现次数），则易见 A,B\leq (m_1+m_2)^{L} ，得到：
\mathrm{Pr}\big[A\equiv B\pmod {Q}\big]=O\Big(\dfrac{L\log (m_1+m_2) \log Q_{max}}{Q_{max}}\Big)
  • 所以取 Q_{max}\approx 10^{12} 就绰绰有余。如果机器无法支持这么大的整数运算，可以用双哈希代替。

分析后者发生的概率：

  • 在 Schwartz-Zippel 引理中：
    • 取域 F 为模 Q 的剩余系对应的域
    • 取 f(x_{*,*})=P_0(x_{*,*})-P_1(x_{*,*}) 为 L 次非零多项式
    • 取 S=F
  • 得到：所求概率 \leq \dfrac LQ 。

注意到我们需要对每个 L 都能保证正确性，所以要想保证严谨的话还需用 Union Bound（见后文）说明一下。

实践上我们不必随机选取模数，因为——比如说——用自己的生日做模数的话，实际上已经相当于随机数了。

例：(*）子矩阵不同元素个数

问题

给定 n\times m 的矩阵， q 次询问一个连续子矩阵中不同元素的个数，要求在线算法。

允许 \epsilon 的相对误差和 \delta 的错误率，换句话说，你要对至少 (1-\delta)q 个询问给出离正确答案相对误差不超过 \epsilon 的回答。

n\cdot m\leq 2\cdot10^5;q\leq 10^6;\epsilon=0.5,\delta=0.2

引理：令 X_{1\cdots k} 为互相独立的随机变量，且取值在 [0,1] 中均匀分布，则 \mathrm{E}\big[\min\limits_i X_i\big]=\dfrac 1{k+1} 。

  • 证明：考虑一个单位圆，其上分布着 相对位置 均匀随机的 k+1 个点，分别在位置 0,X_1,X_2,\cdots,X_k 处。那么 \min\limits_i X_i 就等于 k+1 段空隙中特定的一段的长度。而因为这些空隙之间是“对称”的，所以其中任何一段特定空隙的期望长度都是 \dfrac 1{k+1} 。

我们取 k 为不同元素的个数，并借助上述引理来从 \min\limits_i X_i 反推得到 k 。

考虑采用某个哈希函数，将矩阵中每个元素都均匀、独立地随机映射到 [0,1] 中的实数上去，且相等的元素会映射到相等的实数。这样的话，一个子矩阵中的所有元素对应的那些实数，在去重后就恰好是先前的集合 \{X_1,\cdots,X_k\} 的一个实例，其中 k 等于子矩阵中不同元素的个数。

于是我们得到了算法：

  1. 给矩阵中元素赋 [0,1] 中的哈希值。为保证随机性，哈希函数可以直接用 map 和随机数生成器实现，即每遇到一个新的未出现过的值就给它随机一个哈希值。
  2. 回答询问时设法求出子矩阵中哈希值的最小值 M ，并输出 \dfrac 1M-1 。

然而，这个算法并不能令人满意。它的输出值的期望是 \mathrm{E}\Big[\dfrac 1{\min\limits_i X_i}-1\Big] ，但事实上这个值并不等于 \dfrac 1{\mathrm{E}\big[\min\limits_i X_i\big]}-1=k ，而（可以证明）等于 \infty 。

也就是说，我们不能直接把 \min\limits_i X_i 的单次取值放在分母上，而要先算得它的期望，再把期望值放在分母上。

怎么算期望值？多次随机取平均。

我们用 C 组不同的哈希函数分别执行前述过程，回答询问时计算出 C 个不同的 M 值，并算出其平均数 \overline M ，然后输出 \big(\overline M\big)^{-1}-1 。

实验发现取 C\approx 80 即可满足要求。严格证明十分繁琐，在此略去。

最后，怎么求子矩阵最小值？用二维 S-T 表即可，预处理 O(nm\log n\log m) ，回答询问 O(1) 。

随机化在算法中的其他应用

随机化的其他作用还包括：

  • 防止被造数据者用针对性数据卡掉。例如在搜索时随机打乱邻居的顺序。
  • 保证算法过程中进行的“操作”具有（某种意义上的）均匀性。例如 模拟退火 算法。

在这些场景下，随机化常常（但并不总是）与乱搞、骗分等做法挂钩。

例：「TJOI2015」线性代数

本题的标准算法是网络流，但这里我们采取这样的乱搞做法：

  • 每次随机一个位置，把这个位置取反，判断大小并更新答案。
代码 
#include <algorithm>
#include <cstdlib>
#include <iostream>

int n;

int a[510], b[510], c[510][510], d[510];
int p[510], q[510];

int maxans = 0;

void check() {
  memset(d, 0, sizeof d);
  int nowans = 0;
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++) d[i] += a[j] * c[i][j];
  for (int i = 1; i <= n; i++) nowans += (d[i] - b[i]) * a[i];
  maxans = std::max(maxans, nowans);
}

int main() {
  srand(19260817);
  std::cin >> n;
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++) std::cin >> c[i][j];
  for (int i = 1; i <= n; i++) std::cin >> b[i];
  for (int i = 1; i <= n; i++) a[i] = 1;
  check();
  for (int T = 1000; T; T--) {
    int tmp = rand() % n + 1;
    a[tmp] ^= 1;
    check();
  }
  std::cout << maxans << '\n';
}

例：(*）随机堆

可并堆最常用的写法应该是左偏树了，通过维护树高让树左偏来保证合并的复杂度。然而维护树高有点麻烦，我们希望尽量避开。

那么可以考虑使用随机堆，即不按照树高来交换儿子，而是随机交换。

代码 
struct Node {
  int child[2];
  long long val;
} nd[100010];
int root[100010];

int merge(int u, int v) {
  if (!(u && v)) return u | v;
  int x = rand() & 1, p = nd[u].val > nd[v].val ? u : v;
  nd[p].child[x] = merge(nd[p].child[x], u + v - p);
  return p;
}

void pop(int &now) { now = merge(nd[now].child[0], nd[now].child[1]); }

随机堆对堆的形态没有任何硬性或软性的要求，合并操作的期望复杂度对任何两个堆（作为 merge 函数的参数）都成立。下证。

期望复杂度的证明

将证，对于任意的堆 A ，从根节点开始每次随机选左或者右走下去（直到无路可走），路径长度（即路径上的结点数）的期望值 h(A)\leq\log_2 (|A|+1) 。

  • 注意到在前述过程中合并堆 A,B 的期望复杂度是 O\big(h(A)+h(B)\big) 的，所以上述结论可以保证随机堆的期望复杂度。

证明采用数学归纳。边界情况是 A 为空图，此时显然。下设 A 非空。

假设 A 的两个子树分别为 L,R ，则：

\begin{align} h(A) &=1+\frac{h(L)+h(R)}2 \\&\leq1+\frac{\log_2(|L|+1)+\log_2(|R|+1)}2 \\&=\log_2{2\sqrt{(|L|+1)(|R|+1)}} \\&\leq\log_2{\frac{2\big((|L|+1)+(|R|+1)\big)}2} \\&=\log_2{(|A|+1)} \end{align}

证毕。

与随机性有关的证明技巧

以下列举几个比较有用的技巧。

自然，这寥寥几项不可能就是全部；如果你了解某种没有列出的技巧，那么欢迎补充。

概率上界的分析

随机算法的正确性或复杂度经常依赖于某些“坏事件”不发生或很少发生。例如，快速排序的复杂度依赖于“所选的 pivot 元素几乎是最小或最大元素”这一坏事件较少发生。

本节介绍几个常用于分析“坏事件”发生概率的工具。

工具

Union Bound：记 A_{1\cdots m} 为坏事件，则

\mathrm{Pr}\Big[\bigcup\limits_{i=1}^m A_i \Big]\leq \sum\limits_{i=1}^m \mathrm{Pr}[A_i]

  • 即：坏事件中至少一者发生的概率，不超过每一个的发生概率之和。

  • 证明：回到概率的定义，把事件看成单位事件的集合，发现这个结论是显然的。

  • 这一结论还可以稍作加强：

    • 坏事件中至少一者发生的概率，不小于 每一个的发生概率之和，减掉每两个同时发生的概率之和。
    • 坏事件中至少一者发生的概率，不超过 每一个的发生概率之和，减掉每两个同时发生的概率之和，加上每三个同时发生的概率之和。
    • ……
    • 随着层数越来越多，交替出现的上界和下界也越来越紧。这一系列结论形式上类似容斥原理，证明过程也和容斥类似，这里略去。

自然常数的使用： \Big(1-\dfrac 1n\Big)^n\leq \dfrac 1e,\forall n\geq1

  • 左式关于 n\geq 1 单调递增且在 +\infty 处的极限是 \dfrac 1e ，因此有这个结论。

  • 这告诉我们，如果 n 个互相独立的坏事件，每个的发生概率为 1-\dfrac 1n ，则它们全部发生的概率至多为 \dfrac 1e 。

(*) Hoeffding 不等式：若 X_{1\cdots n} 为互相独立的实随机变量且 X_i\in [a_i,b_i] ，记随机变量 X:=\sum\limits_{i=1}^n X_i ，则

\mathrm{Pr}\Big[\big|X-\mathrm{E}[X]\big|\geq t\Big]\leq2\exp {-\dfrac {t^2}{\sum\limits_{i=1}^n (b_i-a_i)^2}}
  • 这一不等式限制了随机变量偏离其期望值的程度。从经验上讲，如果 \mathrm{E}[X] 不太接近 a_1+\cdots+a_n ，则该不等式给出的界往往相对比较紧；如果非常接近的话（例如在 UOJ #72 全新做法 中），给出的界则往往很松，此时更好的选择是使用 (*)Chernoff Bound，它和 Hoeffding 不等式同属于 (*)Concentration Inequality。

例子

例：抽奖问题

一个箱子里有 n 个球，其中恰有 k 个球对应着大奖。你要进行若干次独立、等概率的随机抽取，每次抽完之后会把球放回箱子。请问抽多少次能保证以至少 1-\epsilon 的概率，满足 每一个 奖球都被抽到至少一次？给出一个上界即可，不要求精确答案。

与该问题类似的模型经常出现在随机算法的复杂度分析中。

解答

假如只有一个奖球，则抽取 M:=-n\log\epsilon 次即可保证，因为 M 次全不中的概率 \Big(1-\dfrac 1n\Big)^{n\cdot (-\log\epsilon)}\leq e^{\log\epsilon}=\epsilon 。

现在有 k>1 个奖球，那么根据 Union Bound，我们只需保证每个奖球被漏掉的概率都不超过 \dfrac \epsilon k 即可。于是答案是 -n\log\dfrac \epsilon k 。

例：(*)随机选取一半元素

给出一个算法，从 n 个元素中等概率随机选取一个大小为 \dfrac n2 的子集，保证 n 是偶数。你能使用的唯一的随机源是一枚均匀硬币，同时请你尽量减少抛硬币的次数（不要求最少）。

解法

首先可以想到这样的算法：

  • 通过抛 n 次硬币，可以从所有子集中等概率随机选一个。
  • 不断重复这一过程，直到选出的子集大小恰好为 \dfrac n2 。
    • 注意到大小为 \dfrac n2 的子集至少占所有子集的 \dfrac 1n ，因此重复次数的期望值 \leq n 。

这一算法期望需要抛 n^2 次硬币。

另一个算法：

  • 我们可以通过抛期望 2\lceil\log_2 n\rceil 次硬币来实现随机 n 选 1。
    • 具体方法：随机生成 \lceil\log_2 n\rceil 位的二进制数，如果大于等于 n 则重新随机，否则选择对应编号（编号从 0 开始）的元素并结束过程。
  • 然后我们从所有元素中选一个，再从剩下的元素中再选一个，以此类推，直到选出 \dfrac n2 个元素为止。

这一算法期望需要抛 n\lceil\log_2 n\rceil 次硬币。

将两个算法缝合起来：

  • 先用第一个算法随机得到一个子集。
  • 如果该子集大小不到 \dfrac n2 ，则利用第二个算法不断添加元素，直到将大小补到 \dfrac n2 。
  • 如果该子集大小超过 \dfrac n2 ，则利用第二个算法不断删除元素，直到将大小削到 \dfrac n2 。

尝试分析第二、第三步所需的操作次数（即添加/删除元素的次数）：

  • 记 01 随机变量 X_i 表示 i 是否被选入初始的子集，令 X:=X_1+\cdots+X_n 表示子集大小，则第二、第三步所需的操作次数等于 \big|X-\mathrm{E}[X]\big| 。在 Hoeffding 不等式中取 t=c\cdot\sqrt n （其中 c 为任意常数），得到 \mathrm{Pr}\Big[\big|X-\mathrm{E}[X]\big|\geq t\Big]\leq 2e^{-c^2} 。也就是说，我们可以通过允许 \Theta(\sqrt n) 级别的偏移，来得到任意小的常数级别的失败概率。

至此我们已经说明：该算法可以以很大概率保证抛硬币次数在 n+\Theta(\sqrt n\log n) 以内。

  • 其中 n 来自获得初始子集的抛硬币次数； \Theta(\sqrt n\log n) 是 \Theta(\sqrt n) 次添加/删除元素的总开销。
计算期望复杂度

我们再从另一个角度分析，尝试计算该算法的期望抛硬币次数。

用 Hoeffding 不等式求第二、第三步中操作次数期望值的上界：

\mathrm{E}\Big[\big|X-\mathrm{E}[X]\big|\Big]=\int\limits_0^\infty \mathrm{Pr}\Big[\big|X-\mathrm{E}[X]\big|\geq t\Big]\mathrm{d}t\leq2\int\limits_0^\infty \exp {-\dfrac {t^2}n}\mathrm{d}t=\sqrt{\pi n}

从而第二、第三步所需抛硬币次数的期望值是 \sqrt{\pi n}\cdot2\lceil\log_2 n\rceil 。

综上，该算法期望需要抛 n+2\sqrt{\pi n}\lceil\log_2 n\rceil 次硬币。

「耦合」思想

「耦合」思想常用于同时处理超过一个有随机性的对象，或者同时处理随机的对象和确定性的对象。

引子：随机图的连通性

问题

对于 n \in \mathbf{N}^*; p,q\in [0,1] 且 q\leq p ，求证：随机图 G_1(n,p) 的连通分量个数的期望值不超过随机图 G_2(n,q) 的连通分量个数的期望值。这里 G(n,\alpha) 表示一张 n 个结点的简单无向图 G ，其中 \dfrac {n(n-1)}2 条可能的边中的每一条都有 \alpha 的概率出现，且这些概率互相独立。

这个结论看起来再自然不过，但严格证明却并不那么容易。

证明思路

我们假想这两张图分别使用了一个 01 随机数生成器来获知每条边存在与否，其中 G_1 的生成器 T_1 每次以 p 的概率输出 1， G_2 的生成器 T_2 每次以 q 的概率输出 1。这样，要构造一张图，就只需把对应的生成器运行 \dfrac {n(n-1)}2 遍即可。

现在我们把两个生成器合二为一。考虑随机数生成器 T ，每次以 q 的概率输出 0，以 p-q 的概率输出 1，以 1-p 的概率输出 2。如果我们将这个 T 运行 \dfrac {n(n-1)}2 遍，就能同时构造出 G_1 和 G_2 。具体地说，如果输出是 0，则认为 G_1 和 G_2 中都没有当前考虑的边；如果输出是 1，则认为只有 G_1 中有当前考虑的边；如果输出是 2，则认为 G_1 和 G_2 中都有当前考虑的边。

容易验证，这样生成的 G_1 和 G_2 符合其定义，而且在每个实例中， G_2 的边集都是 G_1 边集的子集。因此在每个实例中， G_2 的连通分量个数都不小于 G_1 的连通分量个数；那么期望值自然也满足同样的大小关系。

这一段证明中用到的思想被称为“耦合”，可以从字面意思来理解这种思想。本例中它体现为把两个本来独立的随机过程合二为一。

应用：NERC 2019 Problem G: Game Relics

简要题意

有若干个物品，每个物品有一个价格 c_i 。你想要获得所有物品，为此你可以任意地进行两种操作：

  1. 选择一个未拥有的物品 i ，花 c_i 块钱买下来。
  2. 花 x 块钱从所有物品（包括已经拥有的）中等概率随机抽取一个。如果尚未拥有该物品，则直接获得它；否则一无所获，但是会返还 \dfrac x2 块钱。 x 为输入的常数。

问最优策略下的期望花费。

观察：如果选择抽物品，就一定会一直抽直到获得新物品为止。

  • 理由：如果抽一次没有获得新物品，则新的局面和抽物品之前的局面一模一样，所以如果旧局面的最优行动是“抽一发”，则新局面的最优行动一定也是“再抽一发”。

我们可以计算出 f_k 表示：如果当前已经拥有 k 个不同物品，则期望要花多少钱才能抽到新物品。根据刚才的观察，我们可以直接把 f_k 当作一个固定的代价，即转化为“每次花 f_k 块钱随机获得一个新物品”。

期望代价的计算

显然 f_k=\dfrac x2 \cdot (R-1)+x ，其中 R 表示要得到新物品期望的抽取次数。

引理：如果一枚硬币有 p 的概率掷出正面，则首次掷出正面所需的期望次数为 \dfrac 1p 。

  • 感性理解： \dfrac 1p \cdot p = 1 ，所以扔这么多次期望得到 1 次正面，看起来就比较对。
  • 这种感性理解可以通过 大数定律 严谨化，即考虑 n\to \infty 次“不断抛硬币直到得到正面”的实验。推导细节略。
  • 另一种可行的证法是，直接把期望的定义带进去暴算。推导细节略。

显然抽一次得到新物品的概率是 \dfrac {n-k}n ，那么 R=\dfrac n{n-k} 。

结论：最优策略一定是先抽若干次，再买掉所有没抽到的物品。

这个结论符合直觉，因为 f_k 是关于 k 递增的，早抽似乎确实比晚抽看起来好一点。

证明

先考虑证明一个特殊情况。将证：

  • 随机过程 A ：先买物品 x ，然后不断抽直到得到所有物品
  • ……一定不优于……
  • 随机过程 B ：不断抽直到得到 x 以外的所有物品，然后如果还没有 x 则买下来

考虑让随机过程 A 和随机过程 B 使用同一个随机数生成器。即， A 的第一次抽取和 B 的第一次抽取会抽到同一个元素，第二次、第三次……也是一样。

显然，此时 A 和 B 抽取的次数必定相等。对于一个被 A 抽到的物品 y\neq x ，观察到：

  • A 中抽到 y 时已经持有的物品数，一定大于等于 B 中抽到 y 时已经持有的物品数。

因此 B 的单次抽取代价不高于 A 的单次抽取代价，进而抽取的总代价也不高于 A 。

显然 B 的购买代价同样不高于 A 。综上， B 一定不劣于 A 。

然后可以通过数学归纳把这一结论推广到一般情况。具体地说，每次我们找到当前策略中的最后一次购买，然后根据上述结论，把这一次购买移到最后一定不劣。细节略。

基于这个结论，我们再次等价地转化问题：把“选一个物品并支付对应价格购买”的操作，改成“随机选一个未拥有的物品并支付对应价格购买”。等价性的理由是，既然购买只是用来扫尾的，那选到哪个都无所谓。

现在我们发现，“抽取”和“购买”，实质上已经变成了相同的操作，区别仅在于付出的价格不同。选择购买还是抽取，对于获得物品的顺序毫无影响，而且每种获得物品的顺序都是等可能的。

观察：在某一时刻，我们应当选择买，当且仅当下一次抽取的代价（由已经抽到的物品数确定）大于剩余物品的平均价格（等于的话则任意）。

  • 可以证明，随着时间的推移，抽取代价的增速一定不低于剩余物品均价的增速。这说明从抽到买的“临界点”只有一个，进一步验证了先前结论。

最后，我们枚举所有可能的局面（即已经拥有的元素集合），算出这种局面出现的概率（已有元素的排列方案数除以总方案数），乘上当前局面最优决策的代价（由拥有元素个数和剩余物品总价确定），再加起来即可。这个过程可以用背包式的 DP 优化，即可通过本题。

回顾：可以看到，耦合的技巧在本题中使用了两次。第一次是在证明过程中，令两个随机过程使用同一个随机源；第二次是把购买转化成随机购买（即引入随机源），从而使得购买和抽取这两种操作实质上“耦合”为同一种操作（即令抽取和购买操作共享一个随机源）。

参考资料

  1. PANIC - Editorial ↩

  2. UOJ NOI Round #4 Day2 题解 ↩

  3. Anna Gambin and Adam Malinowski, Randomized Meldable Priority Queues ↩

buildLast update and/or translate time of this article，Check the history
editFound smelly bugs? Translation outdated? Wanna contribute with us? Edit this Page on Github
peopleContributor of this article Ir1d, partychicken, ouuan, Marcythm, TianyiQ
translateTranslator of this article Visit the original article!
copyrightThe article is available under CC BY-SA 4.0 & SATA ; additional terms may apply.

Comments