典型的なセット

Typical_set
情報理論、典型的なセットは、シーケンスのセットである確率近くの負乗〜2であり、エントロピそのソース分布。このセットの合計確率が1に近いのは、大数の法則の一種である漸近的等分配特性（AEP）の結果です。典型性の概念は、シーケンスの確率にのみ関係し、実際のシーケンス自体には関係しません。
これは、データを圧縮するための理論的手段を提供し、平均してnH（X）ビットを使用して任意のシーケンスX nを表すことができるため、圧縮理論で非常に役立ちます。したがって、ソース。
AEPは、定常エルゴディックプロセスの大規模なクラスでも証明できるため、より一般的なケースで一般的なセットを定義できます。

コンテンツ
1 （弱い）典型的なシーケンス（弱い典型性、エントロピーの典型性）
1.1 プロパティ 1.2 例
2 非常に典型的なシーケンス（強い典型性、文字の典型性）
3 共同で典型的なシーケンス
4 典型性の応用
4.1 典型的なセットエンコーディング 4.2 典型的なセットのデコード 4.3 ユニバーサルヌル仮説検定 4.4 ユニバーサルチャンネルコード
5 も参照してください
6 参考文献

（弱い）典型的なシーケンス（弱い典型性、エントロピーの典型性）
シーケンス場合、X 1、…、  X nがから引き出されIID分布 X有限アルファベット上に定義され {{ mathcal {X}}}

 、次に典型的なセット、ε（N）
∈ { in { mathcal {X}}}

 （n）は、以下を満たすシーケンスとして定義されます。 2 − （（ （（ ）。+ ε ）。 ⩽ （（ 1
、 2 …
、 ）。⩽ 2
− （（ （（ ）。− ε ）。 {2 ^ {-n（H（X）+ varepsilon）} leqslant p（x_ {1}、x_ {2}、 dots、x_ {n}） leqslant 2 ^ {-n（H（ X）- varepsilon）}}
  どこ （（ ）。= − ∑ y ∈（（ y ）。 ログ
2 （（ y ）。 {H（X）=- sum _ {y in { mathcal {X}}} p（y） log _ {2} p（y）}
  Xの情報エントロピーです 。必要以上の確率はわずか2倍以内であるn個の ε。すべての辺で対数を取り、-nで割ると、この定義は次のように同等に表すことができます。 （（ ）。− ε ≤ −
1 ログ
2 （（ 1
、 2 …
、 ）。
≤ （（ ）。 + ε {H（X）- varepsilon leq-{ frac {1} {n}} log _ {2} p（x_ {1}、x_ {2}、 ldots、x_ {n}） leq H（X）+ varepsilon。}
  iidシーケンスの場合、 （（ 1
、 2 …
、 ）。= ∏
I = 1 （（ 私
）。 {p（x_ {1}、x_ {2}、 ldots、x_ {n}）= prod _ {i = 1} ^ {n} p（x_ {i}）、}
  私たちはさらに持っています （（ ）。− ε ≤ −
1 ∑
I = 1 ログ
2 （（ 私 ）。 ≤ （（ ）。 + ε {H（X）- varepsilon leq-{ frac {1} {n}} sum _ {i = 1} ^ {n} log _ {2} p（x_ {i}） leq H（X）+ varepsilon。}
  大数の法則により、nが十分に大きい場合 − 1 ∑
I = 1 ログ
2 （（ 私 ）。 （（ ）。 { displaystyle-{ frac {1} {n}} sum _ {i = 1} ^ {n} log _ {2} p（x_ {i}） rightarrow H（X）。}

 

プロパティ
典型的な組の本質的な特徴は、そのあるものが多数を描画する場合、N分布から独立ランダムサンプルをX、得られた配列（X 1、  X 2、…、  xはn個）可能性が非常に高いメンバーであります典型的なセットがすべての可能なシーケンスのごく一部しか含まない場合でも、典型的なセットの。正式には、 ε >> 0 { varepsilon> 0}
0″”>
 、次のようにnを選択できます。
シーケンスの確率X （N）から引き出されているA ε（N） 1より大きい-  ε、すなわち [ （（ ）。
∈ ϵ（（ ）。] ≥ 1 − ε
{Pr [x ^ {（n）} in A _ { epsilon} ^ {（n）}] geq 1- varepsilon}
  | ε（（ ）。 | ⩽
