5.3 Randomized algorithms Algorithms


Summary



다음 알고리즘은 5.1절의 HIRE-ASSISTANT(n) 알고리즘에서 랜덤 순서로 들어온다는 가정을 실제로 랜덤하게 구현한 알고리즘이다.

RANDOMIZED-HIRE-ASSISTANT(n)
1 randomly permute the list of candidates
2 best = 0
// candidate 0 is a least-qualified dummy candidate
3 for i = 1 to n
4 interview candidate i
5 if candidate i is better than candidate best
6 best = i
7 hire candidate i

Lemma 5.3
The expected hiring cost of the procedure RANDOMIZED-HIRE-ASSISTANT is O(ch ln n).

Proof 
After permuting the input array, we have achieved a situation identical to that of the probabilistic analysis of HIRE-ASSISTANT.

Lemma 5.2 와 5.3의 차이 : 5.2는 랜덤 순서를 '가정'하고, 5.3은 가정하지 않고 실제로 랜덤 순서를 구현한다.



Randomly permuting arrays

다음은 P배열 요소에 랜덤한 가중치를 대입하고 P를 정렬key로 사용해 A배열의 순서를 바꾸는 알고리즘이다.

PERMUTE-BY-SORTING(A)
1 n = A.length
2 let P[1..n] be a new array
3 for i = 1 to n
4 P[i] = RANDOM(1,n3)
5 sort A, using P as sort keys

※ 가정 : P에서 모든 우선순위는 유일하다. ( 즉, 중복되는 요소가 없다. )

관련문제
5.3-5은 P의 모든 요소가 유일할 확률이 최소 (1 - 1/n)인 확률을 증명해야한다.
5.3-6은 P의 요소 중 동일한 값이 두 개 또는 그 이상 일 때 알고리즘을 구현하는 방법을 물어본다.

문제점
이 procedure가 uniform random permutation을 만드는지를 증명해야한다.

Lemma 5.4
Procedure PERMUTE-BY-SORTING produces a uniform random permutation of the input, assuming that all priorities are distinct.

proof   $$\begin{align*} \text{Pr}\{ E_{1} \cap E_{2} \cap E_{3} \cap \cdots \cap E_{n-1} \cap E_{n} \} &= \left ( \frac{1}{n} \right ) \left ( \frac{1}{n-1} \right ) \cdots \left ( \frac{1}{2} \right ) \left ( \frac{1}{1} \right ) \\ &= \frac{1}{n!} \ , \end{align*}$$

n개의 요소 중 가장 작은 우선순위를 뽑는 확률은 1/n 이다. 다음으로 n-1개 요소중 가장 작은 우선순위를 뽑는 확률은 1/n-1 이다. 모든 요소가 가장 작은 우선순위를 가질 수 있기 때문이다. 이런 식으로 계속하다보면 1/n-(i-1) 이 나온다.


랜덤 순열을 만드는 더 좋은 방법은 적소에 주어진 배열을 순열시키는 것이다.

PERMUTE-IN-PLACE(A)
1 n = A.length
2 for i = 1 to n
3 swap A[i] with A[RANDOM(i,n)]

Lemma 5.5
Procedure RANDOMIZE-IN-PLACE computes a uniform random permutation.

proof  
see 127p of the book.
( 이해 안가는 점 : 증명에서 i-1 부분을 왜 증명하려고 하는지 아무리 생각해도 모르겠다. 범위는 i부터 n까지 인데...)

랜덤화된 알고리즘은 문제를 풀기 위한 가장 단순하고 가장 빠른 방법이다. 





Exercises



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. He reasons that we 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.

  • loop 시작 전에 무작위로 배열에서 한 개를 뽑고 그것을 첫 번째 요소와 바꾸면 된다.


5.3-2
Professor Kelp decides to write a procedure that produces at random any permutation besides the identity permutation. He proposes the following procedure:

PERMUTE-WITHOUT-IDENTITY(A)
1 n = A.length
2 for i = 1 to n-1
3 swap A[i] with A[RANDOM(i+1, n)]

