8. 쿠폰 수집가 문제와 근사하게 조화수 근사하기

근래 다시 출시하여 뭇 어린이와 어른이를 미치게 했던 포켓몬 빵을 기억하는가?

스티커만 가지고 빵을 버리는 사람, 편의점에서 산 빵을 개당 3000원에 되팔이하는 사람은 양반이었다. 빵 공장에서 일하는 사람이 수백 장의 스티커를 되팔 작정으로 횡령했다 뉴스에도 나왔지.

포켓몬 빵이 처음 나왔을 때도 지금도, 관건은 모든 스티커를 모을 때 필요한 빵의 갯수였다. n종류의 스티커를 모을 때 필요한 빵의 갯수는 몇 개인가?

어라... 어디서 많이 본 문제 아니던기? 그렇다, 26217번 문제에서 한 번 다루었던 쿠폰 수집가 문제이다.

 

해당 포스트에서 한 증명은 사실 엄밀하지 않다. \(\mathbb{E}(i+1)\)을 구하는 방법을 약간 어물쩡하게 넘긴 감이 있다.

여기서 완벽하게 한 번 짚고, 그 다음 원래 하려고 했던 조화수 근사를 하도록 하자.

 

성공할 때까지 성공률 p인 시행을 하면, 한 시행 횟수의 기대값이 얼마가 될까.

한 번 시행을 할 확률은 p일 것이고, 두 번 시행할 확률은 첫 번째 실패하고 두 번째에 성공할 확률 (1-p)p일 것이고...

따라서 n+1번째에 성공할 확률은, q=1-p로 간략히 표기할 때 \(q^np\)일 것이다.

그렇다면 기댓값은? 시행 횟수×확률의 합이기 때문에, \(E=\sum_0^{\infty}(n+1)q^np\)d이 되겠지.

양 변에 q를 곱해 보자. 그러면 \(qE=\sum_0^{\infty}(n+1)q^{n+1}p=\sum_0^{\infty}nq^np\)가 된다.

따라서, \(pE=E-qE=\sum_0^{\infty}q^np=1\).

따라서 기댓값이 확률의 역수인 1/p가 되는 것이다. 이로부터 n장의 쿠폰을 얻으려면 평균적으로 \(nH_n\)개의 빵이 필요함을 도출할 수 있다!

 

그 다음으로, 이제 본편으로 들어가 보자. \(H_n\)을 어떻게 근사할 것인가.

이 증명과정은 Donald E. Knuth의 《The Art of Computer Programming》 vol.1의 111~115페이지에 아주 큰 도움을 받았다.

 

여기서 두 가지 표기법을 정립하고 가자. \([x]\)는 x 이하의 정수 중 가장 큰 정수. 좀 더 쉽게 이해하려면, x의 정수 부분이라고 보면 된다. 또한 \(\{x\}=x-[x]\)로, x의 소수 부분이 된다.

그렇다면, 정수 k에 대해서 \(k<x<k+1\)의 범위 내에서는 다음 두 가지가 성립한다. 우선 \(\{x\}=x-k\)이고, \(\frac{d}{dx}\{x\}=1\).

그렇다면 부분적분을 이용해 다음 식을 얻을 수 있다.

