概率与期望

• 离散概率
  • 基本定义
  • 期望的简单运算
  • 方差的简单运算
  • 随机抽样调查
  • 条件概率
    • 贝叶斯公式
  • 概率生成函数
    • Example1
    • Example2(Penney游戏)
    • Example3([SDOI2017] 硬币游戏)
  • 二项式分布
  • 模型
    • 树上随机游走
      • Example1
      • Example2
    • 计数与期望的转换
      • Example(CodeChef Secplayer)
    • 一些小技巧
      • Example1(CF865C)
      • Example2(猎人杀)
      • Example3(AGC019F)
• 数据随机下的性质
  • 树
  • 数
  • 序列
• 随机化算法的分类
  • 数值概率算法
  • Monte Carlo算法
    • 求解最优化问题的Monte Carlo算法
    • 求解判定性问题的Monte Carlo算法
    • 正确率与复杂度
    • 算法设计思路1
      • 设计一个能解决问题的确定性算法
      • 向算法引入随机化优化复杂度
    • 算法设计思路2
      • 设计一个能解决问题的确定性算法
      • 向算法引入随机化优化复杂度
    • Example
      • Example 1(Millar-Rabin算法)
      • Example2(CodeChef MSTONE)
      • Example3(CF364D Ghd)
      • Example4([POI2014]Couriers)
    • Example5([NOI2013] 向量内积)
  • Las Vegas算法(Sherwood算法)
    • 算法设计思路
      • 设计一个能解决问题的确定性算法
      • 向算法引入随机化优化复杂度
    • Example
      • 快速排序算法
      • 一类由Monte Carlo算法改造而成的算法
      • Example3(CF329C Graph Reconstruction)
      • Example4([Petrozavodsk Summer-2015. Moscow IPT Contest B]Game With A Fairy)
  • 爬山与模拟退火
    • 爬山
    • 模拟退火

离散概率

基本定义

概率空间\(\Omega\):在一个给定问题中可能发生的所有情况.

事件:\(\Omega\)的一个子集.

基本事件\(\omega\):\(\Omega\)中的单个元素,也可以看作集合大小为\(1\)的事件.

概率:若\(\omega\in \Omega\),我们称它发生的概率为\(\Pr(\omega)\),有\(\Pr(\omega)\geq 0\)且\(\sum_{\omega\in\Omega}\Pr(\omega)=1\).

随机变量:在概率空间的基本事件上定义的函数.

联合分布:如果两个随机变量\(X\)和\(Y\)定义在同一个概率空间\(\Omega\)上,对于每一个在\(X\)取值范围内的\(x\)以及在\(Y\)取值范围内的\(y\),我们称\(\Pr(X=x\and Y=y)\)为它们的联合分布.

独立:如果对于每一个在\(X\)取值范围内的\(x\)以及在\(Y\)取值范围内的\(y\),\(\Pr(X=x\and Y=y)=\Pr(X=x)\times \Pr(Y=y)\),我们称\(X\)和\(Y\)是独立的.

期望(均值)\(E X\):我们设概率空间上的随机变量\(X\)的期望\(EX=\sum_{x\in X(\Omega)}x\times \Pr(X=x)=\sum_{w\in\Omega}X(\omega)\Pr(\omega)\).

中位数:我们设概率空间上的随机变量\(X\)的中位数为满足\(\Pr(X\leq x)\geq 0.5\and \Pr(X\geq x)\geq 0.5\)的\(x\in X(\Omega)\)所组成的集合.