2 （（ （（ ）。+ ε ）。 { left | {A _ { varepsilon}} ^ {（n）} right | leqslant 2 ^ {n（H（X）+ varepsilon）}}
  | ε（（ ）。 | ⩾（（ 1− ε ）。 2 （（ （（ ）。− ε ）。 { left | {A _ { varepsilon}} ^ {（n）} right | geqslant（1- varepsilon）2 ^ {n（H（X）- varepsilon）}}
  配布が {{ mathcal {X}}}

  が均一ではない場合、典型的なシーケンスの割合は次のようになります。
| ϵ（（ ）。 | | （（ ）。| ≡
2 （（ ）。
2 ログ 2 | | = 2
− （（ ログ 2 | |
− （（ ）。
）。 0 {{ 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があるため、非常に大きくなります （（ ）。< グ 2
| | {H（X）< log _ {2} | { mathcal {X}} |、}
  どこ
| |
{| { mathcal {X}} |}
 の カーディナリティは{{ mathcal {X}}}
 。
一般的な確率過程{ためのX（T AEP有する）}、（弱）の典型的なセットを用いて同様に定義することができ、P（X 1、  xは2、…、  xはN）で置き換えP（X 0 τ）（すなわちサンプルの確率は、時間間隔[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 ログ
2 （（ （（ ）。 = （（ 1 1 … 1 ）。 ）。= − 1 ログ 2 （（ 0.9 ）。= 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 ログ
2 （（ （（ ）。
）。= −
1 ログ
2 （（ 1
− ）。 − =
− ログ
2 −（（ − ）。
ログ 2 （（ 1
− ）。 { displaystyle-{ frac {1} {n}} log _ {2} p（x ^ {（n）}）=-{ frac {1} {n}} log _ {2} p ^ {m}（1-p）^ {nm} =-{ frac {m} {n}} log _ {2} p- left（{ frac {nm} {n}} right） log _ {2}（1-p）。}
  一連のベルヌーイ試行における1の平均数はm = npです。したがって、 − 1 ログ
2 （（ （（ ）。
）。 = − ログ
2 −（（ 1
− ）。
ログ 2 （（ 1
− ）。= （（ ）。 { displaystyle-{ frac {1} {n}} log _ {2} p（x ^ {（n）}）=-p log _ {2} p-（1-p） log _ { 2}（1-p）= H（X）。}
  この例では、n = 10の場合、一般的なセットは、シーケンス全体で1つの0を持つすべてのシーケンスで構成されます。ケースでは、P（0）= P（1）= 0.5、その後、すべての可能なバイナリ配列は、典型的なセットに属しています。

非常に典型的なシーケンス（強い典型性、文字の典型性）
シーケンス場合、X 1、…、X nが有限または無限のアルファベットの上に定義されたいくつかの指定された関節の分布から引き出されます {{ mathcal {X}}}

 、次に強く典型的なセット、ε、強力（N）
∈ { in { mathcal {X}}}

  を満たすシーケンスのセットとして定義されます
| （（ 私）。− （（NS
私）。 | < ε ‖ ‖ { left | { frac {N（x_ {i}）} {n}}-p（x_ {i}） right | <{ frac { varepsilon} { | { mathcal {X} } |}}。}
  どこ （（ 私 ）。 {{N（x_ {i}）}}

  シーケンス内の特定のシンボルの出現回数です。
非常に典型的なシーケンスも弱く典型的である（定数εが異なる）ことを示すことができるため、この名前が付けられています。ただし、2つの形式は同等ではありません。多くの場合、強い典型性は、メモリレスチャネルの定理を証明する際に扱いやすくなります。ただし、定義から明らかなように、この形式の典型性は、有限のサポートを持つ確率変数に対してのみ定義されます。

共同で典型的なシーケンス
2つのシーケンス {x ^ {n}}

  と
y {y ^ {n}}

  ペアが一緒にε-典型的である場合（（ NS、 y NS）。
{ displaystyle（x ^ {n}、y ^ {n}）}

  は、同時分布に関して典型的なεです。 （（ NS、 y NS）。= ∏ I =
1（（ I y
私）。
{p（x ^ {n}、y ^ {n}）= prod _ {i = 1} ^ {n} p（x_ {i}、y_ {i}）}

  と両方 {x ^ {n}}

  と
y {y ^ {n}}

  周辺分布に関してはε-典型的です （（ NS）。
{p（x ^ {n}）}

  と （（ y
NS）。
{p（y ^ {n}）}

 。そのようなシーケンスのすべてのペアのセット（（ NS、 y NS）。
{ displaystyle（x ^ {n}、y ^ {n}）}

  で示されます ε（（ 、 Y ）。
{A _ { varepsilon} ^ {n}（X、Y）}

 。共同でε-典型的なnタプルシーケンスも同様に定義されます。
させて 〜 {{ tilde {X}} ^ {n}}

  と Y 〜 {{ tilde {Y}} ^ {n}}

  同じ周辺分布を持つ確率変数の2つの独立したシーケンスである （（ NS）。
{p（x ^ {n}）}

  と （（ y
NS）。
{p（y ^ {n}）}

 。次に、任意のε> 0の場合、十分に大きいnの場合、共同で典型的なシーケンスは次の特性を満たします。 [ （（NS、 Y NS）。
∈ ε（（ 、 Y ）。
] 1− ϵ
{P left [（X ^ {n}、Y ^ {n}） in A _ { varepsilon} ^ {n}（X、Y） right] geqslant 1- epsilon}
  | ε（（ 、 Y ）。 | ⩽
2 （（ （（ 、 Y ）。+ ϵ ）。 { left | A _ { varepsilon} ^ {n}（X、Y） right | leqslant 2 ^ {n（H（X、Y）+ epsilon）}}
  | ε（（ 、 Y ）。 | ⩾（（ 1− ϵ ）。 2 （（ （（ 、 Y ）。− ϵ ）。 { left | A _ { varepsilon} ^ {n}（X、Y） right | geqslant（1- epsilon）2 ^ {n（H（X、Y）- epsilon）}}

  [ （（ 〜、Y 〜
NS）。
∈ ε（（ 、 Y ）。 ] 2 − （（ 私（（ ; Y ）。− 3 ϵ ）。 {P left [（{ tilde {X}} ^ {n}、{ tilde {Y}} ^ {n}） in A _ { varepsilon} ^ {n}（X、Y） right ] leqslant 2 ^ {-n（I（X; Y）-3 epsilon）}}

  [ （（ 〜、Y 〜
NS）。
∈ ε（（ 、 Y ）。 ] ⩾（（ 1− ϵ
）。 2 − （（ 私（（ ; Y ）。+ 3 ϵ ）。 {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によって無損失であり、ソースのエントロピーレートに等しい最小レートを達成します。
あなたはそれに追加することによって助けることができます

典型的なセットのデコード
情報理論、一般的なセットのデコーディングはと共に使用されるランダム符号化共同観察とε-典型的であるコードワードを有するものとして送信されたメッセージを推定します。NSw ^ = w ⟺（（ ∃ w ）。（（ （（ 1 （（ w
）。 y
1 ）。
∈ ε （（ 、 Y ）。 ）。 {{ hat {w}} = w iff（ exists w）（（x_ {1} ^ {n}（w）、y_ {1} ^ {n}） in A _ { varepsilon} ^ {n}（X、Y））}
  どこw
^ 、 1（（ w
）。 y
1 {{ hat {w}}、x_ {1} ^ {n}（w）、y_ {1} ^ {n}}

  メッセージの見積もり、メッセージのコードワードです w {w}

  それぞれと観察。 ε（（ 、 Y ）。
{A _ { varepsilon} ^ {n}（X、Y）}

  同時分布に関して定義されます （（ 1
NS）。 （（ y
1 | 1
NS）。
{p（x_ {1} ^ {n}）p（y_ {1} ^ {n} | x_ {1} ^ {n}）}

  どこ （（ y
1 | 1
NS）。
{p（y_ {1} ^ {n} | x_ {1} ^ {n}）}

  チャネル統計を特徴付ける遷移確率であり、 （（ 1
NS）。
{p（x_ {1} ^ {n}）}

  ランダムコードブックでコードワードを生成するために使用される入力分布です。
あなたはそれに追加することによって助けることができます

ユニバーサルヌル仮説検定
あなたはそれに追加することによって助けることができます

ユニバーサルチャンネルコード
あなたはそれに追加することによって助けることができます
参照：
アルゴリズムの複雑さの理論

も参照してください
漸近的等分配特性
ソースコーディング定理
シャノンの通信路コーディング定理

参考文献
CEシャノン、「通信の数学的理論」、ベルシステムテクニカルジャーナル、vol。27、pp。379–423、623-656、1948年7月、10月
表紙、トーマスM.（2006）。「第3章：漸近的等分配特性、第5章：データ圧縮、第8章：チャネル容量」。情報理論の要素。ジョンワイリー＆サンズ。ISBN 0-471-24195-4。
デビッドJCマッケイ。情報理論、推論、および学習アルゴリズムケンブリッジ：ケンブリッジ大学出版、2003年
ISBN 0-521-64298-1 “