- 随机算法是非确定性算法, 但是可以看做一个额外有随机数序列作为输入的确定性算法.
- 随机算法的复杂度或者输出可以看做随机变量
- 输出可以看做随机变量的随机算法称为蒙特卡洛算法
- 永远输出正确答案但是复杂度是随机变量的随机算法称为拉斯维加斯算法
- 常常不知道随机化是否是有效的, 也不知道是否能在不牺牲资源的情况下转化为确定性算法.
- 可以结合随机算法和近似算法, 将近似率看做随机变量
概念
- $Random_A(x)$: 算法A在输入x的所有情况下的用到的最大随机比特数
- $Random_A(n) = \max\\{Random_A(x)| x ~is ~a ~input ~of ~size ~n\\}$
- $Prob_{A, x}(C)$: 算法A在输入x时以C的方式运行的概率
- 是运行方式C中所有随机选择的概率之积
- $Prob(A(x) = y)$: 输入x时A输出y的概率
- A在输入x时的期望运行时间
- 当期望时间难求的时候, 经常用最坏情况替代:
- 但是随机算法允许小概率的永不终止
随机算法的分类
拉斯维加斯算法
- 永不给出错误输出
- 定义一:
如果对于问题$F$的所有输入实例$x$, 有则随机算法A是拉斯维加斯算法. 其中的$F(x)$指在输入实例x时问题$F$的解. - 定义二:
如果对于问题$F$的任何输入实例$x$, 有且 - 随机快排: 每次随机选取一个数a, 将所有数分为大于a, 等于a, 小于a三类, 然后递归将小于a和大于a的类排序, 直到一类只有一个数.
- 类似的有随机算法求第k小的数
- 期望运行时间
- 数学归纳法得$E(T(n))\le 5n$
- 拉斯维加斯单向通信:
- 问题:
- $C_I$将输入x计算为一个prefix-free的01位串$\overline C_I(x)$
- $C_{II}$根据$\overline C_I(x)$和y计算出0或者1
- $Choice_n: \{0,1\}^n\times \{1,2,\cdots,n\}\to\{0,1\}: Choice_n(x_1x_2\cdots x_n,i)=x_i$
- 通过单向通信计算$Choice_n$
- 通信复杂度$\max\{|\overline C_I(x)||x\in A_I\}$至少为n
- 有如下$n / 2 + 1$拉斯维加斯算法:
- D1随机选择0或1
- 如果选到0, 发送$0x_1x_2\cdots x_{n/2}$, 否则发送$0x_{n/2+1}x_{n/2+2}\cdots x_{n}$
- $r=0$时, 如果$j\in\{1,2,\cdots,n/2\}$, 输出$x_j$; 否则输出”?”;
- $r=1$时, 如果$j\in\{1,2,\cdots,n/2\}$, 输出”?”; 否则输出$x_j$
- 问题:
单边错误蒙特卡洛算法
- 仅限于决定性问题
- 当算法A满足下列条件时, 称为单边错误蒙特卡洛算法
- 对于所有$x\in L$, $Prob(A(x)=1)\ge \frac{1}{2}$
- 对于所有$x\not\in L$, $Prob(A(x)=0)=1$
- 对于不符合要求的输入从不说”是”
- 例: 通过单向通信计算函数
$Non-Eq_n: \\{0,1\\}^n\times\\{0,1\\}^n\to \\{0,1\\}: Non-Eq_n(x,y)=1 ~iff ~x\ne y$
对于01位串u和v, $u\ne v$ 说明$\overline C_I(u)\ne C_I(v)$
有如下$\log_2 n$单边错误蒙特卡洛算法:- $R_I$随机选取一个[2, $n^2$]间的素数p(约$2\lceil\log_2 n\rceil$random bits)
- $R_I$计算$s=Number(x)\mod p$, 发送$p$和$s$给$R_{II}$
- $R_{II}$计算$q=Number(y)\mod p$, 如果$q\ne s$输出1, 否则输出0
- 算法分析
- 显然$Prob(R_I, R_{II} ~ rejects ~(x,y))=1$
- 若$x\ne y$但$Number(x)\mod p =Number(y) \mod p$
那么$p| h= |Number(x)-Number(y)|$ - 因为$h<2^n$, 所以至多$n-1$个满足要求的素数l, 而区间内总共有至少$n^2/\ln_n^2$个素数,
所以概率至多为$\frac{n-1}{n^2/\ln_n^2}\le \frac{\ln n^2}{n}$. - 因此$Prob((R_I, R_{II})~ accepts ~ (x,y))\ge 1-\frac{\ln n^2}{n}$, 当$n>100$时大于0.9
双边错误蒙特卡洛算法
- 定义: 对问题F的所有输入实例$x$, 存在$\epsilon(1<\epsilon\le \frac{1}{2})$满足$Prob(A(x)=F(x))\ge \frac{1}{2} +\epsilon$
- 让算法A跑t次, 取其中至少出现$\lceil t/2\rceil$的结果(如果存在, 否则输出”?”), 算法记做$A_t$. 假设A跑一次正确概率为$p(x)\ge \frac{1}{2}+\epsilon$, 那么对于x, A跑k次给出正确答案的概率$Prob(A_t(x)=F(x))\ge 1-\frac{1}{2}(1-4\epsilon^2)^{t/2}$
- 如果要$Prob(A_k(x)=F(x))\ge 1-\delta$, 那么需要$k\ge \frac{2\ln 2\delta}{\ln(1-4\epsilon^2)}$
无界错误蒙特卡洛算法
- 定义: 对问题F的所有输入实例$x$, 有$Prob(A(x)=F(x))> \frac{1}{2} $
- 想要通过运行k次无界错误蒙特卡洛算法A得到满足$Prob(A_{k(|x|)}(x)=F(x))\ge 1-\delta$的算法$A_{k(n)}$, 需要接受$Time_{A_{k(n)}}(n)=O(2^{2Random_A(n)}\cdot Time_A(n))$
随机最优化算法
- 取最好的那次
- $Prob(A_k(x)\in Output_U(x))=1-[Prob(A(x)\not\in Output_U(x))]^k$
- 定义: U的随机$\delta-$近似算法: 对于所有$x\in L_I$有
- $Prob(A(x)\in M(x))=1$
- $Prob(R_A(x)\le \delta)\ge 1/2$
- 类似的有随机f(n)-近似算法($\delta$改为$f(|x|)$)
- RPTAS: 对于任意输入对$(x,\delta)\in L_I \times \mathbb R^+$
- 对于所有随机选择, A计算出U的一个可行解: $Prob(A(x,\delta)\in M(x))=1$
- 至少有1/2的概率输出一个相对误差至多$\delta$的可行解: $Prob(\epsilon_A(x,\delta)\le \delta)\ge 1/2$
- $Time_A(x, \delta^{-1})\le p(|x|,\delta^{-1})$, p是|x|的多项式函数
- 如果时间还是$\delta^{-1}$的多项式函数, 那么是RFPTAS
- 随机$\delta-$期望近似算法: 对所有$x\in L_I$
- $Prob(A(x)\in M(x))=1$
- $E[R_A(x)]\le \delta$
随机算法设计范式
- 随机算法打败对手策略中的”难”的输入
- 随机选取构造证书
- 指纹识别判断问题等价性
- 随机选取映射h
- 计算指纹$h(R_1), h(R_2)$
- 如果$h(R_1)= h(R_2)$输出yes, 否则输出no
- 随机采样
- 随机变量的期望保证至少一个样本不大于期望, 至少一个样本不小于期望
- 样本以正概率满足某性质, 则一定有样本满足该性质
- 松弛和随机舍入
- 如整数规划->线性规划