シャノン研究ノート

クロード・シャノンによる共同典型集合：定義、性質、そして情報理論の証明技術への応用

はじめに：共同典型集合の重要性

クロード・シャノンが1948年の記念碑的論文『A Mathematical Theory of Communication』で確立した情報理論は、不確実性の定量化と情報伝送の限界に関する普遍的な枠組みを提供しました。この理論体系を支える基盤概念の一つに、「漸近等分割性 (Asymptotic Equipartition Property, AEP)」があります。AEPは、独立同分布（i.i.d.）な確率変数から生成される長nのシーケンスにおいて、その確率が (2^{-nH}) に漸近的に等しい「典型シーケンス」が全体の確率質量の大部分を占めることを示します。

そして、AEPを二つ以上の確率変数に拡張した概念が「共同典型集合 (Jointly Typical Set)」です。これは、二つ（またはそれ以上）の確率変数から同時に生成されるシーケンスのペア（またはタプル）が、特定の統計的性質を持つ集合に高い確率で含まれることを主張するものです。共同典型集合は、単変数のAEPと同様に、情報理論における多くの重要な定理、特にチャネル容量定理やソース符号化定理（特に複数の情報源や率歪み理論）の証明において不可欠なツールとして機能します。

本稿では、この共同典型集合について、その厳密な定義、主要な性質、そして情報理論の主要な結果を導出する上での具体的な応用方法について掘り下げて解説します。ターゲット読者である情報科学分野の専門家の皆様にとって、この概念の深い理解が自身の研究の一助となれば幸いです。

共同典型集合の厳密な定義

二つの離散確率変数 (X) および (Y) が、結合確率質量関数 (P_{XY}(x, y)) に従って分布しているとします。ここから独立同分布に抽出された長さ (n) のシーケンスペア ((x_1, \dots, x_n)) と ((y_1, \dots, y_n)) を考えます。これらをまとめて ((x^n, y^n)) と表記します。

与えられた (\epsilon > 0) に対し、ペアシーケンス ((x^n, y^n)) が (\epsilon)-共同典型集合 (A_{\epsilon}^{(n)}(P_{XY})) に含まれるとは、以下の三つの条件を全て満たすことであると定義されます。

1. (\left| -\frac{1}{n} \log P_X(x^n) - H(X) \right| \le \epsilon)
2. (\left| -\frac{1}{n} \log P_Y(y^n) - H(Y) \right| \le \epsilon)
3. (\left| -\frac{1}{n} \log P_{XY}(x^n, y^n) - H(X, Y) \right| \le \epsilon)

ここで、 * (P_X(x^n) = \prod_{i=1}^n P_X(x_i)) はシーケンス (x^n) が確率変数 (X) から独立に生成される確率です。(P_Y(y^n)), (P_{XY}(x^n, y^n)) も同様に定義されます。 * (H(X)), (H(Y)) はそれぞれの確率変数のエントロピーです。 * (H(X, Y)) は結合エントロピーです。

これらの条件は、シーケンス (x^n), (y^n), そしてペア ((x^n, y^n)) のそれぞれが、それぞれの確率分布に基づいたAEPの性質を満たすことを要求しています。より具体的には、(x^n) はおおよそ (2^{-nH(X)}) の確率を持ち、(y^n) はおおよそ (2^{-nH(Y)}) の確率を持ち、そしてペア ((x^n, y^n)) はおおよそ (2^{-nH(X,Y)}) の確率を持つシーケンスペアである、ということを意味します。

重要なのは、これらの条件が同時に満たされることです。これは単に (x^n) が (X) の典型シーケンスであり、かつ (y^n) が (Y) の典型シーケンスであることだけを要求しているわけではありません。なぜなら、(X) と (Y) が統計的に従属している場合、典型シーケンスのペアであっても、その結合確率が (2^{-nH(X) - nH(Y)}) とは異なる可能性があり、実際には (2^{-nH(X,Y)}) に近くなるべきだからです。共同典型集合は、この結合確率の構造を正しく捉える概念です。

この定義はシャノンの原論文で直接的にこの形式で提示されているわけではありませんが、彼の容量定理などの証明の過程で用いられる確率論的な性質や漸近的な振る舞いの解析において、この概念の根幹となる考え方が見られます。共同典型集合という用語と厳密な形式化は、その後の情報理論研究によって確立されました。

共同典型集合の主要な性質

共同典型集合 (A_{\epsilon}^{(n)}(P_{XY})) は、(n) が十分に大きいとき、以下の重要な性質を持ちます。

