随机化算法

基本分析

Union Bound

即:,取等当且仅当所有互斥.

Markov 不等式

若,则.

Example(Max-Cut算法)

一个无向无权图,将点集划分成两个部分,使得跨越这两部分的边尽可能多.

直接随机划分,容易见到每条边有的概率是割边,因此期望自然是.

由此立即见到,.

由于每次独立操作,因此如果有的概率失败,那么运行次后至少成功一次的概率应当为.从而即可拿到失败概率.

Chernoff Bound

设是独立,同期望(期望为)的随机变量,令,对于任何失败概率,应当有:

Example(Median Trick)

现在有一个黑盒能够以的概率正确回答Yes或者No,问重复选多少次能拿到的成功概率.

考虑重复次后应当有期望个正确答案,因此直接取中位数.称此算法为Median Trick.

Chernoff Bound 告诉我们足够.

Hoeffding 不等式

设独立随机变量,令,则:

编程中的随机性

一般采用伪随机,也即是给定初值,通过某个确定性的函数来生成这样的.

数值概率算法

即通过随机选取元素从而求得在数值上的近似解.较之于传统算法,其运行速度更快,而且随着运行时间的增加,近似解的精度也会提高.在不可能或不必要求出问题的精确解时,可以使用其得到相当满意的近似解,如随机撒点法(近似求难以计算的图形面积).

Monte Carlo算法

总是能在确定的运行时间内出解,但是得到的解有一定概率是错的.通常出错的概率比较小,因此可以通过反复运行算法来得到可以接受的正确率.

求解最优化问题的Monte Carlo算法

事实上,大部分最优化问题都可以转化为判定性问题:也就是判定一个解是否是最优解,因此我们接下来基本都是讨论的求解判定性问题的Monte Carlo算法.

求解判定性问题的Monte Carlo算法

  1. 假倾向的Monte Carlo算法:当这类算法的返回值为假的时候,结果一定正确,但返回值为真的时候则有一定概率错误.

  2. 真倾向的Monte Carlo算法:当这类算法的返回值为真的时候,结果一定正确,但返回值为假的时候则有一定概率错误.

  3. 产生双侧错误的Monte Carlo算法:无论返回值为什么都有概率出错.基本不会使用.

以下讨论的Monte Carlo算法均为产生单侧错误的Monte Carlo算法.

正确率与复杂度

显然,如果我们有一个单词正确率为,时间复杂度为的算法,我们运行其次,则正确率为,时间复杂度为.

算法设计思路1

我们来总结一下通常的Monte Carlo算法的设计思路:

设计一个能解决问题的确定性算法

  1. 这个算法需要枚举一些元素.

  2. 设这个算法的复杂度为,其中为枚举部分的复杂度,为单词枚举中计算所需的复杂度.大部分情况下应保证不会很大.

向算法引入随机化优化复杂度

  1. 随机化寻找元素来降低复杂度.

  2. 计算随机化情况下的正确率以及复杂度.

算法设计思路2
设计一个能解决问题的确定性算法

  1. 这个算法需要用到一个或多个传入的元素.

  2. 这个元素的值不应该依赖于输入数据.

  3. 我们可以通过check这个元素来得到与答案有关的信息.

向算法引入随机化优化复杂度

  1. 随机这个元素.

  2. 计算随机化情况下的正确率以及复杂度

Example
Example 1(Millar-Rabin算法)

略

Example2(CodeChef MSTONE)

平面上有个互不重合的点,已知存在不超过条直线可以覆盖全部的点,问在平面上作一条直线,最多能覆盖多少个点..

考虑一个朴素的暴力:枚举两个点,确定一条直线,然后判断多少个点在这条直线上.但是这样复杂度是的.

考虑加入随机化.我们不妨每次随机两个点,注意到存在七条直线覆盖全部的点,那覆盖点最多的直线覆盖的点数一定不少于个点.换句话说,我们随机一个点,这个点在这条直线上的概率是,因此随机两个点确定这条直线的概率为.随机次,错误概率为,是很小的.

Example3(CF364D Ghd)

给定一个长度为的序列,要求找出一个长度大于等于的子序列,使这个子序列中所有数的最大,求最大的.,.

注意到我们随机一个数,这个数在最终答案中的概率是.我们不妨直接随机这个数,然后枚举它的因子,判断每个因子在序列中的出现次数即可.但是这样单次复杂度,好像不太能过.

冷静一下,我们不妨将这个质因子全都存下来,然后将个数也全都存下来,做狄利克雷后缀和即可.不过直接做可能还需要离散化/map,我们考虑先把所有数与我们随机到的那个数取一个,这样所有数就都是这个数的因子,可以使用大小因子分别编号来实现.

Example4([POI2014]Couriers)

