シャノン研究ノート

クロード・シャノンによる典型集合 (Typical Set)：漸近等分割性(AEP)からの展開と情報理論の証明技術への応用

Tags: 情報理論, 典型集合, 漸近等分割性, シャノン, 確率論, ソース符号化, チャネル容量

はじめに：シャノンの情報理論における確率論の役割

クロード・シャノンの情報理論は、通信システムにおける情報の定量化と伝送の限界を数学的に明らかにしました。その基礎には、強力な確率論的な枠組みが存在します。特に、情報源符号化定理やチャネル容量定理といった中心的結果の証明において、確率論における「大数の法則」や「エントロピー」といった概念が本質的な役割を果たします。

これらの定理の証明を深く理解する上で不可欠な概念の一つが「典型集合 (Typical Set)」です。典型集合は、長い記号系列（文字列）が従う確率分布において、統計的に「典型的」と見なせる系列全体からなる集合です。この集合の性質を分析することが、情報源の圧縮可能性や通信路を通じた信頼性の高い情報伝送の限界を定める上で鍵となります。

本稿では、シャノンの情報理論における典型集合の概念に焦点を当てます。まず、その基盤となる漸近等分割性（Asymptotic Equipartition Property; AEP）を再確認し、それに基づいて典型集合を厳密に定義します。次に、典型集合が持つ重要な性質、特にその確率的振る舞いと集合のサイズに関する定理を解説します。そして、これらの性質がどのようにしてソース符号化定理やチャネル容量定理といったシャノンの主要な結果の証明に活用されるのかを詳述します。

漸近等分割性 (AEP) とその直感

典型集合の理解には、まず漸近等分割性（AEP）を把握する必要があります。AEPは、ある情報源から独立同分布（i.i.d.）に従って生成される十分に長い記号系列の確率が、概ね一定の値に収束することを示唆する性質です。

具体的には、離散無記憶情報源（Discrete Memoryless Source; DMS）$X$がアルファベット $\mathcal{X}$ 上で確率分布 $p(x)$ を持つとします。この情報源から生成される長さ $n$ の系列 $x_1, x_2, \dots, x_n$ を $x^n$ と表します。$X$がi.i.d.情報源であるため、系列 $x^n$ が生成される確率は次のように書けます。 $$ P(x^n) = \prod_{i=1}^n p(x_i) $$ AEPは、適切な条件下で、この確率の対数（あるいはその平均）が、系列長 $n$ が大きくなるにつれて情報源のエントロピー $H(X)$ に収束することを示します。正確には、確率の対数の負の平均である $-\frac{1}{n} \log P(x^n)$ が、ほとんど全ての系列 $x^n$ に対して $H(X)$ に近づきます。これは大数の法則の多次元版あるいはエントロピー版と解釈できます。 $$ -\frac{1}{n} \log P(x^n) \to H(X) \quad \text{in probability as } n \to \infty $$ 対数を底2とすると、この関係は次のように書けます。 $$ P(x^n) \approx 2^{-nH(X)} $$ これは、十分に長い系列においては、その系列が発生する確率が概ね $2^{-nH(X)}$ という一つの値に集中するということを意味します。AEPは、複雑な確率分布を持つ長い系列の挙動を、エントロピーという単一の量を用いて近似的に捉えることを可能にします。

典型集合 (Typical Set) の定義と性質

AEPの概念に基づき、統計的に「典型的」な系列を集めた集合として典型集合が定義されます。典型集合にはいくつかのバリエーションがありますが、ここでは情報理論の文脈で標準的に用いられる「ストロングリー典型集合 (Strongly Typical Set)」に近い概念を扱います。

ある $\epsilon > 0$ に対して、長さ $n$ の系列 $x^n \in \mathcal{X}^n$ が $\epsilon$-典型的 ( $\epsilon$-typical) であるとは、その経験分布が情報源の真の確率分布に十分に近く、かつその発生確率がエントロピーによって規定される範囲にあることを指します。より厳密には、多くの標準的な定義では、$-\frac{1}{n} \log P(x^n)$ がエントロピー $H(X)$ の近くにある系列を典型系列と定義します。

定義： $\epsilon$-典型集合 ($A_\epsilon^{(n)}$)

