概率分析算法经典案例

雇用问题（概率分析和随机算法）

伪代码

HIRE-ASSISTANT(n)

best = 0

for i=1 to n

interview candidate i

if candidate i is better than candidate best

best = i

hire candidate i //直接雇用他，产生雇用费用

最坏情况，将会雇用所有的人。(如果，从坏到好依次排序）

Xa = 1 如果A发生　　 0 如果A没有发生

E[Xa] = Pr{A}

高中知识：欲求X的期望，X可取的值有1,2,3，，，，，n。然后分别列出取每个值时的概率---

X　　1　　 2　　3，，，，n

P　　p1　　p2 p3，，，pn

E[X] = ∑xPr{X=x}来求期望

第i个应聘者，比前面的所有人都好的概率为 1/i

因此E[X] = 1+1/2+1/3+...+1/n = lnn + O(1)

即，大约雇用其中的 lnn 个人（ln底数为2）

随机排列数组

方法一：得到一个随机排列的数组，一个通常的方式是：为每个元素A[i],赋一个随机的优先级P[i],然后依据优先级对数组中的元素进行排序。

PERMUTE-BY-SORTING(A)

n = A.length

let P[1...n] be a new array

for i = 1 to n

P[i] = RANDOM(1, n^3)

sort A, using P as sort keys

方法二：

RANDOMIZE-IN-PLACE(A)

n = A.length

for i=1 to n

swap A[i] with A[RANDOM(i,n)]

生日悖论

一个屋子里人数必须要达到多少，才能使其中两人生日相同的机会达到50%？

不考虑闰年（即每年365天），假设有k个人

两人生日在同一天的概率为 1/n，即（1/365）

至少两人生日相同的概率，等于 1-所有人生日都不同的概率

事件Ai 表示，第i个人，与他前面的所有人生日都不同。

那么,k个人生日都不同的概率Bk为

Bk = A1 ∩ A2 ∩ A3 ∩ ...Ak

= Ak ∩ Bk-1

Pr{Ak | Bk-1} = n-(k-1) /n = n-k+1 / n

Pr(Bk) = Pr{Bk-1} Pr{Ak | Bk-1}

= Pr{Bk-2} Pr{Ak-1 | Bk-2} Pr{Ak | Bk-1}

= Pr{B1} Pr{A2 | B1} Pr{A3 | B2}... Pr{Ak | Bk-1}

= 1 * n-1/n * n-2/n ..... * n-k+1/n

具体推导，看书 p74

根据1+x<=e^x

Pr{Bk} <= e^(-1/n-2/n…-(k-1)/n) <= 0.5

K(k-1) >= 2nln2

当n=365时，解得k>=23。

球与箱子

把相同的球随机投到b个箱子里，每次投中一个空箱子称为一次命中。我们想知道命中b次，大约需要投多少次。（即使得每个箱子都有球）

算法：

分成1,2,3...i....b个阶段，每个阶段所投的球都是为了获得一次命中。对于第i个阶段的每次投球，获得命中的概率为 (b-i+1)/b

那么，第i个阶段获得一次命中大约要投 b/(b-i+1)次球

故有： ∑(1~b) b/(b-i+1) = b∑(1~b) 1/(b-i+1)

根据调和级数方程：1+1/2+1/3+1/4+...1/n = ln(n) + O(1)

最终大约要投 blnb 次

特征序列

问题：抛一枚均匀硬币n次，期望看到连续正面的最长序列有多长？

解法一：定义Aik为长度至少为k的正面序列开始于第i次抛掷，即第i,i+1,…,i+k-1次硬币是正面，所以有Pr{Aik} = 1/ 2^k

对于k = 2ceil(log n)

因此，长度至少为2ceil(log n)的一个起始于位置i的正面序列概率是很小的

而长度至少为2ceil(log n)的起始于任意位置的正面序列的概率是：

定义Lj：最长正面序列长度正好是j的事件（不相交）

假设最长序列的长度是L