pokapoka-jigoku

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

pokapoka-jigoku

Gergo Nemesの近似式は、 $x\ge 0$ で $3.74 \cdot 10^{-4}$ 程度の近似誤差を誇る。Wikipediaの記事にもある通り、 $x \ge 8$ なら約 $10^{-8}$ まで小さくなる：

\ln (x-1)! \approx \frac{1}{2} \left( \ln {2\pi} - \ln x \right) + x \left[ \ln \left( x + \frac{1}{12x - \frac{1}{10x}} \right) -1 \right]

この式を元に、スターリングの式の形に頑張って近づけていくと（近似も使いながら）：

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

となる。Nemesの近似式よりは誤差が出て、 $x=0$ で $2.28\cdot 10^{-3}$ になるがそれでも優秀だ。
$x \ge 8$ になれば $3.8 \cdot 10^{-6}$ まで落ちるので、十分使い勝手はよい。

一応言っておくと、スターリングの $x^{-1}$ 項までの近似：

\ln x! \approx x \ln x - x + \frac{1}{2} \ln {2\pi x} + \frac{1}{12x}

も、 $x \ge 8$ で $10^{-6}$ 程度の近似精度がある。ただし、 $x=0$ で発散するのが痛い。

pokapoka-jigoku

※以下のアプローチは「スクラップ」であり、別のところで議論しているのでそちらを参照：

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

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$ があると発散してしまうのがしんどい。

であれば、先程の近似式を使ったときにキレイになるように、エントロピーを再定義したくなる。

pokapoka-jigoku

すなわち、

\ln x! \approx (x+1) \ln (x+1) - (x+1) + \frac{1}{2} \ln \left (\frac{2 \pi}{x+1} \right) + \frac{1}{12(x+1)}

を用いて、計算を進めると

\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+1) \sum \alpha q_i^* \ln \alpha q_i^* - (N-1) \left( \ln(M+1) - 1\right) + R + R_2\\ &= (M+1) S_\alpha(q^*) - (N-1) (\ln(M+1) - 1) + R + R_2 \end{split}

ここで、 $S_\alpha$ はバイアス付きエントロピー：

S_\alpha(p) = - \sum \alpha p \ln \alpha p = \alpha S(p) - \alpha \ln \alpha

であり、

\alpha = \frac{M+N}{M+1}

である。（参考）

第２項以降の処理がまだだが、バイアス付きエントロピーの導入、経験分布の調整で従来と類似した形式に持ち込めることが分かった。ただし、第２項の出現は注記に値する。

pokapoka-jigoku

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

\begin{split} R &= \frac{N-1}{2} \ln \left( \frac{M+1}{2 \pi} \right) + \frac{1}{2} \sum_i^N \ln \alpha q_i^* \\ &= \frac{N-1}{2} \ln \left( \frac{M+1}{2 \pi} \right) - \frac{N}{2\alpha} S_\alpha(U, q^*) \end{split}

となる。ここで、 $S_\alpha(U, \cdot)$ は一様分布に対するバイアス付きクロスエントロピーで、

S_\alpha(p, q) = - \sum \alpha p \ln \alpha q = \alpha S(p, q) - \alpha \ln \alpha

。結局、

-(N-1)(\ln(M+1)-1) + R = - \frac{N-1}{2} \left[ \ln \left( \frac{2\pi (M+1)}{e^2} \right) + \frac{N}{(N-1)\alpha} S_\alpha(U, q^*) \right]

となる。

pokapoka-jigoku

まとめると：

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

pokapoka-jigoku

さて、 $R_2$ については、 $R_2=0$ としてしまっても近似精度はそこまで悪くない：

緑が $\ln x!$ 、赤が $R_2 = 0$ 、紫が $R_2$ を入れたものになる。 $R_2$ を入れたほうが $x=0$ 付近の精度がすこぶるいいことに間違いはないが、 $R_2=0$ の場合でも、誤差は -0.081 になる。exponential に直すと0.9222 倍程度で……これをどう捉えるかは問題設定によるだろう。

ちなみに、誤差の具合でいうと、 $R_2$ 項の導入の有無についてはスターリング近似とさほど変わらない。重要なことは、今回の近似式では、その $R_2$ の有無に拘わらず、 $x=0$ 付近で発散しないことだ。誤差が出たとしても評価はできる。スターリング近似では評価すらできなかった。

とはいえ、 $R_2$ を評価することは間違いなく悪いことではないので、計算しておく。

