自由研究：多項試行の再考

N種の多項試行において、 $M$ 回試行で各出目が $\{k_i\}$ のときの場合の数は：

W = \frac{M!}{k_1! ..... k_N!}

で求まる。 $M$ も各 $k_i$ も十分に大きいとき、スターリングの公式：

\ln x! \approx x \ln x - x + O(\ln x)

により、エントロピー $S(q) = - \sum q_i \ln q_i$ を用いて

\ln W \approx M \cdot S(q)

のように表される。とはいえ、 $M$ が大きいのは頑張れるが、 $k_i$ が大きいのはかなり厳しい条件だ。特に、 $k_i = 0$ があると発散してしまうのがしんどい。

というわけで、上記記事のNemes近似式の変形式を使って再計算しよう、というのが本記事の趣旨。

pokapoka-jigoku

\ln (x-1)! = x \ln x - x + \ln \frac{2\pi}{x} + \frac{1}{12x}

pokapoka-jigoku

\ln W = (M+1) \ln (M+1) - (M+1) - \sum^{N} \left[ (k_i + 1) \ln (k_i +1) - (k_i + 1) \right] + R + R_2

ここで、

\begin{split} R &= \frac{1}{2} \ln \frac{2\pi}{M+1} - \sum_{i=1}^{N} \frac{1}{2} \ln \frac{2\pi}{k_i + 1} \\ R_2 &= \frac{1}{12(M+1)} - \sum_i^N \frac{1}{12(k_i +1)} \end{split}

pokapoka-jigoku

$R$ 以外の項をまとめると、変性経験分布：

q_i^{*} := \frac{k_i + 1}{M + N}

を定義して、次の結果を得る：

\begin{split} \ln W &= (M+N) \left[ - \sum q_i^* \ln q_i^* - (-\beta \ln \beta -(1-\beta)\ln (1-\beta)) \right] - (N-1) \left( \ln(N-1) - 1\right) + R + R_2\\ &= (M+N) \left[ S(q^*) - S_\beta \right] - (N-1) \left( \ln(N-1) - 1 \right) + R + R_2 \\ &= (M+N) \left[ S(q^*) - S_\beta \right] + O(N \ln(N)) \end{split}

ここで、 $S$ はエントロピー：

S(p) = - \sum_i^N p_i \ln p_i

であり、 $S_\beta$ はエントロピーバイアスで、

S_\beta = - \beta \ln \beta -(1-\beta)\ln (1-\beta)

\beta = \frac{M+1}{M+N} < 1

である。見た目の通り、 $\beta$ をパラメータとしたベルヌーイ試行のエントロピーである。

第２項以降の処理がまだだが、変性経験分布、エントロピーバイアスの導入で従来と類似した形式に持ち込めることが分かった。

pokapoka-jigoku

第２項以降をまとめていく。まずは $R$ から。詳細は割愛するが：

\begin{split} R &= \frac{N-1}{2} \ln \left( \frac{M+N}{2 \pi} \right) + \frac{1}{2} \left( \sum_i^N \ln q_i^* - \ln \beta \right) \\ &= \frac{N-1}{2} \ln \left( \frac{M+N}{2 \pi} \right) - \frac{1}{2} \left[ \sum_i^N I(q^*_i) - I(\beta) \right] \end{split}

となる。ここで、 $I(q_i)$ は確率 $q_i$ の情報量：

I(q_i) = - \ln q_i

である（ $I(\beta)$ は情報量バイアスとでも言える）。結局、第２項もあわせると：

\begin{split} -(N-1)(\ln(N-1)-1) + R = &- \frac{N-1}{2} \ln \left( \frac{2\pi (1-\beta)}{e^2} (N-1) \right) - \frac{1}{2} \left[ \sum_i^N I(q^*_i) - I(\beta) \right] \end{split}

となる。

Hidden comment

pokapoka-jigoku

$R_2$ の計算。

R_2 = \frac{1}{12(M+1)} - \sum_i^N \frac{1}{12(k_i +1)} = - \frac{1}{12(M+N)} \left[ \sum_i^N \frac{1}{q^*_i} - \frac{1}{\beta} \right]

pokapoka-jigoku

\sum_i^N I(q^*_i)

の範囲評価。下限は一様分布、上限は局所集中（1点のみ確率1、他は0）のときなので、

N \ln N \le \sum_i^N I(q^*_i) \le \ln \frac{M+N}{M+1} + (N-1) \ln (M+N) \le N \ln (M+N)

特に、上限については、

\sum_i^N I(q^*_i) - I(\beta) \le (N-1) \ln (M+N)

であるので、これで $\ln W$ の下限を捉えられる：

\ln W \ge (M+N) \left[ S(q^*) - S_\beta \right] - \frac{N-1}{2} \ln \left( \frac{2\pi (N-1)^2}{e^2} \right) + R_2

Hidden comment

pokapoka-jigoku

下限については、

\sum_i^N I(q^*_i) - I(\beta) \ge N \ln N - I(\beta) \ge (N-1) \ln N + \ln \beta

であるので、これで $\ln W$ の上限を抑えられる：

\begin{split} \ln W &\le (M+N) \left[ S(q^*) - S_\beta \right] - \frac{N-1}{2} \ln \left( \frac{2\pi (1-\beta)}{e^2} (N-1)N \right) -\frac{1}{2} \ln \beta + R_2 \\ &\le (M+N) \left[ S(q^*) - S_\beta \right] - \frac{N-1}{2} \left[ \ln \left( \frac{2\pi (N-1)^2}{e^2} (1-\beta)\right) + \frac{\ln \beta}{N-1} \right] + R_2 \end{split}

