5. Probabilistic Analysis and Randomized Algorithms

5.1. The hiring problem

사람을 채용하는 문제를 생각해 보자. 각각의 사람을 면접보는 데는 비용이 들고, 지금 면접 보는 사람이 지금까지의 면접자들 중에 가장 우수하다면 지금 채용된 사람을 해고하고 그 사람을 채용한다고 하자. 알고리즘으로 쓰면 다음과 같다.

HIRE-ASSISTANT(n)
best = 0 // candidate 0 is a least-qualified dummy candidate
for i = 1 to n
    interview candidate i
    if candidate i is better than candidate best
        best = i
        hire candidate i

이 알고리즘의 시간 복잡도는 어떻게 될까? c_i를 면접 비용, c_h를 채용 비용이라고 하면 채용되는 (중간에 잘리는 사람 포함) 사람을 m명이라 할 때 시간 복잡도는 O(c_{1} n + c_{h} m)이 된다. 이 때 c_{1} n은 상수이므로 고려에서 배제하도록 하자.

Worst-case analysis

최악의 경우는 면접자의 퀄리티가 나쁜 순서부터 면접을 보게 되는 것이다. 이 경우에는 채용하고 해고하는 과정을 n번 반복하게 되므로 시간 복잡도는 O(c_{h} n)이다.

Probabilistic analysis

확률적 분석은 확률을 이용해서 문제를 분석하는 것이다. 보통은 알고리즘의 시간 복잡도를 분석할 때 쓰인다. 이를 위해서는 입력의 분포를 알아야 하는데, 이 때는 보통 평균 수행 시간을 주로 분석한다. 입력의 분포를 모르는 문제라면 확률적 분석을 할 수 없다.

채용 문제에 대해서 분포를 생각해보자면 이는 균일 무작위 순열이 됨을 알 수 있다.

Randomized algorithms

확률적 분석에서 어떤 문제의 입력 분포를 모델링했다고 해도 입력이 진짜로 그 분포에서 무작위로 오는지는 알 수 없다. 이를 위해 무작위성에 대한 가정을 추가한다. 무작위성을 가진 알고리즘은 입력뿐만 아니라 난수 생성기에도 영향을 받는 것을 말한다. 대부분의 프로그래밍 환경에서는 유사난수 생성기를 지원한다. 무작위 알고리즘의 수행 시간을 분석할 때는 분포에 대한 기대값을 취해 기대 수행 시간을 계산한다.

5.2. Indicator random variables

사건 A의 지시확률변수\mathbf{1}_{A}이며 A가 발생하면 1, 발생하지 않으면 0인 확률변수이다.

Lemma 5.1. 표본공간 S 내 사건 A에 대해, X_{A} = \mathbf{1}_{A}의 기대값은 P(A)이다.

Analysis of the hiring problem using indicator random variables

채용 문제에서 X를 채용하는 횟수를 나타내는 확률변수라 하자. 기대값은 E[X] = \sum_{x=1}^{n} x P(x)가 된다. 이 때 관점을 바꿔서 X_{i}를 i번째 후보의 채용에 대한 지시확률변수라고 놓자. 그러면 X = X_{1} + \cdots + X_{n}이 된다. 이 때 i번째 후보가 채용될 확률은 1~i번째 후보들 중에 그 후보가 제일 나을 확률이기 때문에 1/i가 된다. 따라서 기대값은 E[X] = E[\sum_{i=1}^{n} X_{i}] = \sum_{i=1}^{n} E[X_{i}] = \sum_{i=1}^{n} \frac{1}{i} = \ln n + O(1) 이다.

Lemma 5.2. 후보가 무작위 순서로 들어올 때, HIRE-ASSISTANT의 평균 채용 비용은 O(c_{h} \ln n)이다.

5.3. Randomized algorithms

채용 문제는 결정론적 알고리즘이고 무작위 알고리즘은 아니다. 같은 입력에 대해서는 언제나 같은 사람들이 채용되고 해고되기 때문이다. 이를 무작위 알고리즘으로 만들기 위해서는 무작위 순열로 뒤섞어야 한다.

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

Lemma 5.3. RANDOMIZED-HIRE-ASSISTANT 알고리즘의 기대 채용비용은 O(c_{h} \ln n)이다.

