五.随机算法

五.随机算法

一.概率分析总论

随机变量指示器

Interview-HIire问题简介: 假设对于一组有序(且不同)排序随机的面试者,依次面试.雇佣策略为如果比已雇佣的的人好,就雇佣该面试者.求雇佣数目X的期望

随机变量定义法

由于 E(X)=XiPr(X=Xi)E(X)=X_i Pr(X=X_i)E(X)=Xi​Pr(X=Xi​)﻿

可以单独求出值雇佣一个人的概率Pr(X=Xi) Pr(X=X_i)Pr(X=Xi​)﻿ 

随机变量指示器

X=X1+X2…XnX = X_1 + X_2 … X_nX=X1​+X2​…Xn​﻿

E(X)=E(X1)+E(X2)…E(Xn)E(X) = E(X_1) + E(X_2) … E(X_n)E(X)=E(X1​)+E(X2​)…E(Xn​)﻿

其中有E(Xi)E(X_i) E(Xi​)﻿为前面i-1个人中最有资格的,而最有资格的人在前i个人中出现几率相等,则有E(Xi)=1iE(X_i) = \frac{1}{i}E(Xi​)=i1​﻿

此处不再采用广义计数规则及其扩展

即不再采用计算所有可能的情况并除以总情况AnnA_n^nAnn​﻿的算法 

更加灵活的随机应用如何解决？

E(X)=1+1/2+1/3…1/n=Θ(ln(n))E(X) = 1 + 1/2 + 1/3 … 1/n = \Theta(ln(n))E(X)=1+1/2+1/3…1/n=Θ(ln(n))﻿

过程变量和TermNumTermNumTermNum﻿级数

预先定义的概念

过程变量: 参考随机变量,利用随机变量来完成集合→实数的映射,我们也用一个变量完成过程→整数的映射

定义: i=[1..n] 为第i次迭代前

定义: (TermNum)i(TermNum)_i(TermNum)i​﻿ 为第A[1..i-1]特定排序下,未确定序列元素的个数(即分母的值)

引入随机性: 每次我们使用 "各个情况(子集/元素)不具备特殊性且构成一个完备子集组" 这个条件我们就称引入了一次随机性

概率的分析方法

对于求取概率问题: 目前有两种常见思路

特定Pr{子集}: 根据已知概率(公理化: 已知Pr函数初始性质),求出某一种特定情况下的概率(推导已知的Pr{子集}),然后其他的情况(子集)可能和该情况下完全或者,或者利用 集合-Pr 性质 比如Pr{A+B}=Pr{A}+Pr{B}−Pr{AB}Pr\{A+B\} = Pr\{A\} + Pr\{B\} -Pr\{AB\}Pr{A+B}=Pr{A}+Pr{B}−Pr{AB}﻿ 

狭义计数概率规则(古典概型/几何概型): 基本事件数目/样本空间数目,所谓狭义,即只考虑最基本的Cnt(Subset)Cnt(U)\frac{Cnt(Subset)}{Cnt(U)}Cnt(U)Cnt(Subset)​﻿情况

广义计数概率规则: 在特定Pr{A}已知情况下 可能会推导Pr{A+B+C..}=Pr{A}+Pr{B}+Pr{C}...Pr\{A+B+C..\} = Pr\{A\} +Pr\{B\} +Pr\{C\} ... Pr{A+B+C..}=Pr{A}+Pr{B}+Pr{C}...﻿此时可能需要统计有多少个子集,来实现例如Pr{U}=Cn2∗Pr{Subset} Pr\{U\} = C_n^2* Pr\{Subset\}Pr{U}=Cn2​∗Pr{Subset}﻿ 我称这个为广义计数规则

计数原理: 这个术语见附录,代指Cnt(A)函数(以集合作为输入)的所有性质

对于该问题,我们采用特定Pr{subset}Pr\{subset\} Pr{subset}﻿方式, 此处选A[i]=iA[i]=iA[i]=i﻿,这样一个特殊的子序列子集

二.数组随机排序

均匀随机排序: 随机等概率产生AnnA_n^nAnn​﻿种排列

n3n^3n3﻿随机排序

代码

Premute-By-Sortinng(A)
{
	n = A.Length
	make a new array[1..n]
	for i=1 to n
		P[i] = RANDOM(1,n^3)
	Sort A, Using P as sort keys 
}

Copy

算法分析

本质上是一种随机产生优先级(称作Key)并排序的算法

这个算法复杂度并不是我们分析的重点,因为运行时间不因输入的具体分布而改变Θ(n+nlgn)=Θ(nlgn)\Theta(n+nlgn) = \Theta(nlgn)Θ(n+nlgn)=Θ(nlgn)﻿