pokapoka-jigoku

\sum_i^N \frac{1}{q^*_i}

の範囲評価。先と同様、下限は一様分布、上限は局所集中（1点のみ確率1、他は0）のときなので、

N^2 \le \sum_i^N \frac{1}{q^*_i} \le \frac{M+N}{M+1} + (N-1)(M+N) \le N (M+N)

特に、上限については、

\sum_i^N \frac{1}{q^*_i} - \frac{1}{\beta} \le (N-1)(M+N)

であるので、これでさらに $\ln W$ の下限を捉えられる：

\begin{split} \ln W &\ge (M+N) \left[ S(q^*) - S_\beta \right] - \frac{N-1}{2} \ln \left( \frac{2\pi (N-1)^2}{e^2} \right) - \frac{N-1}{12}\\ &= (M+N) \left[ S(q^*) - S_\beta \right] - \frac{N-1}{2} \ln \left( \frac{2\pi (N-1)^2}{e^2} + \frac{1}{6} \right) \\ &= (M+N) \left[ S(q^*) - S_\beta \right] - \frac{N-1}{2} \ln \left( \frac{2\pi (N-1)^2}{e^{\frac{11}{6}}} \right) \end{split}

Hidden comment

pokapoka-jigoku

下限については、

\sum_i^N \frac{1}{q^*_i} - \frac{1}{\beta} \ge N^2 - \frac{1}{\beta} \ge (N-1)^2- \frac{1}{\beta}

より、 $\ln W$ の上限が抑えられて

\ln W \le ..... -\frac{N-1}{12}\left((1-\beta) - \frac{1}{(N-1)(M+1)}\right)

pokapoka-jigoku

\begin{split} \ln W \le (M+N) \left[ S(q^*) - S_\beta \right] - \frac{N-1}{2} \left[ \ln \left( \frac{2\pi (1-\beta)}{e^2} (N-1)^2 \right) + \frac{\ln \beta}{N-1} + \frac{1}{6}\left((1-\beta) - \frac{1}{(N-1)(M+1)}\right) \right] \\ & \end{split}

Hidden comment

pokapoka-jigoku

$\ln W$ の下限値：

\mathrm{inf} \ln W = (M+N) \left[ S(q^*) - S_\beta \right] - \frac{N-1}{2} \ln \left( \frac{2\pi (N-1)^2}{e^{\frac{11}{6}}} \right)

に対して、上限値は：

\begin{split} \mathrm{sup} \ln W - \mathrm{inf} \ln W &= \frac{N-1}{2} \left[ - \ln (1-\beta) + \frac{\beta}{6} \right] - \frac{1}{2} \ln \beta + \frac{1}{12(M+1)} \\ &\approx \frac{M+N}{2} \left[ - (1-\beta) \ln (1-\beta) + \frac{\beta(1-\beta)}{6} \right] - \frac{1}{2} \ln \beta \\ &= \frac{M+N}{2} \left[ S_\beta + \frac{\beta(1-\beta)}{6} \right] + \frac{M}{2} \ln \beta \\ \end{split}

pokapoka-jigoku

\begin{split} \left[ S_\beta + \frac{\beta(1-\beta)}{6} \right] \le \ln 2 + \frac{1}{24} \approx 0.73481.. \end{split}

pokapoka-jigoku

なので、

\begin{split} \mathrm{sup} \ln W - \mathrm{inf} \ln W &\le \frac{M}{2} \ln \beta + \frac{M+N}{2} \left( \ln 2 + \frac{1}{24} \right) \\ \end{split}

pokapoka-jigoku

というわけで：

\begin{split} \ln W = &(M+N)(S(q^*) - S_\beta) - \frac{N-1}{2} \ln \left( \frac{2 \pi}{e^{\frac{11}{6}}} (N-1)^2 \right) \\ &+ \xi(S(q)) \cdot \left[ \frac{M+N}{2} \left( S_\beta + \frac{\beta(1-\beta)}{6} \right) + \frac{M}{2}\ln \beta + \frac{1}{12(M+1)} \right] \end{split}

ここで、 $\xi(S(q))$ は（非変性の）経験分布に対するエントロピーの単調増加関数であり、

\xi(0) = 0,~ \xi(\ln N) = 1

を満たす。

pokapoka-jigoku

ちなみに、

\begin{split} \xi = &\left[ \frac{N-1}{2} \ln \left( (M+N) e^\frac{1}{6} \right) -\frac{1}{2} \left( \sum I(q^*) - I(\beta) \right) -\frac{1}{12(M+N)} \left( \sum \frac{1}{q^*_i} - \frac{1}{\beta} \right)\right] \\ &\cdot \left[ \frac{M+N}{2} \left( S_\beta + \frac{\beta(1-\beta)}{6} \right) + \frac{M}{2}\ln \beta + \frac{1}{12(M+1)} \right]^{-1} \end{split}

pokapoka-jigoku

さて。

\begin{split} S(q^*) &= - \sum q^*_i \ln q^*_i \\ &= -\frac{M}{M+N} \sum q_i \ln q^*_i - \frac{1}{M+N} \sum \ln q^*_i \\ &= \frac{M}{M+N} (S(q) + D_{KL}(q || q^*)) + \frac{1}{M+N} \sum I(q^*_i) \end{split}

であるので、

\sum_i^N I(q^*_i) = (M+N) S(q^*) - M \cdot (S(q) + D_{KL}(q||q^*))

pokapoka-jigoku

・・・これ、 $S(q)$ で表したほうがよくないか？