随机化技巧

概述

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

本文将对 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,也就转化到了平凡的情况。

算法伪代码
1
2
3
4
5
6
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」线性代数

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

  • 每次随机一个位置,把这个位置取反,判断大小并更新答案。
代码
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#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';
}

例:(*)随机堆

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

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

代码
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
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 优化,即可通过本题。


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

参考资料


评论