Probabilistic Analysis

 

---

Probabilistic Analysis

---

 

 

 

0. 개요

 

기존에는 알고리즘의 시간분석도를 계산할 때 알고리즘에서 실행되는 명령어의 수를 계산하는 방식으로 진행했다. 특히 worst case로 진행해 그러나 많은 알고리즘은 주어지는 입력에 따라 성능이 달라지는 경우가 많다. 이렇게 입력이 확률적으로 주어지는 상황에서, 입력에 대한 worst case로 성능을 보는 것이 아닌, 평균적인 성능으로 알고리즘의 성능을 분석하는 방법을 알고리즘의 확률적 분석이라고 한다.

 

다만 확률적 분석은 입력의 분포를 알고 있다는 가정 하에 진행된다. 입력의 분포를 모른다면 확률적 분포를 진행할 수 없다.

 

 

1. Hiring Problem

 

Hiring Problem은 사람을 채용할 때의 문제를 칭한다. 각각 사람을 면접볼 때 비용이 들고, 현재 면접자가 지금까지의 면접자들 중 제일 우수하다면 지금 고용된 사람을 해고하고, 현재 면접자를 채용한다고 한다. 

각각의 비용은 다음과 같이 설정하자:

• 면접비용: C_i
• 채용비용: C_h
• 해고비용: 0

 

지원자 수를 n, 채용자 수를 m이라고 했을 때 시간복잡도는 다음과 같다. 이때, n*C_i 는 상수이므로 무시한다.  

 

O( n*C_i + m*C_h)

 

따라서 Hiring Problem은 주어진 수열에서 최댓값이나 최솟값을 찾는 문제이다. 따라서 

기존에 해왔던 방식으로 worst case 및 best case를 따진다면 다음과 같다.

• Worst Case: 매 인터뷰마다 hire 해서 O( n*C_h)
• Best Case: 첫 번째 지원자가 가장 능력이 좋아서 고용은 한 번 진행, O( 1*C_h)

 

이렇듯 n의 값의 차이가 크다는 것을 확인할 수 있다. 따라서 이러한 경우에는 worst case보다는 평균 시간을 채택하는 것이 합리적일 수 있다. 

 

Randomized Algorithms

 

여기서 한 가지 짚고 넘어가야 할 점은, 어떤 문제의 입력 분포를 모델링했다고 해도 입력이 진짜로 그 분포에서 무작위로 오는지는 알 수 없다는 점이다. 따라서 보통의 경우에는 이를 위해 무작위성에 대한 가정을 추가한다. 이는 뒤에서도 다시 언급되겠지만 랜덤화를 통해 알고리즘의 input dependency 또한 낮출 수 있다.

 

Hiring Problem에서는 다음 3가지 가정을 한다.

• There are `n` candidates
• Each has distinct competitiveness
• `n!` is equally likely

참고) Competitiveness in Advance vs. Randomization: 두 번째의 경우 기업이 순서를 정할 수 있는데 대신 랜덤하게 고를 수 있음. 따라서 기댓값을 구할 수 있는거고, 첫 번째의 경우 정해진게 없이 passive하게 받기 때문에 기댓값은 논할 수 없음. Randomization에 대한 개념을 잡기 위해 가볍게 보면 될 듯.

 

 

Indicator Random Variables

 

앞서도 언급했듯이, Probabilistic Analysis는 입력의 분포를 랜덤 과정에서 가져오기 때문에, 하나의 변수를 랜덤으로 지정해야 한다. 이를 Indicator Random Variable이라고 한다. 

내용은 단순하다. 하나의 Indicator Random Variable I_A가 있을 때, 이의 경우는 다음과 같다.

 

I_A={1 if A occurs, 0 if not occurs}

 

이렇게 하는 이유는 Exp(I_A)=Prob(A)로 계산하기 위해서다. Lemma로 소개되는 부분인데, 본 글에서는 증명은 생략한다ㅎ 

 

이를 고려했을 때, Hiring Problem에서의 기대 채용비용은 다음과 같이 구할 수 있다.