Approximate Counting: Morris Counter

이 포스팅을 시작으로, 몇 번에 걸쳐 Approximate Counting 및 몇가지 관련된 알고리즘들을 공부해 보려고 합니다.

문제

문제 자체는 정말 간단합니다.

이 문제는 당연히 카운터 변수 하나를 관리함으로써 자명하게 해결할 수 있고, 이때 $n$ 까지의 수를 헤아리기 위해서는 $O(\log n)$ 비트가 필요합니다.

오늘 다루고자 하는 문제는 여기서 나아가서, 정확한 횟수 대신 근삿값을 출력하도록 허용함으로써, 위 문제를 더 작은 공간만으로 해결할 수 있는가? 입니다.

---

Approximate Counting: Morris Counter

알고리즘이 단순하기 때문에, 바로 먼저 알고리즘을 서술하고, 분석을 진행하겠습니다. 이 알고리즘은 Robert Morris가 1978년에 [1] 제안하여, 보통 Morris Counter 라는 이름으로 불립니다.

2번 쿼리의 답을 $2^X - 1$ 로 제출하겠다는 것은, $X$를 $\log_2(n + 1)$ 의 근사값으로 사용하겠다는 의미입니다. $n$을 저장하는 대신 $O(\log n)$ 크기의 변수를 하나 저장하고 있기 때문에, 필요한 공간의 기댓값은 $O(\log \log n)$ 가 됩니다.

업데이트가 확률적인 과정에 따라 이루어지기 때문에, $n$번의 업데이트가 이루어진 시점의 $X$의 값을 확률변수 $X_n$ 으로 쓸 수 있습니다. 이제, 이 알고리즘을 분석하기 위해서는, randomized algorithm을 분석하는 일반적인 방법에 따라 다음 두 가지를 보여야 합니다.

• Unbiased: 기댓값 $\E[X_n]$의 값이 정말 $\log_2(n + 1)$ 가 맞는가?
• Accuracy: 그떄의 분산, 또는 적절한 Concentration bound를 줄 수 있는가?

---

Analysis: Unbiasedness

첫번째 명제 - Unbiased - 를 보이기 위해서는, $\E[2^{X_n}] = n + 1$ 을 확인하면 충분합니다. 수학적 귀납법에 따라 증명합니다. $n = 0$ 일 때는 $X_0$의 값이 0이므로 성립합니다.

$\E[2^{X_n}] = n + 1$ 이라고 할 때, $\E[2^{X_{n + 1}}]$ 을 분석하면, 기댓값의 정의에 의해

\[\E[2^{X_{n + 1}}] = \sum_{k = 0}^{\infty} 2^{k} \cdot \P[X_{n + 1} = k]\]

이고, 이때 $\P[X_{n + 1} = k]$ 는 $X_n$의 값에 따라 확률적으로 다음과 같이 계산됩니다.

\[\P[X_{n + 1} = k] = \P[X_{n} = k-1] \cdot \frac{1}{2^{k-1}} + \P[X_{n} = k] \cdot \left(1 - \frac{1}{2^k}\right)\]

앞 항은 $X_n$ 이 $k-1$이었는데 1번에서 확률 $1 / 2^{k-1}$ 에 의해 업데이트에 성공한 경우를, 뒤 항은 $X_n$이 원래 $k$였고 업데이트가 실패한 경우를 의미합니다. 이제, 이 값을 대입하고 적절히 정리하여,

\[\begin{align*} \E[2^{X_{n + 1}}] &= \sum_{k = 0}^{\infty} 2^{k} \left(\P[X_{n} = k-1] \cdot \frac{1}{2^{k-1}} + \P[X_{n} = k] \cdot \left(1 - \frac{1}{2^k}\right)\right)\\ &= \sum_{k = 0}^{\infty} 2 \cdot \P[X_{n} = k-1] + 2^k \cdot \P[X_{n} = k] - \P[X_{n} = k]\\ &= \E[2^{X_{n}}] + 1 \end{align*}\]

이와 같이, $\E[2^{X_{n + 1}}] = \E[2^{X_n}] + 1$ 이므로, $\E[2^{X_n}] = n + 1$ 이 성립합니다.

---

Analysis: Concentration Bound

Variance를 보이는 것은 위와 거의 비슷한 (조금 더 귀찮은) 계산으로 충분합니다.

Variance가 $\E[X]^2$ 와 같은 order로 잡힌다면, Chebyshev’s inequality를 이용하여 적절한 tail bound도 줄 수 있습니다.

상수 -1은 분산에 영향을 주지 않으므로, 위 분산을 계산하기 위해서는, $\E[(2^{X_n})^2]$ 을 계산하는 것으로 충분합니다. 위 계산과 같은 방법으로,

