概率分析和随机算法
5.1 雇用问题
运用概率分析对算法代价进行估算。
当算法行为不仅由输入决定，还由随机数生成器决定，则称该算法为随机的。
对于这个雇用问题，两种描述是不一样的：
- 第一种是每天会来不一样的面试者，对应输入随机的情况。讨论平均情况的运行时间
- 第二种是已知所有的面试者名单，通过随机数来每天抽取一个面试者，这种是本身随机行为的算法。讨论期望运行时间
5.2 指示器随机变量
该节首先定义了指示器：给定样本空间为S，某个事件为A。一个随机变量为$X_A$,对应指示器随机变量$I{A}$。若事件发生，该指示器值为1，否则为0.
引理5.1: $E[X_A]=P(A)$。
5.3 随机算法
设计一个分布，使任意的输入都有等可能的排列形式。
比如在雇佣问题中。
当输入从小到大排列，会一直更新最大值，而从大到小排列输入的话，只会更新一次最大值。
随机算法通过随机数生成器，重新构造一个随机的排列。让所有的输入都不会有极端的执行结果。
见例子：随机排列数组。
5.4 随机算法的例子
5.4.1 生日悖论
k个人，其中两个人生日相同的概率有1/2，k至少为多少。
该节首先使用了我们熟悉的概率论方法计算。
然后使用指示器随机变量分析。
- $1\le i\lt j \le k$
- $X_{ij}=I{i和j生日相同}$
- $E[X_{ij}]=1/n$
- 然后计数器累加。
X=0
for i = 1 -> k
for j = i+1 -> k
X += E[Xij]
- $E[X]=\frac{k(k-1)}{2n}$
- 如何使用该随机变量呢？X指示该房间中，生日相同的人有多少对。当该值为1，就是想计算的结果。
注意使用随机变量指示器的结果与概率方法不相同。
第一种：确定至少一对人生日相同概率为1/2，需要多少人。
第二种：期望有一对人生日相同。
两者渐进阶数相等。
看书都能看出来，指示器为我们的随机算法分析带来了便利。