Asymptotic equipartition property を説明するコードサンプル

大雑把な解説

「確率 p で表の出るコインを n 回投げる」という実験には $2^n$ 通りの結果がありますが、それぞれの結果 $x^n$ の発生確率 $p(x^n)$ を計算すると、n が大きい場合、その確率はある特定の値 $p_0$ のまわりに集中します。一方、この実験を多数回繰り返して、実際に得られたそれぞれの結果に対して発生確率 $p(x^n)$ を計算すると、これもまた、ある特定の値 $p_1$ のまわりに集中します。

ただし、 $p_0$ と $p_1$ は一致しません。一般に $p_0 < p_1$ という関係が成り立ちます。

なぜなら、確率 $p_0$ 付近の事象は、その数は非常に多い代わりに、それらが発生する確率 $p_0$ はあまり大きくないため、実際のサンプルとして得られる数は少なくなるからです。サンプルとして得られる結果が多数集まる確率 $p_1$ は、 $p_0$ よりも大きい値にずれるのです。

このズレを実際に乱数でサンプリングして示すと次の結果が得られます。

横軸は確率の対数 $\log_2 p(x^n)$ で、縦軸は（正規化した）累積度数です。 $n=1000$ の場合、 $\log_2 p(x^n)=-900$ のあたりで赤色のグラフが急速に立ち上がっており、ほとんどのサンプルがこのあたりに集中していることを示します。一方、青色のグラフは、 $2^n$ 通りの結果が均等に発生したと仮定した場合のグラフです。こちらは、 $\log_2 p(x^n)=-1100$ あたりで急速に立ち上がっており、潜在的に発生し得る事象の大部分は、このあたりに集中しています。

特に注目すべき点は、 $n=1000$ の場合、赤色のグラフが立ち上がる $\log_2 p(x^n)=-900$ の部分において、青色のグラフはほぼ完全に立ち上がりきっており、その値はほとんど変化しなくなっていることです。これは、「潜在的に発生し得る事象の大部分は、現実には観測されることがない」という事を示しています。言い換えると、現実に観測される事象は、潜在的に発生し得る事象のごく一部にすぎないのです。

この事実は、データの圧縮処理に活用できます。個々の事象は、全部で $2^n$ 通りあり、生のデータとしては n bit の値として表現されていますが、「現実に観測されるごく一部のデータ」だけを集めて通し番号を振れば、ずっと小さな bit 数でラベリングできてしまいます。可逆性が求められない場合であれば、「現実に観測されるごく一部のデータ」以外の大部分のデータには、同じラベルを振ってしまえば高い圧縮率が実現されます。この圧縮方法は、厳密には可逆性が無いとは言え、同じラベルで潰れてしまうデータは、「現実に観測されるデータ」にはほとんど含まれないので、実用的には可逆性を保つものと考えることができます。

もうちょっと厳密な記述

「現実に観測されるデータ」が集中する部分の確率 $p(x^n)$ は、 $2^{-nH(X)}$ に一致します。ここに、 $H(X)$ は、1回の試行 $x$ に対する確率が持つエントロピーで、今の場合は $0\le H(X)\le 1$ を満たします。先のグラフの破線は、 $-n\left\{H(X)\pm 0.1\right\}$ の範囲を示しています。