離散無記憶情報源 $X$ から生成される長さ $n$ の系列 $x^n \in \mathcal{X}^n$ に対し、$\epsilon > 0$ とします。$\epsilon$-典型集合 $A_\epsilon^{(n)}$ は次のように定義されます。 $$ A_\epsilon^{(n)} = \left{ x^n \in \mathcal{X}^n \mid |-\frac{1}{n} \log P(x^n) - H(X)| \le \epsilon \right} $$ この定義は、AEPで述べた $-\frac{1}{n} \log P(x^n)$ が $H(X)$ に収束するという性質を、有限長 $n$ に対して $\epsilon$ の許容誤差を持って形式化したものです。

典型集合は以下の重要な性質を持ちます。これらの性質が、符号化定理の証明の基盤となります。

  1. 典型集合に含まれる確率: 系列長 $n$ が十分に大きくなるにつれて、情報源から生成される系列が典型集合に含まれる確率が1に収束します。 $$ P(A_\epsilon^{(n)}) \to 1 \quad \text{as } n \to \infty $$ これはAEPの直接的な帰結であり、大数の法則により、ほとんど全ての長い系列が「典型的」になることを意味します。
  2. 典型集合内の系列の確率: 典型集合 $A_\epsilon^{(n)}$ に含まれる任意の系列 $x^n$ の発生確率は、次のように上下から抑えられます。 $$ 2^{-n(H(X)+\epsilon)} \le P(x^n) \le 2^{-n(H(X)-\epsilon)} $$ これは典型集合の定義 $|-\frac{1}{n} \log P(x^n) - H(X)| \le \epsilon$ を変形することで得られます。典型系列の確率が、エントロピー $H(X)$ を用いて概ね $2^{-nH(X)}$ のオーダーで集中していることを示しています。
  3. 典型集合のサイズ: 典型集合 $A_\epsilon^{(n)}$ に含まれる系列の数（集合のサイズ $|A_\epsilon^{(n)}|$）は、系列長 $n$ が十分に大きくなるにつれて、 $2^{nH(X)}$ に漸近的に等しくなります。より正確には、以下の不等式が成り立ちます。 $$ (1-\epsilon) 2^{n(H(X)-\epsilon)} \le |A_\epsilon^{(n)}| \le 2^{n(H(X)+\epsilon)} $$ そして、$|A_\epsilon^{(n)}|$ は $2^{nH(X)}$ に「 probabilistically close」あるいは「asymptotically equal」であると言えます。 $$ \frac{1}{n} \log |A_\epsilon^{(n)}| \to H(X) \quad \text{in probability as } n \to \infty $$ この性質は、典型集合に含まれる確率が1に収束すること（性質1）と、典型集合内の各系列の確率がほぼ等しいこと（性質2）を組み合わせることで導かれます。全確率が1に近づく集合に含まれる各要素の確率がほぼ $2^{-nH(X)}$ ならば、その集合のサイズは約 $1 / 2^{-nH(X)} = 2^{nH(X)}$ となる、という直感に対応します。

これらの性質、特に性質1と性質3は、シャノンの情報理論における多くの証明で中心的な役割を果たします。

ソース符号化定理（可逆圧縮の限界）への応用

情報源符号化定理（ソース符号化定理）は、情報源のデータを平均符号長を最小化する形で可逆圧縮する際の理論的な限界を示します。定理は、平均符号長の下限が情報源のエントロピー $H(X)$ であることを示しています。

典型集合の概念は、この定理の証明、特に「エントロピー以上のレートであれば、系列長を十分に長くすることで任意の小さな誤り確率で復号できる」という部分（直接部分）の証明に用いられます。

