Online 알고리즘 (5) - Randomized Online Algorithms (MBG 문제)

이번 포스팅에서는 Modified Bit Guessing Problem (이하 MBG 문제) 에 대하여 randomness가 deterministic 알고리즘에 어떤 영향을 끼치는지 알아보도록 하겠습니다. MBG 문제는 다음과 같이 정의할 수 있습니다. 

 

2명의 사람이 게임을 한다고 합시다. 한 사람이 n개의 비트의 나열 패턴을 정합니다. 그리고 다른 한 사람은 그 비트를 하나씩 들으면서 다음에 어떤 비트가 올 지 맞추는 게임입니다. 즉, 다음 비트가 0일지 1일지 과거 비트의 패턴을 보고 맞춰야 합니다. 목표는 하나라도 맞추는 것입니다. 맞춘다면 점수를 $g(n)/(1-1/2^{n-1})$를 얻고 모두 틀린다면 1 만큼 점수를 얻습니다. 

 

우선 직관적으로 이 게임에 대해서 해석해봅시다. 만약 비트의 나열 패턴을 정하는 사람이 맞추는 사람의 정답을 듣고 다음 비트를 정하면 어떻게 될까요? 당연히 아무것도 못맞추도록 할 수 있습니다. 그저 0을 말하면 1을 말하면 되고 1을 말하면 0을 말하면 그만입니다. 이러한 상황은 deterministic 알고리즘에 대해 간단한 알고리즘만으로 adversary가 대응할 수 있다고 할 수 있습니다. 하지만 만약 응답에 상관없이 정해둔 패턴을 말하는 양심적인 사람(?)이라면 어떻게 될까요? 총 ${n-1}$번의 매칭에서 적어도 한번은 맞출 확률이 $1-1/2^{n-1}$이므로 $g(n)/(1-1/2^{n-1}) * (1-1/2^{n-1}) = g(n)$ 의 점수를 얻을 것을 기대할 수 있습니다. 이는 randomized 알고리즘에 대해서 망각형 adversary는 대응할 수 없음을 알 수 있습니다. 그리고 이를 봤을 때, 우리는 randomness가 adversary와의 일종의 게임에서 더 유리해질 수 있음을 직관적으로 알 수 있습니다. 그렇다면 Proportional Knapsack 문제에 대한 분석을 정리해보도록 하겠습니다.

 

$W$만큼 담을 수 있는 배낭이 있고 $w_1,...,w_n$의 무게를 가지고 있는 n개의 보석이 있습니다. 그리고 무게를 하나씩 듣고 그 보석을 배낭에 담을지 안담을지 결정합니다. 즉, $\sum_{i=1}^{n}{z_iw_i} <= W$의 최대값을 만족하는 $z_1,...,z_n, z_i\in\{0,1\}$을 구하면 됩니다. 다만 주의할 것은 절대로 총 무게$W$를 초과하면 안됩니다. 

 

배낭은 가장 큰 것을 챙기도록 합시다

우선 이 문제가 deterministic 알고리즘으로 상수의 competitive ratio를 구할 수 없다는 걸 봐야합니다. 

$$\rho(ALG) \ge \frac{\epsilon}{1-\epsilon}, \epsilon > 0$$

 

우선 adversary의 전략을 생각해봅시다. $W=n$일 경우, 알고리즘이 처음으로 배낭에 챙기는 보석의 무게를 $\epsilon n$이라고 합시다. 만약 알고리즘이 하나도 안챙기면 총 보석은 0입니다. 챙긴다면 $OPT \ge \epsilon n$으로 competitve는 매우 커집니다. 만약 알고리즘이 $w_i=\epsilon n$을 배낭에 챙긴다고 하면, adversary를 $w_{i+1} = n(1-\epsilon) +\epsilon$을 다음 보석으로 제시하고 다음부터는 다 0으로 제시합니다. 그렇다면 $i+1$번째 보석을 챙기면 무게를 초과하게 되므로 $ALG = \epsilon n, OPT=n(1-\epsilon)+\epsilon$이므로 위 competitive ratio를 만족합니다.

 

그럼 randomized 알고리즘을 살펴봅시다. 간단하게 1 bit의 랜덤을 통해 competitive ratio 4의 알고리즘을 설계할 수 있습니다. 이 알고리즘은 2가지 모드의 동작으로 이루어져있습니다. 하나는 greedy하게 새로운 보석이 제시되면 알고리즘은 여유공간이 있는지 확인하고 배낭에 챙깁니다. 두번째 모드는 무게가 $\ge W/2$인 보석을 제시받을 때까지 기다립니다. 만약 그런 보석을 제시받으면 배낭에 챙깁니다. 랜덤을 통해 이 2가지 모드 중 하나를 동작하는 알고리즘입니다. 

 

그럼 다음을 2가지 모드를 나누어 각각 증명을 해보도록 하겠습니다. 

 

$$OPT \le 4E(ALG_{simple})$$

 

첫번째 경우는 모든 보석의 무게가 $w_i \lt W/2$인 경우입니다. $\sum_{i=1}^{n}{z_iw_i} <= W$라고 하면 절반의 확률로 첫번째 모드를 실행하고 알고리즘은 모든 보석을 챙길 것 입니다. 따라서 $E(ALG_{simple})\ge1/2\sum{w_i}$입니다. 결국  $OPT\le2E(ALG_{simple})$ 를만족합니다. 만약 $\sum_{i=1}^{n}{z_iw_i} > W$일 경우에는 첫번째 모드에서 챙기지 못하는 보석들이 있을 수 있습니다. $w_i$를 챙기지 못하는 보석 중 첫번째라고 하고 $w_i \lt W/2$라고 한다면 이 알고리즘은 적어도 $W/2$만큼은 배낭에 챙긴거라고 할 수 있습니다.

결국 $ E(ALG_{simple}) \ge (1/2)(w/2) $이므로 $ OPT \le 4E(ALG_{simple})$를 만족합니다.

 

두번째 경우는 보석의 무게가 $w_i \ge W/2$인 보석이 있는 경우입니다. 2번째 모드는 $w_i \ge W/2$일 때, 보석을 배낭에 챙길 것이고 그러면 $ E(ALG_{simple}) \ge (1/2)(w/2) $이므로 $ OPT \le 4E(ALG_{simple})$를 만족합니다. 이로써 우리는 모든 경우의 competitive ratio가 4임을 알 수 있습니다.

 

이번 포스팅에서는 randomness가 알고리즘에 어떤식으로 영향을 끼치는지 살펴보았습니다. randomness는 deterministic 알고리즘으로 풀 수 없는 어려운 문제에 대해서 좋은 radomized 알고리즘을 만들 수 있게 해줍니다. 하지만 사실 randomness는 실제로 굉장히 비싼 자원입니다. 완벽에 가까운, 패턴이 전혀 없는랜덤한 비트는 간단하게 만들 수 없습니다. 그래서 randomness에 대한 의존성을 없애려고 합니다. 이를 "derandomized"라고 하며, computational 모델에 따라 derandomized가 가능한지 결정할 수 있습니다. 예를 들어, 망각형 adversary를 상대로는 불가능하지만(물론 특정 constraint의 문제에 대해서는 가능할 수 있습니다) 적응형-오프라인 adversary에게는 가능합니다. 이는 어떤 경우가 있는지 아직 모르는 미지의 영역이기 때문에 나중에 알게되면 다루도록 하겠습니다.