CLRS5 概率分析和随机算法

2017-05-07 | 阅读：次

随机与期望运行时间

当输入是随机时，称运行时间为平均运行时间。
当算法本身做出随机选择时，称随机算法的运行时间为期望运行时间。

5.1 雇用问题

练习5.1-1 Show that the assumption that we are always able to determine which candidate is best in line 4 of procedure HIRE-ASSISTANT implies that we know a total order on the ranks of the candidates.、

因为总能知道哪个最佳，所以知道所有排序。

练习5.1-2 Describe an implementation of the procedure RANDOM(a, b) that only makes calls to RANDOM(0, 1). What is the expected running time of your procedure, as a function of a and b?

RANDOM(a, b)
    while a < b
        if Random(0, 1)
            a = (a+b) // 2
        else
            b = (a+b) // 2
    return a

运行时间: Θ(lg(b-a))

练习5.1-2 Suppose that you want to output 0 with probability 1/2 and 1 with probability 1/2. At your disposal is a procedure BIASED-RANDOM, that outputs either 0 or 1. It outputs 1 with some probability p and 0 with probability 1 - p, where 0 < p < 1, but you do not know what p is. Give an algorithm that uses BIASED-RANDOM as a subroutine, and returns an unbiased answer, returning 0 with probability 1/2 and 1 with probability 1/2. What is the expected running time of your algorithm as a function of p?

RANDOM()
    while True
        a = BIASED-RANDOM()
        b = BIASED-RANDOM()
        if a != b
            return a

期望运行时间： 1/(2p(1-p))

5.2 指示器随机变量

平均情况下的雇用次数只有lnn

练习5.2-1 In HIRE-ASSISTANT, assuming that the candidates are presented in a random order, what is the probability that you will hire exactly one time? What is the probability that you will hire exactly n times?

1/n
1/n!

练习5.2-2 In HIRE-ASSISTANT, assuming that the candidates are presented in a random order, what is the probability that you will hire exactly twice?

当第一个雇员质量为k,比他质量高的n-k个雇员中质量最高的一个要在最前面，概率是1/(n-k),然后求和

练习5.2-3 Use indicator random variables to compute the expected value of the sum of n dice.

v = 3.5*n

练习5.2-4 Use indicator random variables to solve the following problem, which is known as the hat- check problem. Each of n customers gives a hat to a hat-check person at a restaurant. The hat- check person gives the hats back to the customers in a random order. What is the expected number of customers that get back their own hat?

(1/n) * n = 1

练习5.2-4 Let A[1…n] be an array of n distinct numbers. If i < j and A[i] > A[j], then the pair (i, j) is called an inversion of A. (See Problem 2-4 for more on inversions.) Suppose that each element of A is chosen randomly, independently, and uniformly from the range 1 through n. Use indicator random variables to compute the expected number of inversions.

正序和逆序概率一样，n(n-1)/2/2

5.3 随机算法(一个随机算法通常是解决一个问题最简单、最有效的方法)

雇用问题

RANDOMIZED-HIRE-ASSISTANT(n)
    randomly permute the list of candidates
    best = 0
    for i = 1 to n
        interview candidate i
        if candidate i is better than candidate best
            best = i
            hire candidate i

期望运行时间是O(lnn)

随机排列数组

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-PLAC(A)
    n = A.length
    for i = 1 to n
        swap A[i] with A[RANDOM(i, n)]

练习5.3-1 Professor Marceau objects to the loop invariant used in the proof of Lemma 5.5. He questions whether it is true prior to the first iteration. His reasoning is that one could just as easily declare that an empty subarray contains no 0-permutations. Therefore, the probability that an empty subarray contains a 0-permutation should be 0, thus invalidating the loop invariant prior to the first iteration. Rewrite the procedure RANDOMIZE-IN-PLACE so that its associated loop invariant applies to a nonempty subarray prior to the first iteration, and modify the proof of Lemma 5.5 for your procedure.

那可以把空数组独立出来，把长度为一作为初始条件吗？

练习5.3-2 Professor Kelp decides to write a procedure that will produce at random any permutation besides the identity permutation. He proposes the following procedure: PERMUTE-WITHOUT-IDENTITY(A) 1 n ← length[A] 2 for i ← 1 to n
3 do swap A[i] ↔ A[RANDOM(i + 1, n)]