\[\int_k^{k+1}\left(\{x\}-\frac12\right)f'(x)dx=\left[\left(x-k-\frac12\right)f(x)\right]_k^{k+1}-\int_k^{k+1}f(x)dx=\frac{f(k)+f(k+1)}{2}-\int_k^{k+1}f(x)dx\]

이제 이 식의 양변을 \(1\le k<n\)의 범위에서 더해 주고 양 변에 \(f(n)\)을 더해 주면, 다음 식을 얻을 수 있다.

\[\sum_{k=1}^{n}f(k)=\int_1^nf(x)dx+\frac{f(n)+f(1)}{2}+\int_1^nB_1(\{x\})f'(x)dx\]

여기서, \(B_1(x)\)는 1차 베르누이 다항식으로, \(x-\frac12\)를 의미한다.

 

베르누이 다항식이 나왔으니 베르누이 수가 빠질 수 없다. 고차의 베르누이 다항식을 이용하기 위해서는 반드시 필요하다.

베르누이 수란, \(\frac{z}{e^z-1}\)을 테일러 전개하였을 때 얻어지는 n차항의 계수이다. 정확히는, \(B(z)=\frac{z}{e^z-1}=\sum_0^{\infty}\frac{B_n}{n!}x^n\)의 형식으로 표시되는 수들을 뜻한다.

우선, \(\frac{z}{2}+\frac{z}{e^z-1}=\frac{z}{2}\frac{e^z+1}{e^z-1}=\frac{-z}{2}\frac{e^{-z}+1}{e^{-z}-1}\)이 성립하게 된다.

B(z)를 테일러 전개하였을 때 3차항 이상의 홀수차항은 계수가 모조리 0이 된다는 것이다.

곧, \(B_3=B_5=B_7=B_9=\cdots=0\)이라는 것.

또한, 양 변에 \(e^z-1=\sum_1^{\infty}\frac{z^n}{n!}\)을 대입한 다음 동류항끼리 정리하면, 다음 쓸만한 식을 얻게 된다.

\[\sum_{k=0}^n\binom{n}{k}B_k=B_n\]

 

이제 베르누이 다항식으로 돌아와 보자. 갈 길이 멀다!

베르누이 다항식을 그대로 대입한 다음 양 변을 미분해버린다면, 다음과 같은 관계식이 얻어진다.

\[B_m'(x)=\sum_k\binom{m}{k}(m-k)B_kx^{m-k-1}=m\sum_k\binom{m-1}{k}B_kx^{m-1-k}=mB_{m-1}(x)\]

따라서, m이 1 이상일 때, 부분적분을 통해서 똑같이 이 식을 얻어낼 수 있다.

\[\frac{1}{m!}\int_1^nB_m(\{x\})f^{(m)}(x)dx=\frac{B_{m+1}(1)f^{(m)}(n)-B_{m+1}(0)f^{m}(1)}{(m+1)!}-\frac1{(m+1)!}\int_1^nB_{m+1}(\{x\})f^{(m+1)}(x)dx\]

이 식에 반복적분을 적용시켜 보면, \(R_{mn}=\frac{(-1)^{m+1}}{m!}\int_1^nB_m(\{x\})f^{(m)}(x)dx\)라고 나머지항을 두었을 시 다음과 같이 단순화시킬 수 있다.

\[\sum_1^{n-1}f(k)=\int_1^nf(x)dx+\sum_1^m\frac{B_k(f^{(k-1)}(n)-f^{(k-1)}(1))}{k!}+R_{mn}\]

 

이 식을 함수열 \(\left\{\frac{f^{(m)}}{m!}\right\}\)이 uniformly bounded될 때. 곧 \(\forall m\in\mathbb{N}, \left|\frac{f^{(m)}}{m!}\right|<M\)인 양수 M이 존재한다고 가정할 때는 더 단순화시킬 수 있다.

베르누이 수는 \(\lim_n B_n=0\)이 성립하므로, 여기서 m을 무한히 크게 키우게 된다면 나머지 항이 사라지게 될 것이다.

그리고, 조화수열임을 이용하기 위해서 \(f(x)=\frac{1}{x}\)을 대입하게 되면, 우리가 원했던 식이 드디어! 떨어지게 된다.

\[H_n=\frac{1}{n}+\sum_1^{n-1}f(k)=\frac{1}{n}+\int_1^n\frac{1}{x}dx-\sum_1^\infty\frac{(-1)^{k-1}B_k}{k}\left(\frac{1}{n^k}-1\right)\]

이제 n을 무한으로 보내게 되면 \(\lim_n(H_n-\log n)=\sum_1^\infty\frac{(-1)^kB_k}{k}=\gamma\)로, 여분의 항을 오일러-마스케로니 상수를 통해 처리할 수 있게 된다.

마지막으로! 정리된 식은 따라서 다음과 같다.

\[ H_n = \log n+\gamma+\frac{1}{2n}+\sum_{2}^{n}\frac{(-1)^{k-1}B_k}{kn^k}=\log n+\gamma+\frac{1}{2n}-\sum_{k=1}^\infty\frac{B_{2k}}{2kn^{2k}} \]

이를 통해서 조화수를 근사하게 근사할 수 있다.

 

\(f(x)=\frac{1}{x}\)가 아닌 다른 함수를 집어넣으면 당연히 다른 합을 얻을 수 있다. 정확하게는, 적당히 0으로 수렴하는 단조감소함수를.

완전히 같은 논리로 \(f(x)=\log x\)을 대입하게 된다면, 스털링 근사로 잘 알려진 다음 식을 얻을 수 있다.

\[ \log(n!)=n\log\left(\frac{n}{e}\right)+\frac12\log n+\frac12\log(2\pi)-\sum_1^{\infty}\frac{B_{2k}}{2k(2k-1)n^{2k-1}}\]

 

이번 포스트에서는 조화수의 근사한 근사와 쿠폰 수집가 문제를 주로 다루었다.

이것들이 특정한 상황 아래에서 stable matching을 구하는 알고리즘의 수행 시간을 개선하는데 쓰인다고 하는데, 그것들에 대해서는 아직 아는 바가 없다.

그럼에도 알아두어 나쁠 것은 없다. 그렇지 않은가?

조화수열