Randomly permuting arrays

무작위 순열로 뒤섞는 알고리즘은 다음과 같으며, 이는 균일 무작위 순열을 생성한다.

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

Lemma 5.4. PERMUTE-BY-SORTING은 키가 모두 다르다는 전제 하에 균일 무작위 순열을 생성한다.

이 알고리즘은 O(n lg n)이다. 무작위 순열에는 이것보다 더 좋은 O(n)의 시간복잡도를 갖는 방법이 있다.

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

Lemma 5.5. RANDOMIZE-IN-PLACE는 균일 무작위 순열을 생성한다.

5.4. Probabilistic analysis and further uses of indicator random variables

5.4.1. The birthday paradox

생일 패러독스는 다음과 같다. 한 방의 사람들 중에 생일이 같은 두 명의 사람이 있을 확률이 50%가 넘기 위해 필요한 인원은 몇 명인가? 이 확률은 방 안의 사람들의 생일이 모두 다를 확률을 1에서 빼면 된다. 계산해 보면 23명이 있으면 생일이 같은 두 명의 사람이 있을 확률이 50%가 넘게 된다.

An analysis using indicator random variables

지시확률변수 X_{ij}를 사람 i와 사람 j가 생일이 같은 사건이라고 하자. 이 사건이 발생할 확률은 1/n (=1/365)이다. 한 방의 사람들 중에 생일이 같은 두 명의 사람이 생기는 사건은 X = \sum_{i=1}^{k-1} \sum_{j=i+1}^{k} X_{ij} 이므로 E[X] =  \sum_{i=1}^{k-1} \sum_{j=i+1}^{k} E[X_{ij}] = \binom{k}{2} \frac{1}{n} = \frac{k(k-1)}{2n}이다. 계산해 보면 28명이 있으면 생일이 같은 두 명의 사람이 있을 거라는 기대를 할 수 있다.

5.4.2. Balls and bins

동일한 n개의 공들을 b개의 바구니에 던져 넣는 문제를 생각하자. 던진 공이 각각의 바구니에 들어갈 확률은 같다고 가정하자.

평균적으로각각의 바구니에 몇 개의 공이 들어가는가? n / b개.

한 바구니에 공이 들어가기 전까지 평균적으로 공을 몇 개 던져야 하는가? 1 / b개.

모든 바구니에 공이 하나 이상 들어가기 전까지 평균적으로 공을 몇 개 던져야 하는가? 바구니 i – 1개가 공이 들어 있을 때 빈 바구니는 b – i + 1개이므로 빈 바구니에 공이 들어갈 확률은 (b – i + 1) / b이다. 따라서,

E[n] = \sum_{i=1}^{b} \frac{b}{b-i+1} = b (\ln b + O(1)) 이 된다.

이를 쿠폰 수집가 문제라고도 한다.

5.4.3. Streaks

공정한 동전을 n번 던질 때 앞면이 연속해서 나오는 기대횟수는 얼마인가? 답은 \Theta(\lg n)이다.

먼저 O(\lg n)임을 증명해 보자. 사건 A_{ik}를 i번째부터 i + k – 1번째가 모두 앞면만 나오는 사건이라 하면 이 확률은 1/2^{k}이다. 그러므로 k = 2 \lceil \lg n \rceil 이라 하면 P(A_{i, 2 \lceil \lg n \rceil}) \leq 1/n^{2}이고, n번 던질 때 앞면이 k번 연속해서 나올 확률은

P( \bigcup_{i=1}^{n - 2 \lceil \lg n \rceil + 1} A_{i,   2 \lceil \lg n \rceil} ) \leq \sum_{i=1}^{n - 2 \lceil \lg n \rceil + 1} \frac{1}{n^{2}} <  \sum_{i=1}^{n} \frac{1}{n^{2}} = \frac{1}{n}  가 된다.

L_{j}를 n번 던질 때 앞면이 연속해서 나오는 최대 횟수가 j번인 사건이라 하면 최대 앞면 횟수의 기대값은

