算法导论学习笔记（四） 初稿

5.1 雇用问题

5.2 指示器随机变量

个人感觉与独立重复试验类似

核心：将问题分解为子问题

应聘者问题的指示器随机变量解法 E[X]=∑x=1nxP{X=x}=∑i=1nE[xi]=∑i=1n1/i=lnn+O(1) $$E[X]=/sum_{x=1}^n xP /{ X=x /}= /sum_{i=1}^n E[x_i]=/sum_{i=1}^n 1/i=lnn+O(1)$$

关于例题

帽子核对问题 对于每个顾客，拿到自己的帽子的概率为1/n$1/n$，故其数学期望为∑ni=11/n=1$/sum_{i=1}^n 1/n =1$

逆序对问题 对于每一组数的组合，都有一半的概率为逆序，故其数学期望为C2n⋅12=n(n−1)/4$C_n^2 /cdot /frac 1 2 =n(n-1)/4$

5.3 随机算法

含义 让分布固定，而通过特定算法实现随机化。

随机排列数组

PERMUTE-BY-SROTING

RANDOMIZE-IN-PLACE

证明

初始化：初始化赋值i=2（涉及讨论i=1的空数组，故先显式交换一次），即对于每个1排列，长度为1的子数组包含这种排列的概率为 (n−1)!/n!=1/n$(n-1)!/n!=1/n$，第一次循环迭代前循环不变式成立。

保持：假设i次迭代前每种(i-1)排列出现概率为(n−i+1)!/n!$(n-i+1)!/n!$，则第i次迭代后，概率为1n−i+1⋅(n−i+1)!n!$/frac{1}{n-i+1} /cdot /frac{(n-i+1)!}{n!}$

终止：终止时，i=n+1，子数组任一排列概率为1/n!$1/n!$

5.4 特征序列

问题：抛一枚标准硬币n次，求最长连续正面的数学期望

思路： 类似夹逼准则

证明过程：

O(lgn)

设连续掷硬币k次，k=2lgn。

起始于某一位置，长度**大于等于**k的序列至多有n-k+1个，故开始于任一位置的概率总和小于等于 ∑i=1n−k+11/2k≤∑i=1n−k+11/n2<∑i=1n1/n2=1/n $$/sum_{i=1}^{n-k+1} {1/2}^k /leq /sum_{i=1}^{n-k+1} 1/n^2 < /sum_{i=1}^n 1/n^2 = 1/n$$

由定义知 E[L]=∑j=0njP{Lj}=∑j=0k−1jP{Lj}+∑j=knjP{Lj} $$E[L]=/sum_{j=0}^n jP/{L_j/}=/sum_{j=0}^{k-1} jP/{L_j/} + /sum_{j=k}^n jP/{L_j/}$$ 其中j为长度的具体值。

显然，当j较大时P{Lj}$P/{L_j/}$较小，当P{Lj}$P/{L_j/}$较大时j较小，故 E[L]<∑j=0k−1kP{Lj}+∑j=knnP{Lj}<k∑j=0k−1P{Lj}+1 $$E[L]</sum_{j=0}^{k-1} kP/{L_j/} + /sum_{j=k}^n nP/{L_j/}<k/sum_{j=0}^{k-1}P/{L_j/}+1$$ 又因为∑k−1j=0P{Lj}<1$/sum_{j=0}^{k-1}P/{L_j/}<1$，原式小于O(k)=O(lgn)$O(k)=O(lgn)$

Ω(lgn)

把n次投掷划分为n/s组，每组掷s次，s取lgn/2。

显然任一一组，结果为同一面（假设为正面）概率为 1/2s=1/n√ $$1/2^s=1//sqrt n$$

故每组都不是同一面概率为 (1−1/n√)n/s−1≤e(n/s−1)/n√=O(e−lgn=O(1/n)) $$(1-1/ /sqrt n)^{n/s-1} /leq e^{(n/s-1)/ /sqrt n} = O(e^{-/lg n} = O(1/n))$$

对j值较小的部分，其值忽略不计，因此 ∑j=0njP{Lj}≥∑j=snjP{Lj}≥s∑j=snP{Lj}≥s(1−O(n))=Ω(lgn) $$/sum_{j=0}^n jP/{L_j/} /geq /sum_{j=s}^n jP/{L_j/} /geq s/sum_{j=s}^nP/{L_j/} /geq s(1-O(n))=/Omega (/lg n)$$

结论：特征序列长为lgn。

指示器随机变量的近似结果：n−k+12k$/frac{n-k+1}{2^k}$，且带入k=lgn时值近似符合要求。

5.5 在线雇佣问题

问题：只雇佣一次应聘者，并且每次应聘必须决定是否雇佣这个人。

实现思路：选择一个正整数k，面试并拒绝前k个应聘者，并雇佣后面第一个分数比前k个应聘者中分最高者还高的人，若没有则雇佣最后一个人。问题转化为寻找k的最优值。

过程：

令P{Si}$P/{S_i/}$表示应聘者为第i时面试成功的概率，Bi$B_i$表示最佳面试者为第i人的概率，M(j)$M(j)$表示前1~j人中的最高分，Oi$O_i$表示从k+1到i-1的应聘者都小于M(k)$M(k)$的概率。

显然 P{S}=∑i=k+1nP{Si} $$P/{S/}=/sum_{i=k+1}^{n}P/{S_i/}$$ P{Bi}=1/n $$P/{B_i/}=1/n$$ P{Oi}=k/(i−1) $$P/{O_i/}=k/(i-1)$$ P{Si}=P{Bi}⋅P{Oi} $$P/{S_i/}=P/{B_i/} /cdot P/{O_i/}$$

解得 P{S}=kn(lnn−lnk)$P/{S/}= /frac{k}n (/ln n - /ln k)$

求导，得k=n/e$k=n/e$