シャノンの漸近等分割性（AEP）再考：統計的典型性と情報理論的証明技術への応用
はじめに：情報理論におけるAEPの基礎的役割
クロード・シャノンが1948年の画期的な論文『A Mathematical Theory of Communication』で提唱した情報理論は、情報のエントロピーによる定量化、通信路容量の概念、そして通信における符号化の理論的限界を明らかにしました。これらの理論の多くの核心部分は、漸近等分割性（Asymptotic Equipartition Property, AEP）と呼ばれる極めて重要な性質に基づいています。
AEPは、十分に長い独立同分布（i.i.d.）な確率変数の系列において、そのほとんど全てが「典型的な（typical）」振る舞いをすることを示唆します。これは一見単純なステートメントのように思われますが、確率論における大数の法則や中心極限定理とも関連し、情報理論においてはデータ圧縮や信頼性のある通信の限界を導出するための主要な数学的ツールとなります。特に、AEPによって定義される「典型集合（Typical Set）」の概念は、情報源符号化定理やチャネル符号化定理の証明において、中心的な役割を果たします。
本稿では、シャノンのAEPが導入した統計的典型性の概念を再考し、その数学的な厳密性、統計学との関連、そして情報理論における主要な証明技術への具体的な応用について詳細に掘り下げます。ターゲット読者である情報科学分野の専門家の方々にとって、AEPが単なる定理のステートメントに留まらない、情報理論の思想とその証明技術の基盤をなすものであることを改めて認識していただけることを目指します。
漸近等分割性 (AEP) の厳密な定義
AEPを議論するにあたり、最も基本的なケースである離散無記憶情報源（Discrete Memoryless Source, DMS）を考えます。DMSは、アルファベット $\mathcal{X} = {x_1, x_2, \dots, x_m}$ から記号を独立に、かつ固定された確率分布 $p(x)$ に従って生成します。$p(x) = P(X=x)$ は、任意の $x \in \mathcal{X}$ に対して $p(x) > 0$ であり、$\sum_{x \in \mathcal{X}} p(x) = 1$ を満たします。
長さ $n$ の系列 $X_1X_2\dots X_n$ を $X^n$ と表記します。各 $X_i$ は独立に、同じ分布 $p(x)$ に従います。系列 $x^n = x_1x_2\dots x_n$ が観測される確率は、独立性より $P(X^n=x^n) = \prod_{i=1}^n p(x_i)$ で与えられます。対数を取ると、$\log P(X^n=x^n) = \sum_{i=1}^n \log p(x_i)$ となります。情報源の生成する系列の確率の対数は、確率変数 $\log p(X_i)$ の和として表されることが分かります。
ここで、確率変数 $Z_i = -\log p(X_i)$ を考えます。$E[Z_i] = E[-\log p(X_i)] = -\sum_x p(x) \log p(x) = H(X)$ は、情報源のエントロピーです。大数の法則によれば、独立同分布な確率変数の標本平均は、標本数 $n$ を大きくするにつれて、その期待値に確率収束します。すなわち、$\frac{1}{n} \sum_{i=1}^n Z_i \to E[Z_1]$ as $n \to \infty$（確率収束）。 これを元の確率に戻すと、 $$ \frac{1}{n} \sum_{i=1}^n (-\log p(X_i)) \to H(X) \quad \text{as } n \to \infty $$ $$ -\frac{1}{n} \log P(X^n) \to H(X) \quad \text{as } n \to \infty $$ $$ \frac{1}{n} \log P(X^n) \to -H(X) \quad \text{as } n \to \infty $$ これは、十分に大きな $n$ に対して、$P(X^n) \approx 2^{-nH(X)}$ となることを示唆しています。より厳密には、AEPは次のように定義されます。
定理 (AEP): DMSによって生成される長さ $n$ の系列 $X^n$ に対して、任意の $\epsilon > 0$ について、 $$ P\left(\left|-\frac{1}{n} \log P(X^n) - H(X)\right| \le \epsilon\right) \to 1 \quad \text{as } n \to \infty $$ あるいは等価的に、 $$ P\left(2^{-n(H(X)+\epsilon)} \le P(X^n) \le 2^{-n(H(X)-\epsilon)}\right) \to 1 \quad \text{as } n \to \infty $$
この定理は、大数の法則を確率の対数に適用した直接的な結果であり、その証明も $-\frac{1}{n} \log P(X^n)$ が確率変数 $-\log p(X_i)$ の平均であることから、大数の法則を用いて容易に導かれます。
典型集合 (Typical Set) の定義と性質
AEPに基づき、シャノンは典型集合 (Typical Set)という概念を導入しました。これは、確率的に発生しやすい、すなわち「典型的な」系列を集めた集合です。AEPの定義に基づき、典型集合 $A_\epsilon^{(n)}$ を次のように定義します。
定義 (典型集合): 確率分布 $p(x)$ を持つDMSから生成される長さ $n$ の系列 $x^n$ に対して、$\epsilon > 0$ を所与としたとき、典型集合 $A_\epsilon^{(n)}$ は次のように定義されます。 $$ A_\epsilon^{(n)} = \left{x^n \in \mathcal{X}^n \mid 2^{-n(H(X)+\epsilon)} \le P(x^n) \le 2^{-n(H(X)-\epsilon)}\right} $$
AEPは、この典型集合 $A_\epsilon^{(n)}$ が、$n$ が十分に大きいとき、ほとんど全ての確率質量を含むことを保証します。すなわち、$P(A_\epsilon^{(n)}) \to 1$ as $n \to \infty$ です。
典型集合には、情報理論の証明において非常に有用な2つの重要な性質があります。これらの性質は、AEPから直接導かれます。
-
典型集合のサイズ: $n$ が十分に大きいとき、典型集合 $A_\epsilon^{(n)}$ に含まれる系列の数 $|A_\epsilon^{(n)}|$ は、おおよそ $2^{nH(X)}$ となります。より正確には、任意の $\epsilon > 0$ について、$n$ が十分に大きいとき、 $$ (1-\epsilon) 2^{n(H(X)-\epsilon)} \le |A_\epsilon^{(n)}| \le 2^{n(H(X)+\epsilon)} $$ 特に、$\frac{1}{n} \log |A_\epsilon^{(n)}| \to H(X)$ as $n \to \infty$ です。これは、典型集合のサイズの指数が情報源のエントロピーによって決定されることを示しています。証明は、$P(A_\epsilon^{(n)}) \ge 1-\delta$ （$\delta$は小さい値）と、典型集合の定義域における各系列の確率の下限・上限を利用して行われます。
-
典型集合上の確率質量: 典型集合 $A_\epsilon^{(n)}$ に含まれる任意の系列 $x^n \in A_\epsilon^{(n)}$ の確率は、おおよそ $2^{-nH(X)}$ です。より正確には、定義により、 $$ 2^{-n(H(X)+\epsilon)} \le P(x^n) \le 2^{-n(H(X)-\epsilon)} \quad \forall x^n \in A_\epsilon^{(n)} $$ これは、典型集合内の全ての系列がほぼ等しい確率を持つことを意味します。この性質が「漸近等分割性」という名称の由来となっています（状態空間が漸近的に確率 $2^{-nH(X)}$ を持つ等しい確率の領域に分割される、というイメージ）。
これらの性質は、非常に長い系列を考える際に、全可能な $\mathcal{X}^n$ の空間ではなく、サイズがはるかに小さい典型集合 $A_\epsilon^{(n)}$ に焦点を絞ることができるという、強力な示唆を与えます。全系列の数は $|\mathcal{X}|^n = m^n = 2^{n \log_2 m}$ ですが、典型集合のサイズは約 $2^{nH(X)}$ であり、通常 $H(X) < \log_2 m$ であるため、$n$ が大きいほどその差は指数関数的に開きます。情報源符号化の文脈では、$H(X)$ は情報源を圧縮する際の理論的な限界を示します。
統計的典型性の意味合い
典型集合は、文字通り、統計的に「典型的な」振る舞いをする系列の集合です。例えば、コイン投げ（$p(Head)=p, p(Tail)=1-p$）を $n$ 回繰り返す場合を考えます。ヘッドが出る回数は、大数の法則により $np$ に近づきます。したがって、典型的な系列では、ヘッドとテールの出現回数がそれぞれ約 $np$ と $n(1-p)$ になります。このような系列の確率は、$p^{np}(1-p)^{n(1-p)} \approx (p^p (1-p)^{1-p})^n = (2^{-H(X)})^n = 2^{-nH(X)}$ となります。典型集合は、このような出現回数が「平均的」な系列を包含する集合であり、その数は二項係数 $\binom{n}{np}$ で近似でき、スターリングの公式などを用いると $\binom{n}{np} \approx 2^{nH(X)}$ となることが分かります。
つまり、AEPと典型集合は、長い系列においては、その統計的性質（記号の出現頻度など）が情報源の真の確率分布を強く反映することを示しています。確率の低い非典型的な系列も存在しえますが、それら全てを合わせた確率は、$n$ が増えるにつれてゼロに収束していきます。この事実は、推定や推論といった統計的な問題において、「ほとんど全ての観測データは典型的な振る舞いをする」という強力な仮定を置くことを可能にします。
情報理論的証明技術への応用
AEPと典型集合は、シャノンの情報理論における最も基本的な定理、特に符号化定理の証明において不可欠なツールです。
情報源符号化定理 (Source Coding Theorem)
情報源符号化定理は、情報源を損失なく圧縮する際の最小平均符号長が、情報源のエントロピーによって与えられることを示します。AEPを用いたこの定理の証明は、典型集合を利用することで非常に直感的かつ簡潔になります。
証明のアイデアは以下の通りです。長さ $n$ の系列を符号化する際、非典型的な系列は無視しても、その発生確率は無視できるほど小さいため、復号誤りの確率は小さく保たれます。したがって、符号化の対象は典型集合 $A_\epsilon^{(n)}$ 内の系列のみとします。典型集合のサイズは $|A_\epsilon^{(n)}| \le 2^{n(H(X)+\epsilon)}$ なので、これらの系列を区別するために必要な符号語の数は多くても $2^{n(H(X)+\epsilon)}$ 個です。各符号語の長さを $\lceil \log_2 |A_\epsilon^{(n)}| \rceil$ とすれば、これは $n(H(X)+\epsilon)$ に漸近的に近づきます。したがって、1記号あたりの平均符号長は $H(X)$ に任意に近づけることができることを示唆しています。
逆に、平均符号長が $H(X)$ より小さい場合は、符号語の数が $2^{nH(X)}$ より少なくなり、典型集合内の全ての系列を符号化しきれなくなるため、復号誤り確率がゼロに収束しなくなることを示すことができます。このように、AEPはエントロピーが圧縮の限界であることの証明を可能にします。
チャネル符号化定理 (Channel Coding Theorem)
ノイズのある通信路を通じた信頼性のある情報伝送の限界（通信路容量）を定めるチャネル符号化定理においても、AEPと同様の概念である共同漸近等分割性 (Joint Asymptotic Equipartition Property, Joint AEP)と共同典型集合 (Joint Typical Set)が中心的な役割を果たします。
共同AEPは、情報源 $X$ とそれを通信路 $P(y|x)$ を通して得られた出力 $Y$ からなる長さ $n$ の対系列 $(X^n, Y^n)$ について、その結合確率 $P(X^n=x^n, Y^n=y^n) = P(X^n=x^n)P(Y^n=y^n|X^n=x^n)$ の対数の平均 $-\frac{1}{n} \log P(X^n, Y^n)$ が、十分に長い系列に対して、結合エントロピー $H(X,Y)$ に確率収束することを示します。
共同典型集合 $A_\epsilon^{(n)}$ は、この共同AEPに基づき、$\left|-\frac{1}{n} \log P(x^n, y^n) - H(X,Y)\right| \le \epsilon$ を満たす系列対 $(x^n, y^n)$ の集合として定義されます。この集合は、$n$ が大きいとき、約 $2^{nH(X,Y)}$ 個の要素を持ち、全確率質量のほとんどを含みます。
チャネル符号化定理の証明（特にランダム符号化を用いた存在証明）では、この共同典型集合の性質が決定的に重要になります。送信側で符号語 $x^n$ を選び、通信路を通して受信語 $y^n$ を得たとき、送信された符号語が $x^n$ であるならば、受信された $y^n$ は $(x^n, y^n)$ が共同典型集合に属するような系列である可能性が非常に高い、という事実を利用します。受信側では、受信した $y^n$ に対して、共同典型集合に属するような符号語 $x^n$ を探します。もしそのような符号語がただ一つ見つかれば、それを復号結果とします。複数の符号語が見つかる、あるいは一つも見つからない場合に誤りが発生すると考えます。共同典型集合の性質から、符号語を適切に設計すれば、通信路容量以下のレートであれば、誤り確率を $n$ を大きくすることで任意に小さくできることが示されます。
この証明の美しさは、個々の符号語や復号器を具体的に設計するのではなく、「ランダムに選ばれた符号語のほとんどが、非常に長い系列に対して良い性能を示す」という確率論的な存在証明が可能になる点にあります。これはAEPが提供する統計的規則性に基づいています。
AEPの拡張と現代における意義
上で述べたAEPは、最も単純なケースである離散無記憶情報源に対するものですが、この概念はより一般的な情報源（例えば、定常エルゴード情報源）に対しても拡張されます。定常エルゴード情報源に対するAEPは、系列エントロピー率（entropy rate）を用いて同様の形で定式化され、より広いクラスの情報源に対する情報源符号化定理の基盤となります。
また、連続値情報源に対しても、微分エントロピーや相互情報量を用いてAEPに類する性質（連続値AEP）が成り立ちます。これは連続値通信路、特にガウスチャネルの容量を導出する際に重要な役割を果たします。
現代の情報科学や関連分野において、AEPおよび典型性の概念は様々な形で現れます。 * 大偏差原理 (Large Deviation Theory): AEPは、標本平均が期待値から大きく外れる確率の漸近的な振る舞いを記述する大偏差原理の初歩的な例と見なすことができます。大偏差原理は統計物理学、金融工学、信頼性工学など、幅広い分野で応用されています。 * 情報幾何学 (Information Geometry): 確率分布の集合に情報理論的な距離（例えばKLダイバージェンス）を導入する情報幾何学において、AEPや典型集合の概念は確率分布の漸近的な振る舞いを理解するための基礎となります。 * 機械学習: データ列の典型性や確率分布の集中現象は、機械学習におけるサンプリング効率、モデルの汎化能力、異常検知などに関連します。例えば、学習データが真のデータ分布からの「典型的な」サンプルであるという仮定は、多くの学習アルゴリズムの根底にあります。
結論
クロード・シャノンが導入した漸近等分割性（AEP）は、情報理論における確率論的アプローチの核心をなす概念です。これは、十分に長い独立同分布系列が示す「統計的典型性」を厳密に定義し、ほとんど全ての確率質量が典型集合に集中するという強力な性質を明らかにしました。
AEPとそれに続く典型集合、共同典型集合の概念は、情報源符号化定理やチャネル符号化定理といった情報理論の最も基本的な結果を、エレガントかつ確率論的に証明するための不可欠なツールとなりました。これらの証明技術は、その後の情報理論研究のみならず、統計学、機械学習、確率論など、幅広い分野における漸近解析や確率的証明の手法に影響を与えています。
シャノンのAEPに関する洞察は、データ系列の「情報量」がその確率の対数と密接に関連し、長い系列の振る舞いが情報源のエントロピーによって支配されるという、情報理論の根幹をなす理解を提供しました。情報理論を深く学ぶ上で、AEPが単なる定理のステートメントとしてではなく、確率的なデータ分析における「典型性」という本質的な概念を捉えていることを理解することは、その後の発展的な理論や応用を理解する上で極めて重要であると言えるでしょう。