但是算法的正确性需要分析: 包括两方面,Key冲突概率,以及在Key无冲突假设下是否满足均匀随机排列

Key冲突概率分析

唯一性图像

关键在于使用RANDOM(1,n^3)目的在于使得所有优先级唯一

如何证明每个每个元素优先级唯一的概率为1−1n1-\frac{1}{n}1−n1​﻿ ?

证明1: 事件个数/所有基本事件数目(写不下去)

Pr\{No\ Conflict\}= \frac{A_k^n}{k^n}=\frac{k!}{k^n*(k-n)!} \approx \frac{\sqrt{2\pi k}(\frac{k}{e})^k}{\sqrt{2\pi (k-n)}(\frac{k-n}{e})^{k-n}*k^n} \\ =\frac{\sqrt{k}}{\sqrt{k-n}}*(\frac{1}{e})^n*(\frac{k}{k-n})^{k-n} \\ Let\ k=n^3\\ \overset{>}{\approx} 1*(\frac{1}{e})^{n}*(\frac{n^2}{n^2-1})^{n^3-n} = 1*(\frac{1}{e})^{n}*(1+\frac{1}{n^2-1})^{(n^2-1)*n}\\ \overset{>}{\approx} \\

证明1: 利用ex≥x+1e^x\geq x+1ex≥x+1﻿ 放缩

Pr\{No\ Conflict\}= \frac{A_k^n}{k^n}=\frac{n}{n}\frac{n-1}{n}\frac{n-2}{n} ...\\ =(1-\frac{0}{n})(1-\frac{1}{n})(1-\frac{2}{n}) ...\\ (UpScale)\ 1-\frac{i}{n}\leq e^{(-\frac{i}{n})}\\ ~\\ Pr\{No\ Conflict\}\leq e^{-(\frac{0+1+2...+k}{n})}= e^{-(\frac{k(k+1)}{2n})}

证明2: 随机变量指示器⇒期望⇒马尔科⇒概率

定义A[i]为第i个分配的优先级(A[i]仅仅为自然生成顺序,还未排列)

随机变量指示器Xij=1 (当A[i]=A[j]) X_{ij} = 1 \  (当A[i]=A[j] )Xij​=1 (当A[i]=A[j])﻿

则有E(Xij)=n3n3∗n3=1n3E(X_{ij}) = \frac{n^3}{n^3*n^3} = \frac{1}{n^3}E(Xij​)=n3∗n3n3​=n31​﻿

E(X)=∑i,jAll (i,j) Combine1n3=(1+2+...n−1)∗1/n3 =n∗(n−1)2∗1n3 =n−12n2<1nE(X) = \sum\limits_{i,j}^{All\ (i,j) \ Combine} {\frac{1}{n^3}}\\

 = (1+2+...n-1) *1/n^3 \\
~\\
= \frac{n*(n-1)}{2} * \frac{1}{n^3} \\
~\\
= \frac{n-1}{2n^2} < \frac{1}{n}E(X)=i,j∑All (i,j) Combine​n31​=(1+2+...n−1)∗1/n3 =2n∗(n−1)​∗n31​ =2n2n−1​<n1​﻿

引理: 马尔科夫不等式 Pr{X≥a}≤E(X)aPr\{X \geq a\} \leq \frac{E(X)}{a}Pr{X≥a}≤aE(X)​﻿ 

则有Pr{X≥1}≤E(X)1≤1nPr\{X \geq 1\} \leq \frac{E(X)}{1} \leq \frac{1}{n}Pr{X≥1}≤1E(X)​≤n1​﻿

Pr{NoConflict}=1−Pr{X≥1}≥1−1nPr\{No Conflict\} = 1 - Pr\{ X\geq 1\} \geq 1 - \frac{1}{n}Pr{NoConflict}=1−Pr{X≥1}≥1−n1​﻿

均匀随机排列分析

定义和证明思路: 对于某一个特定的排列产生的概率为1n!\frac{1}{n!}n!1​﻿即可,剩下的其他排列都可以用归纳法即可

选择一个特殊排列: 对于Key[i]其优先级顺序恰好也为i的排列

对于A[1] 其 恰好为最大值的概略为Pr{A}=Pr{Rnak(Key[1]=1)}=1nPr\{A\}=Pr\{Rnak(Key[1]=1)\}=\frac{1}{n}Pr{A}=Pr{Rnak(Key[1]=1)}=n1​﻿

基础概率假设: 不同A[i]产生特定优先级的概率相等为1n\frac{1}{n}n1​﻿,且Pr{A∣B}=1n−1Pr\{A|B\}=\frac{1}{n-1}Pr{A∣B}=n−11​﻿