証明のアイデアは以下の通りです。

  1. 非常に長い系列 $x^n$ が情報源から生成されたとします。
  2. 系列 $x^n$ が典型集合 $A_\epsilon^{(n)}$ に含まれる確率は、$n \to \infty$ で1に近づきます（性質1）。
  3. 符号化器は、典型集合 $A_\epsilon^{(n)}$ に含まれる系列のみを符号化の対象とします。典型集合のサイズは約 $2^{nH(X)}$ です（性質3）。
  4. サイズが約 $M = 2^{n(H(X)+\delta)}$ の集合を符号化するには、 $\log_2 M \approx n(H(X)+\delta)$ ビットが必要です。典型集合のサイズは約 $2^{nH(X)}$ ですから、この集合に番号を割り当てるには約 $n H(X)$ ビットで十分です。
  5. 典型集合に含まれる系列を $2^{nH(X)}$ 個程度の符号語に対応させます。これには約 $nH(X)$ ビットが必要となります。つまり、1記号あたりの平均符号長は約 $H(X)$ となります。
  6. 復号器は、受け取った符号語に対応する系列が典型集合に含まれると仮定して復号を行います。
  7. 情報源から生成された系列が典型集合に含まれない確率は、$n \to \infty$ で0に近づきます。典型集合に含まれない系列は、符号化されていないか、あるいは別の系列と同じ符号語が割り当てられる可能性がありますが、その確率は非常に小さくなります。
  8. したがって、平均符号長を $H(X)+\delta$ （任意の小さな $\delta > 0$）とすることで、系列長 $n$ を十分に長くすれば、復号誤り確率を限りなく小さくすることができます。

このように、典型集合は「圧縮可能なたたみ込み範囲」を明確にし、その範囲のサイズがエントロピーによって規定されることを示すことで、ソース符号化定理の直接部分の証明を可能にします。

チャネル容量定理（ノイズあり通信の限界）への応用

チャネル容量定理は、ノイズが存在する通信路を通じた信頼性の高い情報伝送レートの理論的な最大値（チャネル容量）を示します。この定理の証明、特に「チャネル容量以下のレートであれば、系列長を十分に長くすることで任意の小さな誤り確率で情報伝送できる」という部分（直接部分）においても、典型集合の概念、特に「ジョイント典型集合 (Jointly Typical Set)」が中心的な役割を果たします。

送信記号系列 $x^n$ と受信記号系列 $y^n$ のペア $(x^n, y^n)$ がジョイント典型であるとは、送信側からの系列 $x^n$ が情報源 $X$ の典型系列であり、受信側での系列 $y^n$ がチャネル特性 $p(y|x)$ に従って生成される系列として典型であり、かつ、ペア $(x^n, y^n)$ 全体としても同時分布 $p(x,y) = p(x)p(y|x)$ に関して典型である、というような概念です。より厳密な定義は、 $-\frac{1}{n} \log p(x^n)$, $-\frac{1}{n} \log p(y^n)$, $-\frac{1}{n} \log p(x^n, y^n)$ がそれぞれ $H(X)$, $H(Y)$, $H(X,Y)$ の近くにある、というものです。

定義： $\epsilon$-ジョイント典型集合 ($A_\epsilon^{(n)}(X,Y)$)

同時確率分布 $p(x,y)$ に従う確率変数ペア $(X,Y)$ に対して、$\epsilon > 0$ とします。長さ $n$ のペア系列 $(x^n, y^n) \in \mathcal{X}^n \times \mathcal{Y}^n$ が $\epsilon$-ジョイント典型であるとは、次のように定義されます。 $$ A_\epsilon^{(n)}(X,Y) = \left{ (x^n, y^n) \mid \begin{aligned} &|-\frac{1}{n} \log p(x^n) - H(X)| \le \epsilon, \ &|-\frac{1}{n} \log p(y^n) - H(Y)| \le \epsilon, \ &|-\frac{1}{n} \log p(x^n, y^n) - H(X,Y)| \le \epsilon \end{aligned} \right} $$ ジョイント典型集合も、単一の情報源に対する典型集合と同様にいくつかの重要な性質を持ちます。最も重要な性質の一つは、同時分布 $p(x,y)$ から生成されるペア系列 $(X^n, Y^n)$ がジョイント典型集合に含まれる確率が、$n \to \infty$ で1に収束することです。また、ジョイント典型集合のサイズは約 $2^{nH(X,Y)}$ となります。

チャネル容量定理の証明では、このジョイント典型性の概念を用いて、送信可能なメッセージ数を評価します。

