최적화로 얻어진 거듭제곱 분포

마이클 미첸마허 교수의 2004년 논문을 읽었습니다. <인터넷 수학>이라는 저널에 실린 이 논문의 제목을 한글로 옮기면 "거듭제곱 분포와 로그정규분포를 만드는 모형에 관한 간단한 역사"입니다. (pdf 내려받기) 제 블로그에서도 종종 얘기했듯이 거듭제곱 분포를 만들어내는 다양한 모형, 즉 다양한 메커니즘이 있지요. 뉴만의 논문에서 본 율 과정(Yule process)이 대표적인데 두 마디로 '빈익빈 부익부'라고 할 수 있습니다.

오늘 이 글에서는 최적화의 결과로서 얻어딘 거듭제곱 분포를 소개합니다. 원래 만델브로트가 제시한 거라고 하네요. n개의 낱말로 이루어진 언어를 생각합시다. j번째로 자주 쓰이는 낱말을 이용하는데 드는 비용을 C_j라고 합시다. 어떤 낱말을 한 번 이용할 때마다 전달되는 정보량을 최대화한다고 해봅시다. 여기서 정보량은 엔트로피로 정의됩니다. j번째 낱말이 쓰일 확률을 p_j라고 하면, 낱말 당 평균 정보량과 비용은 다음처럼 주어집니다.

\(H=-\sum p_j \log p_j,\ C=\sum p_jC_j\)

H/C를 최대화하는 건 C/H를 최소화하는 것과 같습니다.

\(\frac{d(C/H)}{dp_j}=\frac{C_jH+C\log(ep_j)}{H^2}=0\)

로부터,

\(p_j=e^{-HC_j/C-1}\)

여기서는 C_j를 log j에 비례하는 양으로 가정(?)하는데 왜 그런지 모르겠네요. 여튼 비례상수를 a라고 하고 이 가정을 위 결과에 집어넣으면,

\(p_j=e^{-Ha\log j/C-1}\propto j^{-aH/C}\)

처럼 p_j가 j의 거듭제곱 꼴이 됩니다. 이건 순위(j)에 따른 확률인데, 이로부터 이 확률의 분포도 구할 수 있습니다. 자세한 건"대한민국 100대 최고가 아파트의 거듭제곱 지수" 라는 글에 좀 성의 없게 달아놓은 주석을 참고하세요;;;

만델브로트의