E[L] = \sum_{j=0}^{n} j P(L_{j}) = \sum_{j=0}^{2 \lceil \lg n \rceil - 1} j P(L_{j}) +  \sum_{j= 2 \lceil \lg n \rceil  }^{n} j P(L_{j}) <  \sum_{j=0}^{2 \lceil \lg n \rceil - 1}  2 \lceil \lg n \rceil  P(L_{j}) +  \sum_{j= 2 \lceil \lg n \rceil  }^{n} n P(L_{j}) < 2  \lceil \lg n \rceil  \cdot 1 + n \cdot (1 / n) = O(\lg n)

이 된다. 이제 \Omega(\lg n)임을 증명해 보자. n번의 시행을 \lfloor \frac{n}{\lfloor (\lg n)/2 \rfloor} \rfloor 그룹의 \lfloor  (\lg n)/2  \rfloor 시행으로 쪼개자. 이 때 P(A_{i, \lfloor (\lg n) / 2 \rfloor}) = 1/2^{ \lfloor (\lg n) / 2 \rfloor } \geq 1 / \sqrt{n} 이므로, 그룹 중에 전부 앞면이 나오는 그룹이 하나도 없을 확률은 최대

(1 - 1/\sqrt{n})^{ \frac{n}{\lfloor (\lg n)/2 \rfloor} } \geq  (1 - 1/\sqrt{n})^{ \frac{2 n}{\lg n} - 1}  \leq e^{-(  \frac{2 n}{\lg n} - 1 )/\sqrt{n}} = O(e^{-\lg n}) = O(1/n)

이 된다. 그러므로 앞면이 연속해서 나오는 최대 횟수가 \lfloor (\lg n) / 2 \rfloor 이상일 확률은 \sum_{j= \lfloor (\lg n) / 2 \rfloor }^{n} P(L_{j}) \geq 1 - O(1/n) 이다. 그러므로

E[L] = \sum_{j=0}^{n} j P(L_{j}) = \sum_{j=0}^{ \lfloor (\lg n) / 2 \rfloor  - 1} j P(L_{j}) +  \sum_{j=  \lfloor (\lg n) / 2 \rfloor  }^{n} j P(L_{j}) \geq  \sum_{j=0}^{ \lfloor (\lg n) / 2 \rfloor  - 1 }  0 \cdot  P(L_{j}) +  \sum_{j=  \lfloor (\lg n) / 2 \rfloor   }^{n}  \lfloor (\lg n) / 2 \rfloor  P(L_{j}) \geq 0 +  \lfloor (\lg n) / 2 \rfloor (1 - O(\frac{1}{n})) = \Omega(\lg n) 이 된다.

지시확률변수를 이용해 더 간단히 풀 수도 있다.

5.4.4. The on-line hiring problem

채용 문제를 바꿔서, 지원자 n명을 전부 면접보지 않고 한 명을 뽑으면 그 뒤에는 면접을 보지 않는다고 하자. 이 때 최초의 k명은 탈락시키고, 최초의 k명보다 점수가 더 높은 면접자가 나오면 그 사람을 채용한다고 하자. 이를 쓰면 다음과 같다.

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

이 때 최적의 k는 얼마일까? M(j)를 지원자 1~j 중 최고 점수라 하고, S를 최고의 지원자를 뽑는 데 성공하는 사건, S_{i}를 최고의 지원자를 뽑았는데 그 지원자가 i번째인 사건이라 하자. S_{i}가 발생하려면 최고의 지원자가 i번째여야 하고 (확률 \frac{1}{n} ), k + 1번째부터 i – 1번째의 지원자가 뽑히지 않아야 한다. 즉, 1번째부터 i – 1번째까지의 지원자 중 최고의 지원자는 1번째부터 k번째 사이에 있어야 한다 (확률 \frac{k}{i-1}). 그러므로 P(S_{i}) = \frac{k}{n(i-1)} 이가 되고, P(S) = \sum_{i=k+1}^{n} P(S_{i}) = \frac{k}{n} \sum_{i=k}^{n-1}\frac{1}{i} 이 된다. 이를 근사하면 이 확률을 최대화하는 k = \frac{n}{e} 를 얻는다.

답글 남기기

아래 항목을 채우거나 오른쪽 아이콘 중 하나를 클릭하여 로그 인 하세요:

WordPress.com 로고

WordPress.com의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Google photo

Google의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Twitter 사진

Twitter의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Facebook 사진

Facebook의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

%s에 연결하는 중