没有实现。这样的话像[1,3,2...]等排列就无法产生。

练习5.3-3 Suppose that instead of swapping element A[i] with a random element from the subarray A[i .. n], we swapped it with a random element from anywhere in the array: PERMUTE-WITH-ALL(A) 1 n ← length[A] 2 for i ← 1 to n 3 do swap A[i] ↔ A[RANDOM(1, n)] Does this code produce a uniform random permutation? Why or why not?

See https://blog.codinghorror.com/the-danger-of-naivete/
我用正确算法排列 [1,2,3] 1000万次，得到的各个排列出现次数分别为 1666677 1668937 1667071 1664804 1665172 1667339
而用上面的算法，得到的是 1666800 1666468 1667281 1666158 1664742 1668551
好像差不多……

练习5.3-4

很明显不对。。。
只会产生n种选择，应该要n!种。

练习5.3-5 Prove that in the array P in procedure PERMUTE-BY-SORTING, the probability that all elements are unique is at least 1 - 1/n.

很基础的证明，证 1(1-1/n^3)(1-2/n^3)(1-3/n^3)…… >= 1-1/n就好了~

练习5.3-6 Explain how to implement the algorithm PERMUTE-BY-SORTING to handle the case in which two or more priorities are identical. That is, your algorithm should produce a uniform random permutation, even if two or more priorities are identical.

有相同的再排一次，直到都不同为止。

练习5.3-7

RANDOM-SAMPLE(m, n)
    if m == 0 
        return {}
    else 
        S = RANDOM-SAMPLE(m-1, n-1)
        i = RANDOM(1, n)
        if i in S
            S = S +｛n｝
        else S = S + {i}
        return S

用归纳法可以证出来。

5.4

在线雇用问题

ONLINE-MAXIMUM(k, n)
    for i = 1 to k
        if score(i) > bestscore
            bestscore = score(i)
    for i = k + 1 to n
        if score(i) > bestscore
            return i

练习5.4-1 How many people must there be in a room before the probability that someone has the same birthday as you do is at least 1/2? How many people must there be before the probability that at least two people have a birthday on July 4 is greater than 1/2?

253

613

练习5.4-2 Suppose that balls are tossed into b bins. Each toss is independent, and each ball is equally likely to end up in any bin. What is the expected number of ball tosses before at least one of the bins contains two balls?

这也是生日问题
https://en.wikipedia.org/wiki/Birthday_problem

练习5.4-3 For the analysis of the birthday paradox, is it important that the birthdays be mutually independent, or is pairwise independence sufficient? Justify your answer.

Pairwise independence is sufficient.

练习5.4-4 How many people should be invited to a party in order to make it likely that there are three people with the same birthday?

1-(364^n+364^(n-1)*n+364^(n-2)*n*(n-1))/365^n >= p

练习5.4-5 What is the probability that a k-string over a set of size n is actually a k-permutation? How does this question relate to the birthday paradox?

p = 1-((k-1)!^n)/((k!)^n)

练习5.4-6 Suppose that n balls are tossed into n bins, where each toss is independent and the ball is equally likely to end up in any bin. What is the expected number of empty bins? What is the expected number of bins with exactly one ball?

都是n/e
算出来有一个bin空，就大概是第一问
然后有一个bin刚好有1个球，是第二问
http://clrs.skanev.com/05/04/06.html

思考题

5-1

https://en.wikipedia.org/wiki/Approximate_counting_algorithm
这个算法好神奇
概率算法都好神奇啊
每次的期望都是1,n次就是n喽

方差懒得算了

5-2

a.
RANDOM-SEARCH(A, x)
    S = set()
    while True
        i = RANDOM(1, len(A)
        S.add(i)
        if A[i] == x
            return i
        if len(S) == len(A)
            return -1

b. n

c. n/k

d. nlnn 直接用结论

e. n/2, n

f. n/(k+1), n-k+1

g. n, n

h. n, n, n, n/2

i. 第二种……其它都太坑了

Sasuke

Jing

CLRS5 概率分析和随机算法

随机与期望运行时间

5.1 雇用问题

5.2 指示器随机变量

5.3 随机算法(一个随机算法通常是解决一个问题最简单、最有效的方法)

5.4

思考题