証明のアイデア（ランダム符号化を用いる場合の一例）は以下の通りです。

  1. 送信可能なメッセージ数 $M$ を決めます。レートは $R = \frac{\log_2 M}{n}$ です。
  2. $M$ 個のメッセージそれぞれに対し、長さ $n$ の符号語をランダムに生成します。これらの符号語は、ある固定された入力確率分布 $p(x)$ からi.i.d.に生成されると仮定します。
  3. メッセージ $m$ に対応する符号語 $X^n(m)$ が送信されたとき、受信側では系列 $Y^n$ が観測されます。
  4. 受信器は、観測された $Y^n$ に対して、どのメッセージ $m$ の符号語 $X^n(m)$ が送信された可能性が最も高いかを判定します。この判定は「ジョイント典型性復号 (Joint Typicality Decoding)」に基づきます。すなわち、受信器は、ペア $(X^n(m), Y^n)$ がジョイント典型集合に含まれるような、唯一のメッセージ $m$ を探します。
  5. 誤りが発生するのは、送信されたメッセージ $m$ に対応するペア $(X^n(m), Y^n)$ がジョイント典型でない場合、あるいは、送信されたメッセージ $m$ とは異なるメッセージ $m' \ne m$ に対応するペア $(X^n(m'), Y^n)$ がジョイント典型である場合です。
  6. シャノンは、レート $R$ が相互情報量 $I(X;Y)$ より小さければ（つまり、 $R < I(X;Y)$ であれば）、ジョイント典型性復号における誤り確率が系列長 $n$ を長くするにつれて0に近づくことを示しました。この証明において、異なるメッセージ $m'$ の符号語 $X^n(m')$ と観測された $Y^n$ がジョイント典型になる確率は非常に小さいことが、ジョイント典型集合の性質（サイズ推定など）を用いて示されます。

チャネル容量は、この $I(X;Y)$ を可能な入力分布 $p(x)$ 全てにわたって最大化した値 $C = \max_{p(x)} I(X;Y)$ です。ジョイント典型集合は、信頼性の高い通信が可能となる「望ましい」入出力ペアの集合を数学的に定義し、その統計的性質を利用することで、情報伝送レートの限界を定量的に示すことを可能にしました。

歴史的背景と現代における意義

典型集合の概念は、シャノンが1948年の画期的な論文 "A Mathematical Theory of Communication" の中で implicitly に用いていました。後の研究者たちによってその概念がより形式的に整理され、「典型集合」という用語が定着しました。これは、複雑な確率的な事象に対して、確率の高い少数の「典型的な」結果に焦点を当てることで、理論的な解析を容易にするという、シャノン的な確率論の巧みな応用法の一つです。

この概念は、情報理論における確率論的な定理証明の標準的な手法となり、その後の多くの発展に影響を与えました。例えば、多端子情報理論（ネットワーク情報理論）における様々な容量領域の解析や、統計学における情報理論的手法（仮説検定、推定など）への応用、さらには機械学習における情報理論的尺度を用いたアルゴリズム設計など、現代の情報科学の広範な分野でその考え方の影響を見ることができます。

典型集合は、単なる数学的な道具に留まらず、情報理論が扱う「情報」という抽象的な概念が、長い記号系列の確率的な振る舞いとどのように結びついているのかを明確に示唆しています。それは、情報の本質が、発生確率の低い、すなわち驚きや不確実性の高い事象にある、という情報量・エントロピーの定義とも整合しています。典型集合は、そのエントロピーによって「圧縮された」形で表現される確率空間上の部分集合であり、情報理論における確率の集中現象を示す重要な例です。

結論

クロード・シャノンによって導入された典型集合の概念は、漸近等分割性（AEP）を基盤とし、情報源符号化定理やチャネル容量定理といった情報理論の根幹をなす定理の証明において、確率論的な議論を可能にする強力なツールとして機能します。典型集合が持つ「含まれる確率が1に収束する」「サイズが $2^{nH(X)}$ に漸近的に等しい」といった性質は、情報源の圧縮の限界や信頼性のある通信の限界を定量的に導出する上で不可欠です。

典型集合とその関連概念（ジョイント典型集合など）は、シャノンの情報理論の後の発展においても、その確率論的基盤を支え続けています。現代の情報科学においても、情報理論的手法が様々な分野で応用される中で、典型集合によって示される確率の集中現象や漸近的な性質の理解は、依然として重要性を保っています。シャノンのオリジナルの洞察が、いかに深く、そして長期にわたって学術研究に影響を与えているかを示す好例と言えるでしょう。

本稿が、情報理論の研究に携わる読者の皆様にとって、典型集合の概念、その数学的基盤、そしてシャノンの主要な定理におけるその役割について、より深い理解の一助となれば幸いです。典型集合の厳密な定義や性質の詳細な証明については、シャノンの原論文や現代の情報理論に関する専門書をご参照ください。