第五章：Probabilistic Analysis and Randomized Algorithms
通过人员招聘问题，引入算法的随机性分析，最好、最差、期望运行时间分析。介绍并证明随机洗牌算法。最后介绍了几个有趣的应用。
生日悖论：至少需要多少个人才能保证有50%的可能性使得其中两人的生日相同？
不妨假设一年有n(n = 365)天，人数为k。所有k个人生日不同的概率为 A(n, k) / n^k = n! / ((n-k)! n^k)，令该式小于1/2，解得k >= 23
另外，可以求近似解：假定知道i的生日，则j的生日与i相同的概率是1/n，因此期望生日相同的人数对为C(k, 2)*1/n = k*(k-1)/2n，令该式大于1，解得k>=28，也即至少28个人中，我们期望能找到两个人的生日相同。
Coupon Collector's Problem: 有b种礼券，每次收到每种礼券的概率相等，问期望收集多少份礼券之后能集齐所有礼券。
假设已经收集了i-1种礼券，则下一次收集到新礼券的概率是b-i+1/b，期望次数是b/(b-i+1)，因此第i次收集到新礼券的期望次数是b/(b-i+1)，于是集齐礼券的期望次数是1 + b/(b-1) + ... + b/1 = b(1 + 1/2 + 1/3 + ... + 1/b) = b(lnb + O(1) （调和级数收敛到lnb，可以用积分上下界方法证明）
Streaks: 扔一枚均匀（正反面出现概率相等）的硬币n次，则连续的正面朝上或朝下次数的期望是多少呢？
O(lgn)
证明比较复杂，以后再看……
人员招聘问题：假设有n个候选人，首先查看前k个候选人，记录最高分，再检查剩下的候选人，如果比之前记录的最高分要好，则雇佣该人。如果都比之前的最高分低，则雇佣最后一个人。
可以证明，雇佣到最优候选人的概率是k/n * \sum\_{i=k}^{n-1} 1/i，通过积分方法确定上下界，可以求得k = n/e时最大概率是1/e，真的很神奇！
5.1-2
RANDOM(a, b) = RANDOM(0, b-a) + a, assume 2^{k-1} < b-a <= 2^k, then invoke RANDOM(0, 1) k times, convert binary to digit, if bigger than b then drop else use
5.1-3
01 -> 0, 10 -> 1, both have probability of p(1-p), expected running time is O(1/2p(1-p))
5.2-1
if the best candidate is in 1st order, then hire one time, the probability is 1/n;
if the candidates are in ascending order, then hire n times, the probability is (1/n)*(1/(n-1))*...*1 = 1/n!
5.2-2
candidate 1 has rank i <= n-1, while all candidates whose ranks are i+1, i+2, ..., n-1 must be interviewed after the candidate whose rank is n.
\sum_{i=1}^{n-1}1/(n-i) * 1/n
5.2-3
1*1/n + 2*1/n + ... + n*1/n = (n+1)/2
5.2-4
everyone has a change of 1/n to get his own hat back, so the expected number is n * 1/n = 1
5.2-5
there are n*(n-1)/2 pairs, and each pair has a probability of 1/2 to be inversion, so the expected number of inversions is n*(n-1)/4
5.3-2
NO. for any i, A[i] will be swap to A[i+1..n], it can't stay where it was
5.3-3
NO. this will produce n^n permutations, but we just want n!, and n^n maybe can't be divided by n!
5.4-6
for each of the n bins, the probability for any bin to be empty is (1 - 1/n)^n, so the expected number of empty bin is n * (1 - 1/n)^n, as n approaches infinite, (1 - 1/n)^n approaches 1/e, so the expected number approaches n/e;
for each of the n bins, the probability for any bin to get exactly one ball is C(n, n-1)(1 - 1/n)^{n-1}1/n = (1 - 1/n)^{n-1}, so the expected number is n * (1 - 1/n)^{n-1}, as n approaches infinite, the expected number approaches n^2/(e(n-1))
Problem 5-1
a. for each INCREMENT, it has 1/(n_{i+1} - n_i) probability to increase n_{i+1} - n_i, so the expected increase value is 1, that means, after n times such operation, the expected value will be n
b. with 1/100 probability to increase 100, and 99/100 to stay the same, for each operation, Var = E(X^2) - E(X)^2 = (0^2 * 99/100 + 100^2 * 1/100) - 1 = 99. so the final Var is 99n
No comments:
Post a Comment