R_2 = \frac{1}{12(M+1)} \left( 1 - \sum_i^N \frac{1}{\alpha q^*} \right)

となる。ここで、 $q^*$ が関わる項の範囲は：

N \exp\left( \frac{1}{\alpha} S_\alpha(U, q^*) \right) \le \sum_i^N \frac{1}{\alpha q^*} \le 1+(N-1)(M+1)

となる。下限は相加相乗平均の不等式から求めた。上限は $\{k_i\}$ が一極集中（1点で $M$ , 他が $0$ ）のときに最大であることから求めた（証明割愛）。よって、

- \frac{N-1}{12} \le R_2 \le \frac{1-N \exp\left( \frac{1}{\alpha} S_\alpha(U, q^*) \right)}{12(M+1)}

pokapoka-jigoku

※余談だが、 $R_2$ の下限が抑えられるということが、Nemes由来の近似式の偉大なところである。

Hidden comment

pokapoka-jigoku

一様分布に対するバイアスつきエントロピーの範囲

S_\alpha(U, q^*) = \alpha S(U, q^*) - \alpha \ln \alpha

S(U, q^*) = - \sum \frac{1}{N} \ln q_i^* = D_{KL}(U||q^*) + \ln N

について。下限については、 $D_{KL} \ge 0$ であるから、明らかに、 $S(U, q^*) \ge \ln N$ である。

上限については、一極集中のときであるから、

\begin{split} S(U, q^*) &= \frac{1}{N} \sum \ln \frac{M + N}{k_i + 1} \\ &= \frac{1}{N} \left( \ln \frac{M+N}{M+1} + (N-1) \ln (M+N) \right)\\ &= \ln (M+N) - \frac{1}{N} \ln (M+1) \end{split}

よって、範囲として：

\ln N \le S(U, q^*) \le \ln (M+N) - \frac{1}{N} \ln (M+1)

pokapoka-jigoku

（色々と遊びたいが、まずはやりきろう）よって、バイアス付きエントロピーでは：

\alpha \ln \frac{N}{\alpha} \le S_\alpha(U, q^*) \le \alpha \ln \left [ \frac{M+N}{\alpha (M+1)^{1/N}} \right]

\alpha \ln \frac{N(M+1)}{M+N} \le S_\alpha(U, q^*) \le \alpha \left(1-\frac{1}{N} \right) \ln (M+1)

特に、

-\alpha \ln \left( 1 + \frac{M}{N} \right) \le S_\alpha(U, q^*) - \alpha \ln (1+M) \le - \frac{\alpha}{N} \ln (1+M)

となる。ここで、 $\alpha = \frac{M+N}{M+1}$ を用いた。

pokapoka-jigoku

$N \gg M$ のとき、

- \frac{M}{N} \le - \ln \left(1 + \frac{M}{N} \right)

であるので（ $N \gg M$ でなくともこの不等式は一般になりたつ；ただ実用的でないだけだ）：

-\alpha \frac{M}{N} \le S_\alpha(U, q^*) - \alpha \ln (M+1) \le - \alpha\frac{\ln (M+1)}{N}

$\alpha$ を展開して：

-\left(1 + \frac{M}{N} \right) \frac{M}{M+1} \le S_\alpha(U, q^*) - \alpha \ln (M+1) \le - \left(1 + \frac{M}{N} \right) \frac{\ln (M+1)}{M+1}

結局：

-\left(1 + \frac{M}{N} \right) \le S_\alpha(U, q^*) - \alpha \ln (M+1)\le - \frac{\ln (M+1)}{M+1} \le 0

となる。任意の経験分布について成り立つのは特筆すべきだ。

ざっくり見ると、 $N \gg M$ のとき、

-1 \le S_\alpha(U, q^*) - \alpha \ln (M+1) \le 0

だということになる。

pokapoka-jigoku

$\ln W$ の範囲

というわけで：

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

の下限は：

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

Hidden comment

pokapoka-jigoku

上で述べた $\ln W$ の下限を $L$ とおくと、上限は：

\ln W - L \le \frac{N-1}{2} \ln (M+1) + \frac{N}{2} \ln \left( \frac{\alpha}{N} \right)

となる。

pokapoka-jigoku

そう考えると、オーダーは、

\ln W = (M+1) S_\alpha (q^*) + O\left( \frac{N \ln (M+N)}{M} \right)

Hidden comment

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

一様分布に対するバイアスつきエントロピーの範囲

\ln Wの範囲

$\ln W$ の範囲