众数:我们设概率空间上的随机变量\(X\)的众数为满足\(\Pr(X= x)\geq \Pr(X=x'),\forall x'\in X(\Omega)\)的\(x\in X(\Omega)\)所组成的集合.

方差\(VX\):我们设概率空间上的随机变量\(X\)的方差\(VX=E((X-EX)^2)\).

标准差\(\sigma\):我们设概率空间上的随机变量\(X\)的标准差\(\sigma=\sqrt{VX}\).

期望的简单运算

如果\(X,Y\)是定义在同一个概率空间上的两个随机变量,那么:

1. \(E(X+Y)=EX+EY\).
2. \(E(\alpha X)=\alpha EX\).
3. 如果\(X\)和\(Y\)互相独立,那么\(E(XY)=(EX)(EY)\).

上述法则都可以通过期望的定义简单证明.

方差的简单运算

我们考虑方差的定义式: \[ E((X-EX)^2)=E(X^2-2X(EX)+(EX)^2)\\ =E(X^2)-2(EX)(EX)+(EX)^2\\ =E(X^2)-(EX)^2 \] 也即:方差等于随机变量平方的均值减均值的平方.

当\(X\)和\(Y\)为独立的随机变量时,我们有: \[ V(X+Y)=E((X+Y)^2)-(EX+EY)^2\\ =E((X+Y)^2)-(EX)^2-2(EX)(EY)-(EY)^2 \] 而又有: \[ E((X+Y)^2)=E(X^2+2XY+Y^2)\\ =E(X^2)+2(EX)(EY)+E(Y^2) \] 则: \[ V(X+Y)=E(X^2)+2(EX)(EY)+E(Y^2)-(EX)^2-2(EX)(EY)-(EY)^2 \\=VX+VY \] 即:独立随机变量之和的方差等于它们的方差之和.

接下来,我们可以得到切比雪夫不等式: \[ \Pr((X-EX)^2\geq \alpha)\leq \cfrac{VX}{\alpha},\alpha>0 \] 证明如下: \[ VX=\sum_{\omega\in \Omega}(X(\omega)-EX)^2\Pr(\omega)\\ \geq \sum_{\omega\in\Omega}(X(\omega)-EX)^2\Pr(\omega)[(X(\omega)-EX)^2\geq \alpha]\\ \geq \sum_{\omega\in\Omega}\alpha\Pr(\omega)[(X(\omega)-EX)^2\geq \alpha]\\=\alpha \Pr((X-EX)^2\geq \alpha) \] 如果我们用\(c^2VX\)代替\(\alpha\),我们就有:

\(\Pr(|X-EX|\geq c\sigma)\leq \cfrac{1}{c^2}\).

简单来说,这个不等式说明:\(X\)落在\((EX-c\sigma,EX+c\sigma)\)之外的概率至多为\(\cfrac{1}{c^2}\).

另外,如果我们取\(n\)个独立的样本\(X_1,X_2,...,X_n\),令\(S=\sum_{i=1}^nX_i\),那么它的均值是\(nEX\),标准差是\(\sqrt n\sigma\),也就是说,\(\cfrac{S}{n}\)落在\((EX-\cfrac{c\sigma}{\sqrt n},EX+\cfrac{c\sigma}{\sqrt n})\)之外的概率小于等于\(\cfrac{1}{c^2}\).

随机抽样调查

如果我们随机取得了\(n\)个值\(X_1,X_2,...,X_n\),那么我们可以通过这些值来估计概率空间的期望和方差.

\(\hat EX=\cfrac{\sum_{i=1}^nX_i}{n}\).

\(\hat VX=\cfrac{\sum_{i=1}^nX_i^2}{n-1}-\cfrac{(\sum_{i=1}^nX_i)^2}{n(n-1)}\).

这里的\(\hat VX\)似乎与定义不是那么相符.但是它拥有更好的性质:\(E(\hat VX)=VX\).

证明如下: \[ E(\hat VX)=\cfrac{1}{n-1}E(\sum_{i=1}^nX_i^2-\cfrac{1}{n}\sum_{j=1}^n\sum_{k=1}^nX_jX_k)\\ =\cfrac{1}{n-1}(\sum_{i=1}^nE(X_i^2)-\cfrac{1}{n}\sum_{i=1}^n\sum_{j=1}^nE(X_iX_j))\\ =\cfrac{1}{n-1}(\sum_{i=1}^nE(X^2)-\cfrac{1}{n}\sum_{i=1}^n\sum_{j=1}^n((EX)^2[j\ne k]+E(X^2)[j=k]))\\ =\cfrac{1}{n-1}(nE(X^2)-\cfrac{1}{n}(nE(X^2)+n(n-1)(EX)^2))\\ =E(X^2)-(EX)^2\\ =VX \]

条件概率

已知事件B发生时事件A发生的概率为\(P(A|B)=\frac{P(AB)}{P(B)}\\\).

贝叶斯公式

贝叶斯公式:如果有\(\{B_i\}\)是样本空间的一个划分,即\(\forall i,j\),有\(B_i\cap B_j=\empty\),并且有\(\bigcup_{i=1}^nB_i=\Omega\).则有\(P(B_i|A)=\frac{P(AB_i)}{P(A)}=\frac{P(AB_i)}{P(A)\sum P(B_j)}=\frac{P(A B_i)}{\sum_{j=1}^n P(A B_j)}=\frac{P(A|B_i)P(B_i)}{\sum_{j=1}^n P(A|B_j)P(B_j)}\\\).

简化形式:\(P(B|A)=\frac{P(A|B)P(B)}{P(A)}\\\).

另外,我们考虑设\(O(B)=\cfrac{P(B)}{P(\lnot B)}\),称\(\cfrac{P(B|E)}{P(\lnot B|E)}\)为贝叶斯算子,则同理可得: \[ O(B|E)=O(B)\cfrac{P(B|E)}{P(\lnot B|E)} \] 这个公式更加精准地分开了先验概率和后验概率,也表现了贝叶斯算子对先验概率的改变.

概率生成函数

如果\(X\)是定义在概率空间\(\Omega\)上的随机变量,那么它的概率生成函数为\(G_X(z)=\sum_{k\geq 0}\Pr(X=k)z^k=E(z^X)\).

不难发现\(G_X(z)\)需要满足的条件:所有系数都非负并且\(G_X(1)=1\).

我们发现,当我们定义了概率生成函数后,期望和方差都可以使用它来表示: \[ EX=G_X'(1)\\ E(X^2)=G''_X(1)+G_X'(1)\\ VX=G_X''(1)+G_X'(1)-(G_X'(1))^2 \] 通常,我们也可以将方差和均值的定义扩展到任意函数上,于是我们定义: \[ Mean(G)=G'(1)\\ Var(G)=G''(1)+G'(1)-(G'(1))^2 \] 不过,求导的过程可能会有些麻烦,但我们可以直接使用泰勒定理: \[ G(1+t)=\sum_{i\geq 0}\cfrac{G^{(i)}(1)}{i!}t^i \] 另外,我们不难发现:\(G_{X+Y}(z)=G_X(z)G_Y(z)\).

根据前面的推导,我们有: \[ Mean(G_{X+Y})=Mean(G_X)+Mean(G_Y)\\ Var(G_{X+Y})=Var(G_X)+Var(G_Y) \] 换句话说,若\(G_X(1)=1,G_Y(1)=1\),那么这个式子与直接对\(G_{X+Y}\)使用求导的那个公式是等价的.注意,这里并没有要求这些生成函数的系数是非负的.

于是我们有了另一个法则: \[ Mean(G_X)=Mean(G_{X+Y})-Mean(G_Y)\\ Var(G_X)=Var(G_{X+Y})-Var(G_Y) \]

Example1

一枚硬币正面向上的概率为\(p\),反面向上的概率为\(q\),设硬币正面向上为H,反面向上为T,不断抛掷硬币直到抛掷出连续的THTTH为止,求期望次数.

考虑设\(N\)为所有不包含THTTH的硬币序列的生成函数,\(S\)为所有只有结尾为THTTH的硬币序列的生成函数,令\(H=pz,T=qz\),\(1\)为空集,我们显然有: \[ 1+N\times (H+T)=N+S\\ N\times THTTH=S+S\times TTH \] 解方程即可.

另外不难发现,这种方法取决于字符串的所有border,显然是通用方法.

我们考虑扩展这个方法,设\(A\)是我们要找到的字符串,\(m\)是它的长度,令\(A^{(k)}\)表示\(A\)字符串的前\(k\)个字符所组成的字符串,\(A_{(k)}\)表示\(A\)字符串的后\(k\)个字符所组成的字符串.这样的形式与\(k\)阶导的形式可能会起冲突,但至少在接下来我们的式子中不会出现导数(好吧其实是因为《具体数学》上就这么写的我也懒得改了).

我们的方程将会变为: \[ 1+N(H+T)=N+S\\ N\times A=S(\sum_{k=0}^{m-1}A^{(k)}[A^{(m-k)}=A_{(m-k)}]) \] 如果我们设\(\tilde A\)为将字符串\(A\)中的H替换成\(\cfrac{1}{p}z\),T替换成\(\cfrac{1}{q}z\)之后的值,那么显然有: \[ N\times A=A\times S\times (\sum_{k=1}^{m}\tilde A_{(k)}[A^{(k)}=A_{(k)}])\\ N=S\times (\sum_{k=1}^{m}\tilde A_{(k)}[A^{(k)}=A_{(k)}])\\ \cfrac{S-1}{H+T-1}=S\times (\sum_{k=1}^{m}\tilde A_{(k)}[A^{(k)}=A_{(k)}])\\ S\times(1+(1-H-T)\times (\sum_{k=1}^{m}\tilde A_{(k)}[A^{(k)}=A_{(k)}]))=1 \] 这显然是一个卷积的形式.

令\(w=\sum_{k=1}^{m}\tilde A_{(k)}[A^{(k)}=A_{(k)}]\).

令\(H(z)=1\),\(F(z)=(1+(1-z)\times w)\),\(G(z)=S\).

那么我们显然可以直接求\(G(z)\)的期望和方差,事实上: \[ EX=\sum_{k=1}^{m}\tilde A_{(k)}[A^{(k)}=A_{(k)}]\\ VX=(EX)^2-\sum_{k=1}^m(2k-1)\tilde A_{(k)}[A^{(k)}=A_{(k)}] \] 如果硬币是均匀的(\(p=q=\cfrac 1 2\))我们引入另一个符号:我们设\(A:A=\sum_{k=1}^m2^{k}[A^{(k)}=A_{(k)}]\).那么显然期望需要的抛硬币次数就是\((A:A)\).

Example2(Penney游戏)

一枚均匀硬币,设硬币正面向上为H,反面向上为T.不断扔硬币直到扔出连续的HHT或HTT为止,求最后以HHT结尾的概率.

我们设\(S_A\)为所有以HHT结尾的硬币序列的生成函数,设\(S_B\)为所有以HTT结尾的硬币序列的生成函数.\(N\)为其它的硬币序列的生成函数,令\(H=T=0.5z\).

我们显然有: \[ 1+N(H+T)=N+S_A+S_B\\ N\times HHT=S_A\\ N\times HTT=S_A\times T+S_B \] 解方程并带入\(z=1\),可以有得知以HHT结尾的概率为\(\cfrac{2}3\).

事实上,我们使用类似Example1的方法,设这两个硬币序列分别为\(A\)和\(B\),那么可以求出: \[ \cfrac{S_A}{S_B}=\cfrac{B:B-B:A}{A:A-A:B} \]

Example3([SDOI2017] 硬币游戏)

是Example2的超级加强版.

把上面的东西给形式化一下,不妨设\(g_i\)表示进行了\(i\)步还未结束的概率,\(f_{k,i}\)为进行了\(i\)步恰好第\(k\)个人胜利的概率,\(F,G\)是它们的生成函数,我们自然有:

1. \(1+xG(x)=\sum_kF_k(x)+G(x)\).
2. \((\frac{1}{2}x)^LG(x)=\sum_{j=1}^nF_j(x)\sum_{i=0}^{L-1}(\frac{1}{2}x)^i[A_k^{(L-i)}={A_j}_{(L-i)}]\).

第一个式子的用处在于带入\(x=1\),发现\(\sum_{k}F_k(1)=1\).

把(2)化简一下,有: \[ x^LG(x)=\sum_{j=1}^nF_j(x)\sum_{i=0}^{L-1}(\frac{1}{2}x)^{i-L}[A_k^{(L-i)}={A_j}_{(L-i)}]\\ x^LG(x)=\sum_{j=1}^nF_j(x)\sum_{i=1}^{L}(\frac{1}{2}x)^{-i}[A_k^{(i)}={A_j}_{(i)}] \] 带入\(x=1\),有: \[ G(1)=\sum_{j=1}^nF_j(1)\sum_{i=1}^{L}2^i[A_k^{(i)}={A_j}_{(i)}] \] 不难发现对于不同的\(k\),(2)的右边不同,而左边一定相同,这样就给出了\(n\)个等式,算上(1)一共有\(n+1\)个等式,可以算出\(G(1),F_{1\cdots n}(1)\)这\(n+1\)个未知数.

二项式分布

现在有一个大小为\(n+1\)的概率空间,其中\(\Pr(\omega_k)=\binom{n}{k}p^kq^{n-k}\\\),我们把这样的概率序列称为二项式分布.

如果我们令\(H(z)=q+pz\),不难发现二项式分布的生成函数为\(H(z)^n\).

不难发现,满足二项式分布的随机变量的均值是\(np\),方差是\(npq\).

与二项式分布相对应的还有负二项式分布,它的生成函数形如:\(G(z)^n=(\cfrac{p}{1-qz})^n=\sum_{k}\binom{n+k-1}{k}p^nq^kz^k\).

我们考虑如何求\(G(z)\)的方差和均值,不妨设\(F(z)=\cfrac{1-qz}{p}=\cfrac{1}{p}-\cfrac{q}{p}z\),则\(G(z)^n=F(z)^{-n}\).

不难发现\(F(z)\)满足二项式分布.也就是说,以\((n,p,q)\)为参数的负二项式分布也就是以\((-n,-\cfrac{q}{p},\cfrac{1}{p})\)为参数的二项式分布.

模型

树上随机游走

随机游走指每次从相邻的点中随机选一个走过去， 重复这样的过程若干次.

Example1

给一棵所有边长都为\(1\)的\(n\)个点的树,问所有点对\((i,j)(1\leq i,j\leq n)\)中,从\(i\)走到\(j\)的期望距离的最大值是多少.

由于树上简单路径唯一,我们考虑设\(f_u\)表示\(u\)随机走到它父亲的期望,\(g_v\)表示\(v\)的父亲(假设是\(u\))走到\(v\)的期望.

对于\(f_u\),我们有: \[ f_u=\cfrac{\sum_{u\rightarrow v}(f_v+f_u)}{\deg_u}+1\\ f_u=\deg_u+\sum_{u\rightarrow v}f_v \] 对于\(g_v\),我们有: \[ g_v=\cfrac{g_u+g_v+\sum_{u\rightarrow w,w\ne v}(g_v+f_w)}{\deg_u}+1\\ g_v=g_u+\sum_{u\rightarrow w,w\ne v}f_w+\deg_u \]

Example2

给出一棵\(n\)个节点的树,每个点有可能是黑白两种颜色的一种.

现在从\(1\)号点开始随机游走(即走这个点的每条出边的概率是相同的),每到一个点,如果这个点是黑点,或者这是白点并且这个点第一次经过,那么答案\(+1\).当走到度数为\(1\)的节点时游走停止.

注意到黑白点对答案的贡献是互相独立的,所以分开讨论:

如果只有黑点,那么显然答案就是路径的期望长度,我们设\(f_u\)表示以\(u\)为起点的路径的期望长度,不难注意到\(f_{leaf}=1\)且\(f_u=1+\cfrac{1}{\deg_u}\sum_{u\rightarrow v\or v\rightarrow u}f_v\).这个dp转移显然是有后效性的,可以使用高斯消元做,但有一个经典做法:我们求得\(f_u=k_uf_{fa}+b_u\),然后就可以采取带入化简的方法做了.

如果只有白点,考虑每个点只会贡献一次,所以我们要求出的就是每个点被走到的概率.注意到一个点被走到一定是从它父亲走来的,于是我们需要求出\(g_v\)表示从\(v\)的父亲(假设是\(u\))走到\(v\)的概率,再令\(f_u\)表示从\(u\)走到父亲的概率,类似Example1,我们有: \[ f_u=\cfrac{1}{\deg_u}(1+\sum_{u\rightarrow v} f_vf_u)\\ g_v=\cfrac{1}{\deg_u}(1+g_vg_u+\sum_{u\rightarrow w,w\ne v}f_wg_v) \] 最后把两部分答案合起来就好.

计数与期望的转换

Example(CodeChef Secplayer)

冷静一下,如果我们直接计数的话会发现巨大难做,因为项太多了,直接乘起来也太麻烦了.

这启发我们:当我们注意到一个计数题的各种情况相乘很麻烦的时候,我们不妨只考虑一种情况并计算期望,然后拿期望和总数反推计数.注意到权值最小的人最危险,他不能和其他任何一个人匹配到,不然就死了.那不难求得此时他作为次大值存活的概率为\(\frac{1}{\binom{n}{2}}\).

把所有人权值从大到小排序,设\(f_i\)表示只考虑前\(i\)个人的时候的期望,不难发现:\(f_{i}=\frac{1}{\binom{i}{2}}v_i+(1-\frac{1}{\binom{i}{2}})f_{i-1}\).

一些小技巧

Example1(CF865C)

首先写出转移式子,但是存在后效性.如果我们设\(f_{i,j}\)表示过了\(i\)关,花费为\(j\)的期望,不难发现所有的\(f\)都需要与\(f_{0,0}\)取\(\min\),这咋办?

我们考虑二分这个\(f_{0,0}\),做的时候直接取\(\min\),这样最后还会求出一个\(f_{0,0}\),比较一下大小然后继续做二分.

等一下,为撒子这样是收敛的呢?

首先,根据这个题,期望肯定是存在的.

我们注意到我们一开始二分的\(f_{0,0}\)越大,最后的答案就越大,但是增长的一定会变慢.换句话说,最后的答案关于我们二分的值的关系应该是一个上凸的函数(增长的时候会被取\(\min\)的另一项限制住,但原本应该是没被限制的),于是这个时候得到的答案如果比二分的答案更小,那我们就应该调小一点.

换句话说,当我们二分答案的时候,应该判断函数凸性.wqs二分也是这个道理:二分答案并判断答案是否满足条件.

Example2(猎人杀)

先做一步转化:如果做期望的时候,会有一些操作变得不能做,那我们改为:先随便选,如果选到不合法的操作就跳过,概率和期望都不会变.

offline

Example3(AGC019F)

人类智慧题…

首先注意到策略显然是每次选剩下最多的答案.

我们画一张\(n\times m\)的图(假设\(n\geq m\)),其中格点\((a,b)\)表示现在还剩\(a\)个Yes,\(b\)个No.我们再把我们的策略用图上的有向边表示.我们先考虑转化为计数问题,那答案显然就是所有从\((n,m)\)走到\((0,0)\)的路径与我们图上有向边的交的大小总和.

然后咧?

我们注意到这张图长得太规律了,换句话说,如果我们把图的左半部分沿着直线\(y=x\)翻折(路径也跟着翻折),注意到对着这张图做仍然是一样的!

所以呢?由于从\((n,m)\)走到\((0,0)\)一定会经过\(n\)条有向边,所以期望贡献一定要加上一个\(n\).而如果我走到了直线\(y=x\)上,那接下来的贡献是\(\frac{1}{2}\).我们只需要枚举一下走到了多少次即可.

数据随机下的性质

树

1. 随机树树高为\(\sqrt n\).
2. 点的度数期望为\(\log n\).

数

1. 数字的期望因数个数为\(\log V\).

序列

1. 随机序列的LIS长度期望为\(O(\sqrt n)\).

随机化算法的分类

数值概率算法

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

Monte Carlo算法

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

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

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

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

1. 假倾向的Monte Carlo算法:当这类算法的返回值为假的时候,结果一定正确,但返回值为真的时候则有一定概率错误.
2. 真倾向的Monte Carlo算法:当这类算法的返回值为真的时候,结果一定正确,但返回值为假的时候则有一定概率错误.
3. 产生双侧错误的Monte Carlo算法:无论返回值为什么都有概率出错.基本不会使用.

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

正确率与复杂度

显然,如果我们有一个单词正确率为\(p\),时间复杂度为\(O(f(n))\)的算法,我们运行其\(k\)次,则正确率为\(1-(1-p)^k\),时间复杂度为\(O(kf(n))\).

算法设计思路1

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

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

1. 这个算法需要枚举一些元素.
2. 设这个算法的复杂度为\(O(f(n)g(n))\),其中\(f(n)\)为枚举部分的复杂度,\(g(n)\)为单词枚举中计算所需的复杂度.大部分情况下应保证\(g(n)\)不会很大.

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

1. 随机化寻找元素来降低复杂度.
2. 计算随机化情况下的正确率以及复杂度.

算法设计思路2

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

1. 这个算法需要用到一个或多个传入的元素.
2. 这个元素的值不应该依赖于输入数据.
3. 我们可以通过check这个元素来得到与答案有关的信息.

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

1. 随机这个元素.
2. 计算随机化情况下的正确率以及复杂度

Example

Example 1(Millar-Rabin算法)

略

Example2(CodeChef MSTONE)

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

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

考虑加入随机化.我们不妨每次随机两个点,注意到存在七条直线覆盖全部的点,那覆盖点最多的直线覆盖的点数一定不少于\(\lceil\frac{n}{7}\rceil\)个点.换句话说,我们随机一个点,这个点在这条直线上的概率是\(\frac{1}{7}\),因此随机两个点确定这条直线的概率为\(\frac{1}{49}\).随机\(1000\)次,错误概率为\(1-(\frac{48}{49})^{1000}\),是很小的.

Example3(CF364D Ghd)

给定一个长度为\(n\)的序列,要求找出一个长度大于等于\(\frac{n}{2}\)的子序列,使这个子序列中所有数的\(\gcd\)最大,求最大的\(\gcd\).\(n\leq 10^6\),\(a_i\leq 10^{12}\).

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

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

Example4([POI2014]Couriers)

给定长度为\(n\)的序列\(a\),有\(m\)次询问,每次给定一个区间\([l,r]\),问\(a[l,r]\)中是否存在出现次数严格大于其它所有数出现次数之和的数,如果存在请输出.\((n,m\leq 500000,1\leq a_i\leq n)\).

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

Example5([NOI2013] 向量内积)

先考虑\(k=2\)的情况:

首先,我们自然可以枚举一个向量\(A\)并判断它与其它向量的内积,这样复杂度为\(O(n^2d)\).

冷静一下,这个过程其实就是一个矩阵乘法的过程:我们设\(A=\begin{bmatrix}\vec{a_1},\vec{a_2},...,\vec{a_n}\end{bmatrix}\),那我们要验证的无非是\(B=AA^T\)中是否存在一个不在主对角线上的元素\(B_{i,j}\)在\(\mod 2\)意义下为\(0\).

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

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

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

令\(D=B-C\),若返回相等但实际上不相等,则\(D\)中至少存在一个不为\(0\)的数字,假设\(D_{i,j}\ne 0\).我们令\(E=X\times D\),那么只有当\(E\)是零向量时才会错误.而\(E_j=\sum_{k}X_kD_{k,j}\),不难解得:\(E_i=-\frac{1}{D_{i,j}}\sum_{k\ne i}X_kD_{k,j}\),也就是说如果\(X\)的其它位置都确定了,那么\(E\)只有一种取值会返回错误.由于\(k\)一共就俩取值,所以正确率至少\(\frac{1}2\).

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

\(k=3\)的话,我们注意到\(\mod 3\)意义下,\(1\)和\(2\)的平方都是\(1\).考虑\(\sum_{j}B_{i,j}^2X_j=\sum_{j}B_{i,j}X_jB_{h,i}^T\),大概做做.

Las Vegas算法(Sherwood算法)

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

算法设计思路

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

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

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

1. 随机化寻找排列来降低复杂度.
2. 通常证明复杂度和正确率巨大麻烦,这里建议直接实践证明.

Example

快速排序算法

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

不妨设\(T(n)\)表示对长度为\(n\)的序列运行快速排序算法所需的期望时间,我们有: \[ T(0)=0\\ T(n)=n+\frac{1}{n}\sum_{i=0}^{n-1}(T_i+T_{n-i-1}) \] 做放缩(可能有些地方需要\(+1\)或者\(-1\)或者加取整,但是问题不大,反正是期望): \[ T(n)=n+\frac{1}{n}\sum_{i=0}^{n-1}(T_i+T_{n-i-1})\\ =n+\frac{2}{n}\sum_{i=\frac{n}{2}}^{n-1}(T_i+T_{n-i-1})\\ =n+\frac{2}{n}\sum_{i=\frac{n}{2}}^{\frac{3n}{4}}(T(i)+T(n-i-1))+\frac{2}{n}\sum_{i=\frac{3n}{4}}^{n}(T(i)+T(n-i-1)) \] 由于\(T(n)\geq n\),所以对于\(\frac{n}2\leq i\leq j\),我们显然有:\(T(i)+T(n-i)\leq T(j)+T(n-j)\).

因此: \[ T(n)\leq n+\frac{2}{n}\sum_{i=\frac{n}{2}}^{\frac{3n}{4}}(T(\frac{3n}{4})+T(\frac{n}{4}))+\frac{2}{n}\sum_{i=\frac{3n}{4}}^{n}(T(n-1)+T(0))\\ \leq n+\frac{1}{2}(T(\frac{3n}{4})+T(\frac{n}{4})+T(n-1)) \] 我们要证明\(\exists c\),\(T(n)\leq cn\log n\),考虑使用数学归纳法,则: \[ T(n)\leq n+\frac{1}2(\frac{3cn}4\log(\frac{3n}{4})+\frac{cn}4\log(\frac{n}{4})+c(n-1)\log(n-1))\\ \leq n+c(\frac{3n}{8}\log n-\frac{3n}{8}\log\frac{4}{3}+\frac{n}{8}\log n-\frac{n}{4}+\frac{n}{2}\log n)\\ =cn\log n+n(1-\frac{3c}{8}\log(\frac{4}{3})-\frac{c}{4}) \] 于是显然存在,假设成立.

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

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

设其期望运行\(k\)次,则: \[ k=\sum_{i=1}^{\infty}p(1-p)^{i-1}i\\ (1-p)k=\sum_{i=1}^{\infty}p(1-p)^ii\\ pk=\sum_{i=2}^{\infty}p(1-p)^{i-1}=p\sum_{i=0}^{\infty}(1-p)^i\\ k=\frac 1 p \] 则期望复杂度为\(O(\frac{f(n)}{p})\).

Example3(CF329C Graph Reconstruction)

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

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

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

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

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

爬山与模拟退火

爬山

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

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

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

模拟退火

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

下面给出这个概率的公式: \[ P=\begin{cases}1&E_{t+1}>E_t\\e^{\frac{E_{t+1}-E_t}{T}}&E_{t+1}\leq E_t\end{cases} \] 具体流程是,先设定一个初始温度\(T_0\),降温速度\(k\in(0,1)\),以及终止温度\(T_k\),每次操作后让\(T=kT\),直到其小于终止温度.