\[\begin{align*} \E[2^{2X_{n + 1}}] &= \sum_{k = 0}^{\infty} 2^{2k} \cdot \P[X_{n + 1} = k]\\ &= 2^{2k} \left(\P[X_{n} = k-1] \cdot \frac{1}{2^{k-1}} + \P[X_{n} = k] \cdot \left(1 - \frac{1}{2^k}\right)\right)\\ &= \sum_{k = 0}^{\infty} 4 \cdot 2^{k - 1} \P[X_{n} = k-1] + 2^{2k} \cdot \P[X_{n} = k] - 2^k \P[X_{n} = k] \\ &= 4 \E[2^{X_n}] + \E[2^{2X_{n}}] - \E[2^{X_n}]\\ &= \E[2^{2X_{n}}] + 3(n + 1) \end{align*}\]

$\E[2^{2X_{0}}] = 1$ 이므로, $\E[2^{2X_{n}}] = 3n(n + 1) / 2 + 1$ 가 됩니다. 따라서,

\[\Var[2^{X_n} - 1] = \frac{3n(n + 1)}{2} + 1 - (n + 1)^2 = \frac{(n^2 - n)}{2} \leq n^2 / 2\]

임을 알 수 있습니다.

이제, Chebyshev’s inequality로부터,

\[\P[|2^{X_n} - 1 - n| > \epsilon] < \frac{\Var[2^{X_n}]}{\epsilon^2} \leq \frac{n^2}{2\epsilon^2}\]

이므로, $\epsilon = k \sqrt{n}$ 을 취하면, 오차가 $k \sqrt{n}$ 이상 발생할 확률은 $1 / 2k^2$ 이하임을 확인할 수 있습니다.

---

Extensions: Mean / Median trick

이 문단의 내용들은 다양한 확률적 알고리즘들에 동일하게 적용이 가능하므로, [별도 포스팅(작성중)]에서 더 자세히 다루고 있습니다.

Morris counter는 가장 간단한 형태의 approximate counting 알고리즘들이기 때문에, 관련하여 다양한 확장들이 있습니다.

우리는 보통 확률적 알고리즘들을 분석할 때에, 작은 상수 $\epsilon, \delta$를 설정해 두고, $\P[\text{error} > \epsilon] < \delta$ 로 만들기 위한 최소한의 실행횟수 (시간) / 메모리에 관심을 갖습니다.

• 단순히 여러 개를 parallel하게 작동시켜 그 평균을 사용하는 경우, $1 / (\epsilon^2 \delta)$ 개의 estimator들을 사용함으로써, $O\left(\frac{\log\log{n}}{\epsilon^2\delta}\right)$ 공간 복잡도로 위 bound에 부합하는 알고리즘을 얻습니다.
• 별도 포스팅에서 다룰 Median Trick을 이용하여 알고리즘을 개선할 수 있고, 그 경우 $O\left(\frac{\log\log{n}}{\epsilon^2} \cdot \log (1 / \delta)\right)$ 공간 복잡도로 위 bound에 부합하는 알고리즘을 얻습니다.

---

Extensions: Parametrized Version

위 알고리즘의 내용에서, $2^{X_n}$ 을 사용하는 대신, 임의의 수 $(1 + a)$ ($a > 0$) 로도 비슷하게 생각할 수 있습니다.

이경우 $((1 + a)^{X_n} - 1) / a$ 를 estimation으로 사용하고, 업데이트도 $X_n = k$ 일 때는 $1 / (1 + a)^{k}$ 확률로 1을 더해 주는 식으로 해주면 됩니다. 분석도 거의 똑같이 할 수 있어서, 위 계산에서 필요한 부분을 (조금씩 더 귀찮아지지만) 바꾸어 계산해보면 expectation은 똑같이 성립하며 variance는 $\frac{an(n - 1)}{2} \leq an^2 / 2$ 가 됨을 알 수 있습니다. 따라서, $a = 1 / (\epsilon^2 \delta)$ 를 잡아주면, variance가 바로 $\frac{n^2}{2\epsilon^2 \delta}$ 로 줄어들기 때문에 Chebyshev 부등식만 적용해도 바로 $(\epsilon, \delta)$ - estimation이 성립하게 됩니다.

이렇게 얻어지는 estimator는 위에 논의한, randomized algorithm들 대개에 적용되는 일반적인 방법보다 훨씬 더 효과적입니다. 우리가 사용하는 expected space는 $\log X_n$ bit이며, 위 세팅에서 이는 대략 (asymptotic하게 계산하고 있으므로, $X_n \approx \log_{1 + a}(an)$ 으로 생각하여)

\[\begin{align*} \log X_n \approx \log_2 \log_{1 + a} (an) &= \log \log (an) - \log \log (1 + a) \\ & = \log \log (an) + \log 1 / (\log (1 + a))\\ &\leq \log \log (an) + \log (1 / a) \end{align*}\]

이와 같이 유도됩니다 (마지막 부등식에서는 $\log (1 + a) \leq a$ 임을 사용하였습니다). 따라서, Space complexity는

\[\log \log (n / \epsilon^2 \delta) + \log (1 / \epsilon^2\delta) = O(\log \log n + \log (1 / \epsilon) + \log(1 / \delta))\]

임을 얻게 됩니다.

---