Type of set in information theory
情報理論 において 、 典型集合とは、 確率が 2の元分布の エントロピー の負の乗に近い 系列の集合である。この集合の全 確率が1に近いことは、 大数の法則の 一種である 漸近的等分配性 （AEP）の帰結である 。典型性の概念は、系列の確率のみに関係し、系列そのものには関係しない。
これは 、データを圧縮するための理論的な手段を提供し、平均して nH ( X ) ビットを使用して任意のシーケンス X n を表すことができるため、圧縮 理論で非常に役立ちます。したがって、ソースからの情報の尺度としてエントロピーを使用することが正当化されます。
AEP は、 定常エルゴード過程 の大規模なクラスに対しても証明することができ、より一般的なケースで典型的なセットを定義することができます。
さらに、典型集合の概念は、通信システムにおけるデータ伝送と誤り訂正の限界を理解する上で基礎となります。典型系列の特性を活用することで、シャノンの 情報源符号化定理 や 通信路符号化定理 といった効率的な符号化方式が開発され、ノイズの多い通信路においてもほぼ最適なデータ圧縮と信頼性の高い伝送が可能になります。
（弱）典型的シーケンス（弱典型性、エントロピー典型性） 有限アルファベット上で定義された 独立同一分布確率変数 (IID) X から シーケンス x 1 , ..., x n が抽出された場合、典型的なセット A ε ( n ) ( n ) は次の条件を満たすシーケンスとして定義されます。 X {\displaystyle {\mathcal {X}}} ∈ X {\displaystyle \in {\mathcal {X}}}
2 − n ( H ( X ) + ε ) ⩽ p ( x 1 , x 2 , … , x n ) ⩽ 2 − n ( H ( X ) − ε ) {\displaystyle 2^{-n(H(X)+\varepsilon )}\leqslant p(x_{1},x_{2},\dots ,x_{n})\leqslant 2^{-n(H(X)-\varepsilon )}} どこ
H ( X ) = − ∑ x ∈ X p ( x ) log 2 p ( x ) {\displaystyle H(X)=-\sum _{x\in {\mathcal {X}}}p(x)\log _{2}p(x)} はX の情報エントロピーである 。上記の確率は2 n ε の係数以内であればよい。 すべての辺の 対数をとり、 -n で割ると、この定義は次のように等価に述べられる。
H ( X ) − ε ≤ − 1 n log 2 p ( x 1 , x 2 , … , x n ) ≤ H ( X ) + ε . {\displaystyle H(X)-\varepsilon \leq -{\frac {1}{n}}\log _{2}p(x_{1},x_{2},\ldots ,x_{n})\leq H(X)+\varepsilon .} iidシーケンスの場合、
p ( x 1 , x 2 , … , x n ) = ∏ i = 1 n p ( x i ) , {\displaystyle p(x_{1},x_{2},\ldots ,x_{n})=\prod _{i=1}^{n}p(x_{i}),} さらに
H ( X ) − ε ≤ − 1 n ∑ i = 1 n log 2 p ( x i ) ≤ H ( X ) + ε . {\displaystyle H(X)-\varepsilon \leq -{\frac {1}{n}}\sum _{i=1}^{n}\log _{2}p(x_{i})\leq H(X)+\varepsilon .} 大数の法則によれば、十分に大きな nに対して
− 1 n ∑ i = 1 n log 2 p ( x i ) → H ( X ) . {\displaystyle -{\frac {1}{n}}\sum _{i=1}^{n}\log _{2}p(x_{i})\rightarrow H(X).}
プロパティ 典型集合の本質的な特徴は、分布 Xから n 個の独立したランダムサンプルを多数抽出した場合 、結果として得られるシーケンス ( x 1 , x 2 , ..., x n ) は、典型集合がすべての可能なシーケンスのごく一部しか含まないにもかかわらず、典型集合のメンバーである可能性が非常に高いことです。正式には、任意の が与えられた場合、 次のように n を 選択できます。 ε > 0 {\displaystyle \varepsilon >0}
X (n)から A ε ( n ) までのシーケンスが 抽出される確率は 1 − ε より大きい 、すなわち P r [ x ( n ) ∈ A ϵ ( n ) ] ≥ 1 − ε {\displaystyle Pr[x^{(n)}\in A_{\epsilon }^{(n)}]\geq 1-\varepsilon } | A ε ( n ) | ⩽ 2 n ( H ( X ) + ε ) {\displaystyle \left|{A_{\varepsilon }}^{(n)}\right|\leqslant 2^{n(H(X)+\varepsilon )}} | A ε ( n ) | ⩾ ( 1 − ε ) 2 n ( H ( X ) − ε ) {\displaystyle \left|{A_{\varepsilon }}^{(n)}\right|\geqslant (1-\varepsilon )2^{n(H(X)-\varepsilon )}} 分布が 均一でない場合、典型的なシーケンスの割合は X {\displaystyle {\mathcal {X}}} | A ϵ ( n ) | | X ( n ) | ≡ 2 n H ( X ) 2 n log 2 | X | = 2 − n ( log 2 | X | − H ( X ) ) → 0 {\displaystyle {\frac {|A_{\epsilon }^{(n)}|}{|{\mathcal {X}}^{(n)}|}}\equiv {\frac {2^{nH(X)}}{2^{n\log _{2}|{\mathcal {X}}|}}}=2^{-n(\log _{2}|{\mathcal {X}}|-H(X))}\rightarrow 0} n が 非常に大きくなるにつれて、 の 基数 に なります 。 H ( X ) < log 2 | X | , {\displaystyle H(X)<\log _{2}|{\mathcal {X}}|,} | X | {\displaystyle |{\mathcal {X}}|} X {\displaystyle {\mathcal {X}}} AEPを伴う一般 確率過程 { X ( t )}の場合、（弱）典型集合は同様に定義することができ、 p (x1, x2 , ... , xn ) を p (x0τ)（つまり、時間間隔[0,τ]に限定されたサンプルの確率）に置き換えればよい 。n は 時間 間隔 における 過程 の 自由 度 、 H ( X ) は エントロピー 率 である。過程が連続値をとる場合は、代わりに 微分エントロピー が用いられる。
例 直感に反して、最も可能性の高いシーケンスは、典型的集合のメンバーではないことがよくあります。例えば、 Xが p (0)=0.1、 p (1)=0.9 の iid ベルヌーイ確率変数であるとします。n 回の 独立試行において、 p (1)> p (0)であるため、最も可能性の高い結果シーケンスは、すべて1のシーケンス(1,1,...,1)です。ここで、 X のエントロピーは H ( X )=0.469 ですが、
− 1 n log 2 p ( x ( n ) = ( 1 , 1 , … , 1 ) ) = − 1 n log 2 ( 0.9 n ) = 0.152 {\displaystyle -{\frac {1}{n}}\log _{2}p\left(x^{(n)}=(1,1,\ldots ,1)\right)=-{\frac {1}{n}}\log _{2}(0.9^{n})=0.152} したがって、このシーケンスは、 n の値をどれだけ大きくしても、その平均対数確率がランダム変数 X のエントロピーに任意に近づくことができないため、典型的なセットには含まれません 。
ベルヌーイ確率変数の場合、典型的な集合は、 n回の 独立試行における0と1の平均個数を持つ系列から構成される。これは簡単に証明できる。p (1) = p かつ p(0) = 1-p とすれば、 m個の1を持つ n回 の試行において 、
− 1 n log 2 p ( x ( n ) ) = − 1 n log 2 p m ( 1 − p ) n − m = − m n log 2 p − ( n − m n ) log 2 ( 1 − p ) . {\displaystyle -{\frac {1}{n}}\log _{2}p(x^{(n)})=-{\frac {1}{n}}\log _{2}p^{m}(1-p)^{n-m}=-{\frac {m}{n}}\log _{2}p-\left({\frac {n-m}{n}}\right)\log _{2}(1-p).} ベルヌーイ試行における1の平均個数は m = np である。したがって、
− 1 n log 2 p ( x ( n ) ) = − p log 2 p − ( 1 − p ) log 2 ( 1 − p ) = H ( X ) . {\displaystyle -{\frac {1}{n}}\log _{2}p(x^{(n)})=-p\log _{2}p-(1-p)\log _{2}(1-p)=H(X).} この例において、 n = 10 の場合、典型集合は 、 シーケンス全体に 0 が 1 つ含まれるすべてのシーケンスから構成されます。p (0) = p (1) = 0.5 の場合、すべての可能なバイナリシーケンスが典型集合に属します。
強い典型的シーケンス（強い典型性、文字の典型性） 有限または無限アルファベット上で定義された特定の結合分布から シーケンス x 1 , ..., x n が抽出された場合、強い典型セット A ε,strong ( n ) は、次を満たすシーケンスの集合として定義されます。 X {\displaystyle {\mathcal {X}}} ∈ X {\displaystyle \in {\mathcal {X}}}
| N ( x i ) n − p ( x i ) | < ε ‖ X ‖ . {\displaystyle \left|{\frac {N(x_{i})}{n}}-p(x_{i})\right|<{\frac {\varepsilon }{\|{\mathcal {X}}\|}}.} ここで 、これはシーケンス内の特定のシンボルの出現回数です。 N ( x i ) {\displaystyle {N(x_{i})}}
強典型的系列は弱典型的（異なる定数 ε を持つ）であることも示されており、これがこの名前の由来です。しかし、これら2つの形式は同等ではありません。記憶のない通信路の定理を証明する際には、強典型性の方が扱いやすい場合が多いです。しかし、定義から明らかなように、この形式の典型性は有限台を持つ確率変数に対してのみ定義されます。
共同で典型的なシーケンス 2つのシーケンス とが 共時的にε-典型的であるとは、そのペアが 共時分布に関してε-典型的であり 、かつ、との両方 が それぞれの周辺分布とに関してε-典型的である場合に 言う 。このようなシーケンスのペア全体の集合 は と表記される 。共時的にε-典型的な n 組シーケンスも同様に定義される。 x n {\displaystyle x^{n}} y n {\displaystyle y^{n}} ( x n , y n ) {\displaystyle (x^{n},y^{n})} p ( x n , y n ) = ∏ i = 1 n p ( x i , y i ) {\displaystyle p(x^{n},y^{n})=\prod _{i=1}^{n}p(x_{i},y_{i})} x n {\displaystyle x^{n}} y n {\displaystyle y^{n}} p ( x n ) {\displaystyle p(x^{n})} p ( y n ) {\displaystyle p(y^{n})} ( x n , y n ) {\displaystyle (x^{n},y^{n})} A ε n ( X , Y ) {\displaystyle A_{\varepsilon }^{n}(X,Y)}
と を、 同じ周辺分布とを持つ2つの独立した確率変数列とします 。 このとき、任意の ε>0 および十分に大きい n に対して、共同典型列は以下の性質を満たします。 X ~ n {\displaystyle {\tilde {X}}^{n}} Y ~ n {\displaystyle {\tilde {Y}}^{n}} p ( x n ) {\displaystyle p(x^{n})} p ( y n ) {\displaystyle p(y^{n})}
P [ ( X n , Y n ) ∈ A ε n ( X , Y ) ] ⩾ 1 − ϵ {\displaystyle P\left[(X^{n},Y^{n})\in A_{\varepsilon }^{n}(X,Y)\right]\geqslant 1-\epsilon } | A ε n ( X , Y ) | ⩽ 2 n ( H ( X , Y ) + ϵ ) {\displaystyle \left|A_{\varepsilon }^{n}(X,Y)\right|\leqslant 2^{n(H(X,Y)+\epsilon )}} | A ε n ( X , Y ) | ⩾ ( 1 − ϵ ) 2 n ( H ( X , Y ) − ϵ ) {\displaystyle \left|A_{\varepsilon }^{n}(X,Y)\right|\geqslant (1-\epsilon )2^{n(H(X,Y)-\epsilon )}} P [ ( X ~ n , Y ~ n ) ∈ A ε n ( X , Y ) ] ⩽ 2 − n ( I ( X ; Y ) − 3 ϵ ) {\displaystyle P\left[({\tilde {X}}^{n},{\tilde {Y}}^{n})\in A_{\varepsilon }^{n}(X,Y)\right]\leqslant 2^{-n(I(X;Y)-3\epsilon )}} P [ ( X ~ n , Y ~ n ) ∈ A ε n ( X , Y ) ] ⩾ ( 1 − ϵ ) 2 − n ( I ( X ; Y ) + 3 ϵ ) {\displaystyle P\left[({\tilde {X}}^{n},{\tilde {Y}}^{n})\in A_{\varepsilon }^{n}(X,Y)\right]\geqslant (1-\epsilon )2^{-n(I(X;Y)+3\epsilon )}}
典型性の応用
典型的なセットエンコーディング 情報理論 において 、典型セット符号化は、確率的情報源の典型セット内のシーケンスのみを固定長ブロック符号で符号化する。典型セットのサイズは約 2 nH(X) であるため、符号化に必要なビット数は nH(X) のみであり、同時に符号化エラーの可能性はεに制限されることが保証される。漸近的には、AEPによってロスレスとなり、情報源のエントロピーレートに等しい最小レートを達成する。
典型的なセットデコード 情報理論 では 、典型セット復号法はランダム符号化と組み合わせて使用され、送信されたメッセージが観測と共同でε典型的である符号語を持つものとして推定されます。すなわち、
w ^ = w ⟺ ( ∃ w ) ( ( x 1 n ( w ) , y 1 n ) ∈ A ε n ( X , Y ) ) {\displaystyle {\hat {w}}=w\iff (\exists w)((x_{1}^{n}(w),y_{1}^{n})\in A_{\varepsilon }^{n}(X,Y))} ここで、 はそれぞれメッセージ推定値、メッセージのコードワード 、および観測値です。 は結合分布に対して定義されます。 ここで 、はチャネル統計を特徴付ける遷移確率であり、は ランダム コードブック内のコードワードを生成するために使用される入力分布です。 w ^ , x 1 n ( w ) , y 1 n {\displaystyle {\hat {w}},x_{1}^{n}(w),y_{1}^{n}} w {\displaystyle w} A ε n ( X , Y ) {\displaystyle A_{\varepsilon }^{n}(X,Y)} p ( x 1 n ) p ( y 1 n | x 1 n ) {\displaystyle p(x_{1}^{n})p(y_{1}^{n}|x_{1}^{n})} p ( y 1 n | x 1 n ) {\displaystyle p(y_{1}^{n}|x_{1}^{n})} p ( x 1 n ) {\displaystyle p(x_{1}^{n})}
普遍的帰無仮説検定
ユニバーサルチャネルコード
参照
参考文献 
![{\displaystyle Pr[x^{(n)}\in A_{\epsilon }^{(n)}]\geq 1-\varepsilon }](https://wikimedia.org/api/rest_v1/media/math/render/svg/03927f77109e65324ebafd153a67997d3d3cca1c)
![{\displaystyle P\left[(X^{n},Y^{n})\in A_{\varepsilon }^{n}(X,Y)\right]\geqslant 1-\epsilon }](https://wikimedia.org/api/rest_v1/media/math/render/svg/fbd78d1de6eaea1fba3d6b10d3b6a42610044cf2)
![{\displaystyle P\left[({\tilde {X}}^{n},{\tilde {Y}}^{n})\in A_{\varepsilon }^{n}(X,Y)\right]\leqslant 2^{-n(I(X;Y)-3\epsilon )}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d6fe239595a890fa7667f66db91e0054e20fea72)
![{\displaystyle P\left[({\tilde {X}}^{n},{\tilde {Y}}^{n})\in A_{\varepsilon }^{n}(X,Y)\right]\geqslant (1-\epsilon )2^{-n(I(X;Y)+3\epsilon )}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8bec667f9640bfc1b35a3aee260fd53d3294784b)