Does this code do what Professor Kelp intends?

  • 그렇지 않다. 이 procedure는 매번 랜덤하게 배열의 자리를 바꾼다.


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

Does this code produce a uniform random permutation? Why or why not?

  • 만들지 못한다.

    e.g. n=3 이라고 하자. 각 자리마다 세 개 수 중 하나를 선택하여 교환하므로 가지수는 3 * 3 * 3 = 27 이고 확률은 1/27 이다. 3개 수를 순열하면 3! = 6 이다. 각 순열을 가질 확률은 1/6 이다. 이 코드에서의 교환은 중복된 k순열을 만드므로 k/27 확률이다. Since k/27 ≠ 1/6, thus, this code doesn't produce a uniform random permutation. 


5.3-4
Professor Armstrong suggests the following procedure for generating a uniform random permutation:

PERMUTE-BY-CYCLIC(A)
1 n = A.length
2 let B[1..n] be a new array
3 offset = RANDOM(1,n)
4 for i = 1 to n
5 dest = i + offset
6 if dest > n
7 dest = dest - n
8 B[dest] = A[i]
9 return B

Show that each element A[i] has a 1/n probability of winding up in any particular position in B. Then show that Professor Armstrong is mistaken by showing that the resulting permutation is not uniformly random.

  1. A[i]에서 i가 1씩 증가하면서 A[1]부터 A[n]이 B[dest] 에 들어가므로 확률은 1/n 이다.

  2. B 배열이 시작되면 A[1]부터 A[n]이 순서가 바뀌지 않은 채 고정되서 들어간다. Thus, this code isn't a uniform random permutation.


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.

\[ \begin{align*} \Pr\{1 \cap 2 \cap 3 \cap \ldots\} &= \Pr\{1\} \cdot \Pr\{2 | 1\} \cdot \Pr\{3 | 1 \cap 2\} \cdots \\ &= 1 \bigg(1 - \frac{1}{n^3}\bigg) \bigg(1 - \frac{2}{n^3}\bigg) \bigg(1 - \frac{3}{n^3}\bigg) \cdots \\ &\ge 1 \bigg(1 - \frac{n}{n^3}\bigg) \bigg(1 - \frac{n}{n^3}\bigg) \bigg(1 - \frac{n}{n^3}\bigg) \cdots \\ &\ge \bigg(1 - \frac{1}{n^2}\bigg)^n \\ &\ge 1 - \frac{1}{n} &&(\text{by  } (1-x)^{n} \geq 1-nx) \\ \end{align*} \]



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.

  1. Initialize P with P[i]=i for i=1,…,n.

  2. Repeat for i=1,…,n−1:
        Let j be a random number in the range i,…,n.
        Swap P[i] and P[j].
이 방법은 효율성이 떨어지므로 PERMUTE-IN-PLACE 를 쓰는 게 낫다.



5.3-7
Suppose we want to create a random sample of the set {1,2,3, ... , n}, that is, an m-element subset S, where 0 ≤ m ≤ n, such that each m-subset is equally likely to be created. One way would be to set A[i] = i for i = 1,2,3, ... , n, call RANDOMIZE-IN-PLACE(A), and then take just the first m array elements. This method would make n calls to the RANDOM procedure. if n is much larger than m, we can create a random sample with fewer calls to RANDOM. show that the following recursive procedure returns a random m-subset S of {1,2,3, ... , n}, in which each m-subset is equally likely, while making only m calls to RANDOM:

RANDOM-SAMPLE(m,n)
1 if m == 0
2 return ∅
3 else
4 S = RANDOM-SAMPLE(m-1,n-1)
5 i = RANDOM(1,n)
6 if i ∈ S
7 S = S∪{n}
8 else
9 S = S∪{i}
10 return S

  • m이 0이 될 때까지 계산하므로 요소가 총 m개인 부분집합을 가진다.

    재귀 때마다 n의 값은 -1이 되므로 S가 같은 요소를 가질 수가 없다.

    Probability : 1 /
    nCm




References