对于A[2]其 恰好为第二大值概率为

Pr{B}=Pr{Rank(Key[2])=2}=Pr{A}∗Pr{B∣A}=1n∗(n−1)Pr\{B\}=Pr\{Rank(Key[2])=2\} = Pr\{A\}*Pr\{B|A\} = \frac{1}{n*(n-1)}Pr{B}=Pr{Rank(Key[2])=2}=Pr{A}∗Pr{B∣A}=n∗(n−1)1​﻿ 

对于A[3] 同理 ...

最后有该特定排列产生的概率为1n!\frac{1}{n!}n!1​﻿

归纳可得每一种特定排列产生的概率1n!\frac{1}{n!}n!1​﻿, 满足均匀散列定义

Randomize-in-Place 原址交换随机排序

代码

Randomize-in-Place(A)
{
	n = A.length
	for i = 1 to n
		Swap A[i] with A[Random(i,n)]
}

Copy

均匀随机排列分析

利用循环不等式证明

循环不等式条件: 对于第i次迭代前,对于A[1..i-1]子数组而言,出现特定排列的概率为(n−(i−1))!n!=1n∗(n−1)∗(n−2)...n−(i−2)[TermNum(0..i−2)=i−1]\frac{(n-(i-1))!}{n!} = \frac{1}{n*(n-1)*(n-2)...n-(i-2)} [TermNum(0..i-2)=i-1]n!(n−(i−1))!​=n∗(n−1)∗(n−2)...n−(i−2)1​[TermNum(0..i−2)=i−1]﻿

 初始化: 第一次,显然为真,因为无子数组A[1..0]

保持: 对于第i次迭代满足(n−(i−1))!n!\frac{(n-(i-1))!}{n!}n!(n−(i−1))!​﻿ 第i次之后
Pr{AfterIter}=Pr{E2∣E1}∗Pr{E}Pr\{After Iter\} = Pr\{E_2 | E_1\} *Pr\{E\} Pr{AfterIter}=Pr{E2​∣E1​}∗Pr{E}﻿

则有Pr{AfterIter}=1n∗(n−1)∗(n−2)...n−(i−2)∗1n−(i−1)Pr\{After Iter\}= \frac{1}{n*(n-1)*(n-2)...n-(i-2)}*\frac{1}{n-(i-1)}Pr{AfterIter}=n∗(n−1)∗(n−2)...n−(i−2)1​∗n−(i−1)1​﻿

解决关键

则有 i+(TermNum)i=n+1i+(TermNum)_i = n+1i+(TermNum)i​=n+1﻿

