$A(n) = Klog(n)$ からエントロピーの式を導く

シャノンは、先のセッションで証明した $A(n) = Klog(n)$ の式から、エントロピーの式を導き出します。シャノンの推論を追いかけてみましょう。

n 個の自然数 $n_i$ が与えられた時、$\sum n_i = N$ とすれば、$p_i = n_i / N$ として、ある確率分布を得ることができます。この確率分布のエントロピーは、$H( p_1, p_2, \dots ,  p_n)$ で表すことができます。

まず、このn個の可能性から i番目を選んで（その確率は、$p_i $）で、続いて、等確率 $1/n_i $の選択を行うことにしましょう。これがルールです。

このルールのもとでは、ある二つの連続した選択が行われる確率は、$p_i \times 1/n_i = n_i/N \times n_i =1/N $になります。どの i を選んでも、その後に等確率 $1/n_i$ の選択が続くのなら、二つの選択が連続してなされる確率は、等しく、$1/N$ になります。

このルールのもとでは、二番目の等確率 $1/n_i $の選択には、$n_i $ 個の可能性があります。ですから、二つの選択が連続してなされる場合の数は、$n_1 + n_2 + ... + n_n = \sum n_i = N$ となります。

このことは、N個の可能性から等確率の$1/N$を選ぶ選択は、n個から確率$p_i $で一つを選ぶ選択と、$n_i$ 個から等確率の$1/n_i $を選ぶ選択に分解できることを示しています。

「条件 (3)」を使えば、このことは、次の式が成り立つことを意味します。
$$A(N) = H( p_1, p_2, \dots ,  p_n) + p_1 A(n_1) + p_2 A(n_2) + \dots + p_n A(n_n)$$

ここで、前回のセッションで証明した $A(n) = Klog(n) $を使うと、次の式が得られます。
$$Klog(N) = H( p_1, p_2, \dots,  p_n) + p_1 Klog(n_1) + p_2 Klog(n_2) + \dots + p_n Klog(n_n)$$

これから、

$H( p_1, p_2, \dots ,  p_n)= Klog(N) - (p_1 Klog(n_1) + p_2 Klog(n_2) + \dots + p_n Klog(n_n))$
$　= (p_1 +  p_2 + \dots +  p_n) Klog(N)-(p_1 Klog(n_1) + p_2 Klog(n_2) + \dots +  p_n Klog(n_n))$
$　= (p_1 Klog(N) + p_2 Klog(N) +  \dots + p_n Klog(N) -  (p_1 Klog(n_1) + p_2 Klog(n_2) + \dots + p_n Klog(n_n))$
$　= p_1 K log(N/n_1) + p_2 K log(N/n_2) + \dots + p_n Klog(N/n_n)$
$　= K(p_1 log(1/p_1) + p_2 log(1/p_2) + \dots + p_n log(1/p_n))$
$$H( p_1, p_2, \dots ,  p_n) = -K \sum p_i log (p_i) $$