给定长度为的序列,有次询问,每次给定一个区间,问中是否存在出现次数严格大于其它所有数出现次数之和的数,如果存在请输出..

先存下来每个位置的数是第几次出现,我们就可以利用二分快速找到一个区间内某个数出现次数.接下来只需要随机化找这个区间内某个数并判断是否满足条件即可.

Example5([NOI2013] 向量内积)

先考虑的情况:

首先,我们自然可以枚举一个向量并判断它与其它向量的内积,这样复杂度为.

冷静一下,这个过程其实就是一个矩阵乘法的过程:我们设,那我们要验证的无非是中是否存在一个不在主对角线上的元素在意义下为.

这咋做啊?我们冷静一下,构造一个矩阵,其中的主对角线元素与相同,而其他元素全是.接下来我们要做的无非是找到和不同的地方.

这咋办呢?我们考虑这么一点:如果,那么对于任意一个都应该满足,取,我们的问题就转化为:是否能找到一个,使得?这显然可以随机化.计算前者的复杂度为,后者由于很特殊,可以在的时间内求出.这样我们就保证了算法复杂度上的合理性.

接下来,我们要证明其正确率上的合理性.这个算法显然是单侧错误的Monte Carlo算法.问题在于正确率:

令,若返回相等但实际上不相等,则中至少存在一个不为的数字,假设.我们令,那么只有当是零向量时才会错误.而,不难解得:,也就是说如果的其它位置都确定了,那么只有一种取值会返回错误.由于一共就俩取值,所以正确率至少.

至于找到答案:我们找到一个不为的,那么一定存在一组解包含了第个向量,只需枚举另一个向量检验就行,复杂度.

的话,我们注意到意义下,和的平方都是.考虑,大概做做.

Las Vegas算法(Sherwood算法)

总是能返回正确的结果,但是其运行时间不确定.对于一些平均时间复杂度优秀,但是最坏情况下复杂度较高的确定性算法,通过引入随机函数,尝试减小最坏情况的可能性,以在期望意义下达到优秀的时间复杂度.

算法设计思路
设计一个能解决问题的确定性算法

  1. 这个算法需要枚举全排列.

  2. 通常,问题问的是要么只是可行解而不是最优解,要么最优方案特别多,总之要保证有用的排列个数不会太少

向算法引入随机化优化复杂度

  1. 随机化寻找排列来降低复杂度.

  2. 通常证明复杂度和正确率巨大麻烦,这里建议直接实践证明.

Example
快速排序算法

我们试图计算它的期望时间复杂度:

不妨设表示对长度为的序列运行快速排序算法所需的期望时间,我们有:

做放缩(可能有些地方需要或者或者加取整,但是问题不大,反正是期望):

由于,所以对于,我们显然有:.

因此:

我们要证明,,考虑使用数学归纳法,则:

于是显然存在,假设成立.

一类由Monte Carlo算法改造而成的算法

对于一类一定有解的构造性问题,假设我们有一个正确率为,时间复杂度为的产生单侧错误的Monte Carlo算法,我们时图将其改造为Las Vegas算法,我们现在想知道它的期望复杂度.

设其期望运行次,则:

则期望复杂度为.

Example3(CF329C Graph Reconstruction)
Example4([Petrozavodsk Summer-2015. Moscow IPT Contest B]Game With A Fairy)

首先注意到一个问题:操作能得到的信息太少了,应该是没有什么确定性算法.因此考虑随机化,那就肯定要先将整个序列random_shuffle一下.

然后呢?我们考虑之后随机选取新序列的一个前缀询问,只要有大致的正确性/复杂性估计应该就是很正确的.

这里有一种方式:考虑这个前缀中第一个有宝藏的位置和第二个位置,显然只要问到是正确的.

考虑因为是随机,所以的概率应当是不低的(事实上约为),而此时的中必有一个位置是二的整数幂,因此我们查询一个等比数列:.每次random_shuffle后就查一次,就可以得到一个正确性较高的Las Vegas算法.

爬山与模拟退火

爬山

也就是随机一个起始的解,然后走向与其相邻的较大的解.

但是这样会卡在一个局部最优解上而得不到全局最优解.

于是我们就有了模拟退火算法.

模拟退火

简而言之,模拟退火就是以一定的概率跳到随机的不优秀的点,这样就避免卡在了局部最优解上.不妨设我们想找到最大解,如果要最小解那就稍微改改.

下面给出这个概率的公式:

具体流程是,先设定一个初始温度,降温速度,以及终止温度,每次操作后让,直到其小于终止温度.

数据随机下的性质

树

  1. 随机树树高为.

  2. 点的度数期望为.

数

  1. 数字的期望因数个数为.

序列

  1. 随机序列的LIS长度期望为.