(即第i次迭代前,第A[1..i-1]序列已经确定,只对剩下的n-(i-1)元素引入随机性

引入随机性: 对于已经确定A[1..i-1]特定序列下,对于第i个元素的选择,对于剩下的n-(i-1)元素都不具备特殊性,故各个可能的概率相等且平分1.为1n−(i−1)\frac{1}{n-(i-1)}n−(i−1)1​﻿ (特定Pr{子集}的概率推导方法,详见下面求取概率的思路)

同过程变量一起,可构成概率的数学归纳证明

举例: 第一次迭代i=1 (TermNum)i=n(TermNum)_i=n(TermNum)i​=n﻿ 则有Pr{A Certain Rank Set}=1nPr\{A\ Certain\ Rank\ Set\} = \frac{1}{n}Pr{A Certain Rank Set}=n1​﻿

三.其他随机过程分析

生日问题(1-Pr{A})

问题简介: 房间里有n人,请问有任意两个人生日重合的概率是多少

定义: A[i]为第i个人的生日

Pr{特定子集}证明 (基本等同于n^3随机排序的证明1,但是采用了特定子集方式思路而非狭义计数规则)

方便叙述Pr{A[i]=i}Pr\{A[i]=i\}Pr{A[i]=i}﻿记作Pr{Ai}Pr\{A_i\}Pr{Ai​}﻿

由于Pr{A[1]=1} Pr{A[1]=2}...Pr\{A[1]=1\}\ Pr\{A[1]=2\} ... Pr{A[1]=1} Pr{A[1]=2}...﻿并无特殊性,且互斥,故有
Pr{A[i]=m}=Pr{A[i]=k}=1/nPr\{A[i]=m\} = Pr\{A[i]=k\} = 1/n Pr{A[i]=m}=Pr{A[i]=k}=1/n﻿ (随机性引入其一)

Pr{A1A2..Ak}=1−PrA1∗Pr{A2∣A1}∗Pr{A3∣A1A2}...Pr{A1A2..Ak}=1n1n1n...=1nkPr\{A_1A_2..A_k\} = 1- Pr{A_1}*Pr\{A_2|A_1\}*Pr\{A_3|A_1A_2\} ... \\

Pr\{A_1A_2..A_k\} = \frac{1}{n}\frac{1}{n}\frac{1}{n}... = \frac{1}{n^k}
Pr{A1​A2​..Ak​}=1−PrA1​∗Pr{A2​∣A1​}∗Pr{A3​∣A1​A2​}...Pr{A1​A2​..Ak​}=n1​n1​n1​...=nk1​﻿

引入随机性: 显然该子集无特殊性(随机性引入其二),仅仅是集合 所有人生日不重合 中的一个子集,故其他子集的概率也和该子集相同

故总Pr{NoConflict}=AnknkPr\{NoConflict\} = \frac{A_n^k}{n^k}Pr{NoConflict}=nkAnk​​﻿

后续分析见Key冲突分析

随机变量指示器⇒期望⇒求取渐进阶数

思想根基: 有些时候,我们不关注概率本身,而是关注概率的复杂度问题(概率随规模变化的函数)

详细证明

设指示器XijX_{ij}Xij​﻿,当i和j生日为同一天时候该变量为1

则有E(Xij)=1∗Pr{Xij}=1/nE(X_{ij}) =1*Pr\{X_{ij}\} =1/nE(Xij​)=1∗Pr{Xij​}=1/n﻿ 
狭义计数规则: n为天数,取n=365,则有Pr{Xij}=365365∗365Pr\{X_{ij}\}=\frac{365}{365*365}Pr{Xij​}=365∗365365​﻿

则有设 随机变量X 为生日相同的对数 ,则有
E(X)=E(X12)+E(X13)...=Ck21nE(X)=E(X_{12}) +E(X_{13}) ... = C_k^2 \frac{1}{n} E(X)=E(X12​)+E(X13​)...=Ck2​n1​﻿其中k为总人数

则有 k(k−1)>2nk(k-1)>2nk(k−1)>2n﻿ 时候 E(X)>1E(X)>1E(X)>1﻿ 即 k>2n+1k>\sqrt{2n}+1k>2n​+1﻿ 

期望和概率的转换

为何此处不能使用马尔科不等式将期望转换为概率?而是只能求渐进?

球与箱子实验集

实验集: 实验集即实验本身的规则(生成样本空间的规则),我们往往只研究其中一个子集的概率或者期望.

球与箱子问题: 将相同的球扔往完全一致的的b个箱子

特定箱子问题(二项/几何分布)

投掷k个球,特定箱子中的球数目n: 二项分布B(k,1/b) 即
Pr{n=ni}=Ckni(1b)ni(1−1b)k−niPr\{n=n_i\} = C_k^{n_i} (\frac{1}{b})^{n_i} (1-\frac{1}{b})^{k-n_i}Pr{n=ni​}=Ckni​​(b1​)ni​(1−b1​)k−ni​﻿

特定箱子中需要多少个球才中: 几何分布

二者的关系其一: 

 ThrowNum/HitNum图像

考虑一个特殊二维离散随机变量的分布分别为 ThrowNum投掷/HitNum命中次数

特定箱子中需要多少个球才中: 考虑的是 HitNum = 1时候,ThrowNum为随机变量对应的的分布

投掷k个球,特定箱子中的球数目n: 考虑的是ThrowNum = k时候,HitNum 为随机变量对应的分布

礼卷收集问题

问题: 在每个b个框都有至少1个球,设投掷次数为随机变量X,求Pr{X=Xi}Pr\{ X=X_i\}Pr{X=Xi​}﻿分布

区别于问题: 给定k次投掷,设至少有一个球的框数目为随机变量X,求对应变量的分布

X=X1+X2...X= X_1 +X_2 ... X=X1​+X2​...﻿  X1X_1X1​﻿为有一个框里有球时候,投掷次数 X2X_2X2​﻿为第一个框里有球到第二个框里有球时候投掷次数

则有E(X1)=1 E(X2)=1/b−1b E(X3)=1/b−2b...E(X_1) = 1\ E(X_2) = 1/\frac{b-1}{b}\ E(X_3) = 1/\frac{b-2}{b} ...E(X1​)=1 E(X2​)=1/bb−1​ E(X3​)=1/bb−2​...﻿

则有E(X)=b(11+12...+1b)≈b(lnb+O(1))E(X) = b(\frac{1}{1}+\frac{1}{2} ... +\frac{1}{b} ) \approx b(lnb+O(1))E(X)=b(11​+21​...+b1​)≈b(lnb+O(1))﻿  

特征序列问题