[COSE214] Hiring problem

hiring problem은 computational problem은 아니지만 randomized algorithms의 아이디어를 이용하는 문제이다. 회사에서 n명의 candidate를 인터뷰하여 hire할지, fire할지를 정한다고 하자. 이 때 모든 candidate는 모두 distinct competitiveness를 가지고 있고, 우리는 회사가 hire 시 지불해야하는 총 비용을 계산하고자 한다. 

인터뷰 비용: Ci / hire 비용: Ch / fire 비용: 0

best case: nCi + 1 Ch  : 첫번째 면접자가 가장 competitive 한 경우

worst case: nCi + n Ch : 마지막 면접자가 가장 competitive 한 경우

 

이 때 평균적으로 얼마나 많은 candidate가 hire 될 것인가를 계산하기 위해서는 distribution에 대한 정보가 있어야 한다. 면접 순서의 배열에는 n!개의 경우의 수가 존재하나, 우리는 이 possibilities가 항상 equally likely 한지 모르고, 또한 candidates의 이름이나 competitiveness에 대한 정보는 주로 in advance하게 제공되지 않는다. 따라서 n!개의 배열에 대한 possibilities가 equal하고 list of candidates도 주어졌다고 가정했을 때 우리는 

randomisation을 통해 distribution을 impose 하여 고용될 사람의 expectation을 compute 할 수 있다.

 

Probabilities를 expectation으로 전환하기 위해서 indicator random variable I(A)를 이용하면 분석이 더 빨라진다. A가 발생하면 1을 부여하고, 발생하지 않으면 0을 부여하는 것이다. 

 

이를 이용해서 고용되는 사람의 평균 수를 E(X)라고 할 때 다음과 같이 식을 쓸 수 있다. (단, 이 때 가정은 ① n candidate가 distinct competitiveness를 가짐 ② n!는 equally likely: 모든 배열의 확률이 동일하다는 것이다.)

 

** 집합 S에 대해 uniform probability distribution을 가져 picking an element of S at random하다는 것은, 

Pr{s} = 1/S 하다는 것이다.**