1. 確率論的な性質: 共同典型集合に含まれるペアシーケンスの確率の総和は、(n \to \infty) のとき1に漸近的に近づきます。すなわち、(P_{XY}((X^n, Y^n) \in A_{\epsilon}^{(n)}(P_{XY})) \to 1) as (n \to \infty)。これは、大部分の確率質量が共同典型集合に集中していることを意味します。
2. サイズ（要素数）: 共同典型集合のサイズ、すなわち含まれるペアシーケンスの個数は、(n) が十分に大きいとき、おおよそ (2^{n H(X,Y)}) です。より厳密には、((1-\epsilon') 2^{n(H(X,Y)-\epsilon)} \le |A_{\epsilon}^{(n)}(P_{XY})| \le 2^{n(H(X,Y)+\epsilon)}) のように、指数部が結合エントロピー (H(X,Y)) に収束します。ここで (\epsilon' \to 0) as (n \to \infty).
3. 独立性のチェック: ここで、補助的な概念として、確率変数 (X) と (Y) が独立であると仮定した場合の「偽の」共同典型集合を考えます。つまり、(P_X(x)) に従って生成された (x^n) と、(P_Y(y)) に従って生成された (y^n) のペア ((x^n, y^n)) であって、独立な場合の結合エントロピー (H(X) + H(Y)) に関してAEPを満たすものです。この集合は、おおよそ (2^{n(H(X)+H(Y))}) 個の要素を持ちます。もし実際の確率分布が (P_{XY}) であり、(X) と (Y) が真には独立でない場合、(P_{XY}(x^n, y^n)) に従ってランダムに生成されたペア ((X^n, Y^n)) が、独立性を仮定した偽の共同典型集合に含まれる確率は、(n) について指数関数的に小さくなります。これは、(\frac{1}{n} \log \frac{P_{XY}(x^n, y^n)}{P_X(x^n)P_Y(y^n)} \approx -I(X;Y)) であり、独立ならば (I(X;Y)=0) となるべきですが、真の分布が独立でない場合は (I(X;Y)>0) となるためです。

これらの性質は、大数の法則とエントロピーの関係に基づいています。特に、(-\frac{1}{n}\log P(x^n) \to E[-\log P(X)] = H(X)) (概収束または確率収束)というAEPの基本的な考え方が、多変数に拡張されたものです。

情報理論の証明技術への応用

共同典型集合の概念は、情報理論における多くの漸近的な結果、特に容量定理の証明において極めて強力なツールとなります。

チャネル容量定理の達成可能性証明

離散無記憶チャネル (Discrete Memoryless Channel, DMC) は、入力アルファベット (\mathcal{X})、出力アルファベット (\mathcal{Y})、そして遷移行列 (P_{Y|X}(y|x)) で定義されます。チャネル容量定理は、ノイズがあっても信頼性高く伝送できる最大レートは相互情報量 (I(X;Y)) の最大値、すなわちチャネル容量 (C = \max_{P_X} I(X;Y)) であると主張します。共同典型集合は、この定理の「達成可能性」パート、つまりレート (R < C) であれば誤り確率を任意に小さくできる符号が存在することを示す際に用いられます。

証明の概略は以下の通りです。 1. 送信側は、符号帳 (\mathcal{C} = {x^n(m)}{m=1}^{M}) をランダムに生成します。各コードワード (x^n(m)) は、ある入力分布 (P_X) に従ってi.i.d.に生成された長さ (n) のシーケンスとします。ここで (M = 2^{nR}) です。 2. メッセージ (m) を送信する際、送信機は (x^n(m)) をチャネルを通して送ります。 3. 受信機は出力シーケンス (y^n) を受け取ります。 4. 受信機は、受け取った (y^n) と符号帳の各コードワード (x^n(m')) ((m'=1, \dots, M)) を比較し、ペア ((x^n(m'), y^n)) が、結合分布 (P{XY} = P_X P_{Y|X}) に関する (\epsilon)-共同典型集合 (A_{\epsilon}^{(n)}(P_{XY})) に含まれるような、唯一の (m') を復号出力とします。このような (m') が複数あるか、あるいは一つもない場合は誤りとします。

ここで共同典型集合の性質が活きてきます。 * 送信されたメッセージに対応するコードワード (x^n(m)) と、それを受けてチャネルから出力された (y^n) のペア ((x^n(m), Y^n)) は、(n) が大きいとき、高い確率で共同典型集合 (A_{\epsilon}^{(n)}(P_{XY})) に含まれます（性質1）。これは、(X^n) を (P_X) から、そして (Y^n) を (P_{Y|X}(\cdot|X^n)) から独立に生成したペア ((X^n, Y^n)) が (P_{XY}) に従うためです。 * 誤りが発生するのは、送信されたメッセージ (m) に対応するペア ((x^n(m), y^n)) が共同典型集合に含まれないか、または (m \ne m') である他のコードワード (x^n(m')) と受け取った (y^n) のペア ((x^n(m'), y^n)) も共同典型集合に含まれてしまう場合です。 * 後者の誤り（偽警報）の確率を評価する際に、共同典型集合のサイズに関する性質（性質2）と、独立性を仮定した偽の共同典型集合の確率が小さいこと（性質3）が使われます。もし (x^n(m')) が (y^n) と独立に生成されたと仮定する（実際、(x^n(m')) はランダムに選ばれており、特定の (y^n) とは独立と見なせる）ならば、そのペア ((x^n(m'), y^n)) が共同典型集合に含まれる確率は、おおよそ (2^{-n I(X;Y)}) と評価できます。ここで (I(X;Y) = H(X) + H(Y) - H(X,Y)) です。 * メッセージが (M = 2^{nR}) 個あるため、任意の特定の (m' \ne m) に対して偽警報が発生する確率は (2^{-n I(X;Y)}) 程度です。ユニオンバウンドを用いると、どれか一つ以上の (m' \ne m) で偽警報が発生する確率は、およそ (M \times 2^{-n I(X;Y)} = 2^{nR} \times 2^{-n I(X;Y)} = 2^{-n(I(X;Y)-R)}) となります。したがって、レート (R < I(X;Y)) であれば、この確率は (n) が大きくなるにつれて指数関数的にゼロに近づきます。

この共同典型集合を使った復号戦略は、「ジョイント典型性復号 (Joint Typicality Decoding)」と呼ばれ、ランダム符号化と組み合わされることで、チャネル容量の達成可能性証明の基礎となります。

ソース符号化定理（率歪み理論）への応用

共同典型集合の概念は、損失のあるデータ圧縮の限界を定める率歪み理論 (Rate-Distortion Theory) においても中心的な役割を果たします。情報源 (X) を、ある歪み尺度 (d(x, \hat{x})) の下で、レート (R) で圧縮・復元する問題を考えます。率歪み関数 (R(D)) は、許容される平均歪みが (D) 以下であるために必要な最小レートを示します。

率歪み関数の導出や符号化定理の証明において、共同典型集合 (A_{\epsilon}^{(n)}(P_{X\hat{X}})) が用いられます。ここで (P_{X\hat{X}}) は、情報源 (X) と復元された情報 (\hat{X}) の間の結合分布であり、許容歪み条件 (E[d(X, \hat{X})] \le D) を満たすものです。特に、レート (R > I(X;\hat{X})) で符号化が可能であることを示す際に、情報源シーケンス (x^n) と、それに対応する復元シーケンス (\hat{x}^n) のペア ((x^n, \hat{x}^n)) が共同典型集合に含まれる確率が利用されます。

シャノンはこれらの証明において、確率論的な集合のサイズとその確率質量が、エントロピーや結合エントロピーによって特徴づけられることを巧みに利用しました。共同典型集合は、この確率論的な構造を形式化し、情報理論の基本限界が漸近的に達成可能であることを示すための強力な数学的枠組みを提供しています。

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

共同典型集合のアイデアは、シャノンが1948年の論文でチャネル容量の証明に用いた「典型的集合」の概念を、入力と出力のペアに拡張する形で自然に生まれました。シャノン自身が「共同典型集合」という特定の用語を用いたわけではないかもしれませんが、彼の証明における確率的な集合の扱いやサイズの評価は、この概念の基礎を築いています。

その後、CoverとThomasによる標準的な教科書『Elements of Information Theory』などで、AEPと共に共同典型集合が情報理論の基礎概念として明確に定義され、体系的に用いられるようになりました。これは、シャノンの原論文の直感的で工学的な記述を、より厳密な数学的枠組みの上に再構築する過程で重要視された概念です。

現代の情報科学において、共同典型集合は単に変遷的な証明ツールに留まらず、多変数情報理論、ネットワーク情報理論（例：分散情報源符号化、多重アクセスチャネル）、機械学習（例：情報ボトルネック原理）、統計的推論など、幅広い分野でその概念が応用されています。情報源間の依存関係や、入力と出力間の関連性を確率的なシーケンスの集合の性質として捉えるアプローチは、複雑な情報システムを解析する上での基本的な考え方となっています。

例えば、多端子情報理論では、複数の情報源や複数の送信機・受信機が登場しますが、そこでの容量や限界を議論する際に、複数のシーケンスのタプルに対する共同典型性の概念が拡張されて用いられます。これは、システムの全体的な情報量を結合エントロピーとして捉え、その統計的な構造を共同典型集合として表現することの有用性を示しています。

結論

共同典型集合は、シャノンの情報理論におけるAEPの多変数版として位置づけられる、極めて重要な概念です。これは、独立同分布な確率変数から生成される複数のシーケンスが同時に示す統計的な典型性を捉えるものであり、その定義と性質は、情報量のエントロピーによる定量化に基づいています。

特に、チャネル容量定理や率歪み理論といった情報理論の基本限界を示す証明において、共同典型集合は不可欠なツールとして機能します。ランダム符号化と組み合わせたジョイント典型性復号戦略は、容量達成可能性の証明をエレガントに行うことを可能にしました。

共同典型集合の概念は、シャノンの時代から現代に至るまで、情報理論および関連分野の研究の基礎を支え続けています。複雑な情報システムにおける確率的な依存関係や情報フローを解析する上で、この概念の深い理解は不可欠であり、今後の研究においても引き続き重要な役割を担うと考えられます。

この概念の更なる詳細や証明の厳密な追跡は、シャノンの原論文に加え、標準的な情報理論の教科書を参照することをお勧めいたします。特に、CoverとThomasの『Elements of Information Theory』では、共同典型集合の定義と性質が丁寧に解説されています。