漸近等分割性

情報理論において、漸近等分割性（AEP ）は、確率的情報源の出力サンプルの一般的な性質である。これは、データ圧縮理論において用いられる典型集合の概念の基礎となる。

大まかに言えば、この定理は、ランダムなプロセスによって生成される可能性のある一連の結果は多数あるが、実際に生成される結果は、すべて実際に実現される可能性がほぼ同じである、ゆるく定義された結果の集合から生成される可能性が最も高いと述べています (これは、大数の法則とエルゴード理論の結果です)。この集合内のどの結果よりも確率が高い個別の結果もありますが、集合内の結果の数が膨大であるため、結果が集合から生成されることがほぼ保証されます。この特性を直感的に理解する 1 つの方法は、平均からの大きな偏差の確率はサンプル数とともに指数的に減少するという、クラメールの大偏差定理を使用することです。このような結果は、大偏差理論で研究されています。直感的には、等分割に違反するのは大きな偏差ですが、これは起こりそうにありません。

疑似乱数生成の分野において、品質が未確定で、出力系列が何らかの統計的基準によって典型集合から大きく外れている候補生成器は、十分にランダムではないとして排除される。このように、典型集合の定義は曖昧であるものの、十分な典型性に関する実用的な概念が生じる。

意味

確率空間上の離散時間定常エルゴード確率過程が与えられている場合、漸近的等分割性は、ほぼ確実に となる主張です。 ここで、 または は単に のエントロピー率を表し、これはエルゴード過程を含むすべての離散時間定常過程に必ず存在します。漸近的等分割性は、シャノン・マクミラン・ブレイマンの定理における有限値（すなわち ）定常エルゴード確率過程についてはエルゴード理論を用いて、また任意のiid源については離散値の場合（は単にシンボルのエントロピー）と連続値の場合（は微分エントロピー）の両方で大数の法則を直接用いて証明されています。漸近的等分割性の定義は、典型的集合が十分に長い観測時間にわたって存在する特定のクラスの連続時間確率過程に拡張することもできます。収束はすべてのケースで ほぼ確実に証明されています。${\displaystyle X}$ ${\displaystyle (\Omega ,B,p)}$ $${\displaystyle -{\frac {1}{n}}\log p(X_{1},X_{2},\dots ,X_{n})\to H(X)\quad {\text{ as }}\quad n\to \infty }$$ ${\displaystyle H(X)}$ ${\displaystyle H}$ ${\displaystyle X}$ ${\displaystyle |\Omega |<\infty }$ ${\displaystyle H}$ ${\displaystyle H}$

離散時間IIDソース

アルファベット の値を取る可能性のあるiid 情報源が与えられているとすると、その時系列はエントロピーを持つ iid である。大数の弱法則は、エントロピーが^[1] の期待値に等しいことから、 確率 で収束する漸近等分配性を与える。${\displaystyle X}$ ${\displaystyle {\mathcal {X}}}$ ${\displaystyle X_{1},\ldots ,X_{n}}$ ${\displaystyle H(X)}$ $${\displaystyle \lim _{n\to \infty }\Pr \left[\left|-{\frac {1}{n}}\log p(X_{1},X_{2},\ldots ,X_{n})-H(X)\right|>\varepsilon \right]=0\qquad \forall \varepsilon >0.}$$ $${\displaystyle -{\frac {1}{n}}\log p(X_{1},X_{2},\ldots ,X_{n}).}$$

大数の強い法則は、より強いほぼ確実な収束を主張し、 L1の意味での収束はさらに強いことを主張する。$${\displaystyle \Pr \left[\lim _{n\to \infty }-{\frac {1}{n}}\log p(X_{1},X_{2},\ldots ,X_{n})=H(X)\right]=1.}$$ $${\displaystyle \mathbb {E} \left[\left|\lim _{n\to \infty }-{\frac {1}{n}}\log p(X_{1},X_{2},\ldots ,X_{n})-H(X)\right|\right]=0}$$

離散時間有限値定常エルゴード源

確率空間上で定義された離散時間定常エルゴード過程に対する有限値標本空間、すなわち を考える。クロード・シャノン、ブロックウェイ・マクミラン、レオ・ブレイマンによるシャノン・マクミラン・ブレイマン定理は、 L1の意味で収束することを述べている。^[2]チョン・カイライはこれを、エントロピー率が依然として有限である限り、可算無限集合において が値を取る可能性がある場合にまで一般化した。 ^[3]${\displaystyle \Omega }$ ${\displaystyle |\Omega |<\infty }$ ${\displaystyle X:=\{X_{n}\}}$ ${\displaystyle (\Omega ,B,p)}$ ${\displaystyle X}$

証明スケッチ^[3]

• xをある測定可能な集合とする。${\displaystyle x=X(A)}$ ${\displaystyle A\in B}$
• nとxによる結合確率を次のようにパラメータ化する。$${\displaystyle j(n,x):=p\left(x_{0}^{n-1}\right).}$$
• 条件付き確率をi、k、xでパラメータ化すると、$${\displaystyle c(i,k,x):=p\left(x_{i}\mid x_{i-k}^{i-1}\right).}$$
• 条件付き確率の極限をk → ∞として次のように表す。$${\displaystyle c(i,x):=p\left(x_{i}\mid x_{-\infty }^{i-1}\right).}$$
• エントロピー率の2つの概念が存在し、定常エルゴード過程Xを含む任意の定常過程に対して等しいことを論じよ。これをHと表記せよ。$${\displaystyle \lim _{n\to \infty }{\frac {1}{n}}\mathrm {E} [-\log j(n,X)]\quad {\text{and}}\quad \lim _{n\to \infty }\mathrm {E} [-\log c(n,n,X)]}$$
• i が時間インデックスであるはどちらも定常エルゴード過程であり、その標本平均はそれぞれおよびで示される値にほぼ確実に収束すると主張します。$${\displaystyle {\begin{aligned}c(i,k,X)&:=\left\{p\left(X_{i}\mid X_{i-k}^{i-1}\right)\right\}\\c(i,X)&:=\left\{p\left(X_{i}\mid X_{-\infty }^{i-1}\right)\right\}\end{aligned}}}$$ ${\displaystyle H^{k}}$ ${\displaystyle H^{\infty }}$
• 確率のk次のマルコフ近似を次のように定義する。${\displaystyle a(n,k,x)}$ $${\displaystyle a(n,k,x):=p\left(X_{0}^{k-1}\right)\prod _{i=k}^{n-1}p\left(X_{i}\mid X_{i-k}^{i-1}\right)=j(k,x)\prod _{i=k}^{n-1}c(i,k,x)}$$
• 有限値仮定から有限であると主張します。${\displaystyle a(n,k,X(\Omega ))}$
• の標本平均を用いて表し、それがほぼ確実にH ^kに収束することを示す。${\displaystyle -{\frac {1}{n}}\log a(n,k,X)}$ ${\displaystyle c(i,k,X)}$
• 確率尺度を定義する$${\displaystyle a(n,x):=p\left(x_{0}^{n-1}\mid x_{-\infty }^{-1}\right).}$$
• ^の標本平均で表し、それがほぼ確実にH∞に収束することを示します。${\displaystyle -{\frac {1}{n}}\log a(n,X)}$ ${\displaystyle c(i,X)}$
• プロセスの定常性を利用して、k → ∞であると主張してください。${\displaystyle H^{k}\searrow H}$
• レヴィのマルチンゲール収束定理と有限値仮定を用いて、 H = H ^∞を主張します。
• 前に議論したように有限であるものを示します。$${\displaystyle \mathrm {E} \left[{\frac {a(n,k,X)}{j(n,X)}}\right]=a(n,k,X(\Omega ))}$$
• 無限の過去を条件として期待値を繰り返すことで、それを示してください。$${\displaystyle \mathrm {E} \left[{\frac {j(n,X)}{a(n,X)}}\right]=1}$$ ${\displaystyle X_{-\infty }^{-1}}$
• マルコフの不等式と先ほど導出した期待値を使用して、それを示します。$${\displaystyle \forall \alpha \in \mathbb {R} \ :\ \Pr \left[{\frac {a(n,k,X)}{j(n,X)}}\geq \alpha \right]\leq {\frac {a(n,k,X(\Omega ))}{\alpha }}}$$
• 同様に、以下と等しいものを示しなさい。$${\displaystyle \forall \alpha \in \mathbb {R} \ :\ \Pr \left[{\frac {j(n,X)}{a(n,X)}}\geq \alpha \right]\leq {\frac {1}{\alpha }},}$$ $${\displaystyle \forall \alpha \in \mathbb {R} \ :\ \Pr \left[{\frac {1}{n}}\log {\frac {j(n,X)}{a(n,X)}}\geq {\frac {1}{n}}\log \alpha \right]\leq {\frac {1}{\alpha }}.}$$
• 任意のβ>1に対してα = n ^{βを設定し、}ボレル・カンテリの補題を適用することにより、のlimsupがほぼ確実に非正であることを示します。$${\displaystyle {\frac {1}{n}}\log {\frac {a(n,k,X)}{j(n,X)}}\quad {\text{and}}\quad {\frac {1}{n}}\log {\frac {j(n,X)}{a(n,X)}}}$$
• 前の結果の対数を分解して、liminf と limsup がそれぞれH ^∞とH ^kによってほぼ確実に下限と上限に制限されることを示します。$${\displaystyle -{\frac {1}{n}}\log j(n,X)}$$
• 上界と下界はk → ∞としてHに近づくことが前に示されていることを指摘して証明を完成させます。

独立シンボルを生成する非定常離散時間情報源

確率変数の定常性／エルゴード性／同一分布といった仮定は、漸近的等分配性が成立するために必須ではありません。実際、直感的に明らかなように、漸近的等分配性が成立するには、大数の法則の何らかの形が成立するだけで十分であり、これはかなり一般的なものです。しかしながら、その表現を適切に一般化し、条件を正確に定式化する必要があります。

独立なシンボルを生成する情報源を考えよう。その情報源は各時点において異なる出力統計量を持つ可能性があり、そのプロセスの統計量が完全に既知である。つまり、各時点におけるプロセスの周辺分布が既知である。結合分布は周辺分布の積に等しい。このとき、すべてのiに対して、あるM > 0に対して、以下の式が成り立つという条件（緩和可能）の下で、以下の式が成り立つ（AEP）： ここで ${\displaystyle \mathrm {Var} [\log p(X_{i})]<M}$ $${\displaystyle \lim _{n\to \infty }\Pr \left[\,\left|-{\frac {1}{n}}\log p(X_{1},X_{2},\ldots ,X_{n})-{\overline {H}}_{n}(X)\right|<\varepsilon \right]=1\qquad \forall \varepsilon >0}$$ $${\displaystyle {\overline {H}}_{n}(X)={\frac {1}{n}}H(X_{1},X_{2},\ldots ,X_{n})}$$

証拠

証明は、マルコフの不等式（ の 2 番目のモーメントに適用）の単純な適用から得られます。 ${\displaystyle \log(p(X_{i}))}$ $${\displaystyle {\begin{aligned}\Pr \left[\left|-{\frac {1}{n}}\log p(X_{1},X_{2},\ldots ,X_{n})-{\overline {H}}(X)\right|>\varepsilon \right]&\leq {\frac {1}{n^{2}\varepsilon ^{2}}}\mathrm {Var} \left[\sum _{i=1}^{n}\left(\log(p(X_{i})\right)^{2}\right]\\&\leq {\frac {M}{n\varepsilon ^{2}}}\to 0{\text{ as }}n\to \infty \end{aligned}}}$$

任意のモーメントがr > 1に対して一様に有界である場合（この場合もr番目のモーメントに適用されるマルコフの不等式により） 、証明が成立することは明らかです。QED${\displaystyle \mathrm {E} \left[|\log p(X_{i})|^{r}\right]}$

この条件は必須ではありませんが、非定常ランダムプロセスが与えられた場合、上記の方法を使用して漸近等分割特性が成り立つかどうかをテストすることは難しくないはずです。

アプリケーション

非定常離散時間独立プロセスの漸近的等分割特性は、（他の結果の中でも）非定常情報源（独立出力シンボルを持つ）の情報源符号化定理と、非定常メモリレスチャネルの ノイズチャネル符号化定理につながります。

測度論的形式

${\textstyle T}$ は確率空間上の測度保存写像である。 ${\textstyle \Omega }$

が の有限または可算な分割である場合、そのエントロピーはという規則に従います。 ${\textstyle P}$ ${\textstyle \Omega }$ ${\displaystyle H(P):=-\sum _{p\in P}\mu (p)\ln \mu (p)}$ ${\displaystyle 0\ln 0=0}$

有限エントロピーを持つパーティションのみを考慮します。 ${\textstyle H(P)<\infty }$

が の有限または可算な分割である場合、マップを反復して分割のシーケンスを構築します。ここでは最小の上限分割、つまりと の両方を細分化する最も細分化されていない分割です。をが入るの集合 と書きます。したがって、たとえば はの名前の -文字の最初の部分です。 ${\textstyle P}$ ${\textstyle \Omega }$ $${\displaystyle P^{(n)}:=P\vee T^{-1}P\vee \dots \vee T^{-(n-1)}P}$$ ${\textstyle P\vee Q}$ ${\textstyle P}$ ${\textstyle Q}$ $${\displaystyle P\vee Q:=\{p\cap q:p\in P,q\in Q\}}$$ ${\textstyle P(x)}$ ${\textstyle P}$ ${\textstyle x}$ ${\textstyle P^{(n)}(x)}$ ${\textstyle n}$ ${\textstyle (P,T)}$ ${\textstyle x}$

を（ナット単位の）パーティションに関する情報と書き、パーティション内のどの要素が に属するかが分かれば、 に関する情報を復元できます。同様に、パーティション の条件付き情報（パーティション を条件とする）は、に関するもので、コルモゴロフ・シナイエントロピーです。言い換えれば、定義により、期待値は収束します。SMB定理によれば、がエルゴードである場合、L1は収束します。^[4]${\textstyle I_{P}(x)}$ ${\textstyle x}$ ${\textstyle P}$ ${\textstyle x}$ $${\displaystyle I_{P}:=-\ln \mu (P(x))}$$ ${\textstyle P}$ ${\textstyle Q}$ ${\textstyle x}$ $${\displaystyle I_{P|Q}(x):=-\ln {\frac {P\vee Q(x)}{Q(x)}}}$$ ${\textstyle h_{T}(P)}$ $${\displaystyle h_{T}(P):=\lim _{n}{\frac {1}{n}}H(P^{(n)})=\lim _{n}E_{x\sim \mu }\left[{\frac {1}{n}}I_{P^{(n)}}(x)\right]}$$ ${\textstyle T}$

定理 (エルゴードの場合) —がエルゴードである場合、L1 で定数関数 に収束します。 ${\textstyle T}$ $${\displaystyle x\mapsto {\frac {1}{n}}I_{P^{(n)}}(x)}$$ ${\textstyle x\mapsto h_{T}(P)}$

言い換えると、$${\displaystyle E_{x\sim \mu }\left[\left|\lim _{n}{\frac {1}{n}}I_{P^{(n)}}(x)-h_{T}(P)\right|\right]=0}$$

特に、L1 収束は確率 1 でほぼ確実な収束を意味します。 $${\displaystyle h_{T}(P)=\lim _{n}{\frac {1}{n}}I_{P^{(n)}}(x)}$$

系 (エントロピー等分割特性) —、パーティションを「良い」部分と「悪い」部分の 2 つの部分に分割できます。 ${\textstyle \forall \epsilon >0,\exists N,\forall n\geq N}$ ${\textstyle \vee _{k=0}^{n-1}T^{-k}P}$ ${\textstyle G}$ ${\textstyle B}$

悪い部分は小さいです:$${\displaystyle \sum _{b\in B}\mu (b)<\epsilon }$$

良い部分はエントロピーに従ってほぼ均等に分割されます。$${\displaystyle \forall g\in G,\quad -{\frac {1}{n}}\ln \mu (g)\in h_{T}(P)\pm \epsilon }$$

が必ずしもエルゴード的でない場合、基礎となる確率空間は複数の部分集合に分割され、各部分集合は に関して不変となる。この場合、ある関数へのL1収束は依然として得られるが、その関数はもはや定数関数ではない。^[5]${\textstyle T}$ ${\textstyle T}$

定理 （一般の場合）-のすべての -不変測定可能部分集合によって生成されるシグマ代数を とすると、-は L1 で収束し、${\textstyle {\mathcal {I}}}$ ${\textstyle T}$ ${\textstyle \Omega }$ $${\displaystyle x\mapsto {\frac {1}{n}}I_{P^{(n)}}(x)}$$
$${\displaystyle x\mapsto E\left[\lim _{n}I_{P|\vee _{k=1}^{n}T^{-k}P}{\big |}\;{\mathcal {I}}\right]}$$

がエルゴード的である場合、は自明であり、したがって関数 は定数関数 に簡略化されます。これは定義により に等しく、命題により に 等しくなります。${\textstyle T}$ ${\textstyle {\mathcal {I}}}$ $${\displaystyle x\mapsto E\left[\lim _{n}I_{P|\vee _{k=1}^{n}T^{-k}P}{\big |}\;{\mathcal {I}}\right]}$$ ${\textstyle x\mapsto E\left[\lim _{n}I_{P|\vee _{k=1}^{n}T^{-k}P}\right]}$ ${\textstyle \lim _{n}H(P|\vee _{k=1}^{n}T^{-k}P)}$ ${\textstyle h_{T}(P)}$

連続時間定常エルゴード源

離散時間関数は連続時間関数に補間することができます。そのような補間fが測定可能であれば、それに応じて連続時間定常過程を と定義できます。 漸近等分割性が、上記に示した iid または有限値定常エルゴードの場合のように離散時間過程に成り立つ場合、何らかの測定可能な補間によってそこから導かれる連続時間定常過程にも自動的に成り立ちます。すなわち、 と なります。 ここでn は時間τにおける自由度に対応します。nH ( X )/ τとH ( X )は、それぞれシャノンによって定義された単位時間あたりと自由度あたりのエントロピーです。 ${\displaystyle {\tilde {X}}:=f\circ X}$ $${\displaystyle -{\frac {1}{n}}\log p({\tilde {X}}_{0}^{\tau })\to H(X)}$$

このような連続時間定常過程の重要なクラスとして、標本空間が連続関数の部分集合となる帯域制限定常エルゴード過程が挙げられます。漸近等分配性は、過程が白色の場合に成立します。この場合、時間標本は独立同値です。あるいは、T > 1/2 W （Wは公称帯域幅）が存在し、T間隔の時間標本が有限集合内の値を取る場合、離散時間有限値定常エルゴード過程となります。 ${\displaystyle {\mathcal {L}}_{2}}$

時間不変の操作は、漸近的等分割特性、定常性、およびエルゴード性も保持し、プロセス内の有限個の時間サンプルをゼロにすることで、漸近的等分割特性を失うことなく、定常プロセスを簡単に非定常に変換できます。

カテゴリー理論

等分割性のカテゴリー理論的定義はグロモフによって与えられている。^[6]測度空間Pのカルティシアン冪 の列が与えられたとき、この列は漸近的に同値な同質測度空間の列H _{N を}許容する（すなわち、すべての集合は同じ測度を持ち、すべての射は自己同型群の下で不変であり、したがって終端オブジェクトへの射として因数分解される）。 ${\displaystyle P^{N}=P\times \cdots \times P}$

上記には漸近的同値性の定義が必要である。これは距離関数によって与えられ、単射対応が同型写像とどれだけ異なるかを示す。単射対応とは、部分的に定義された写像であり、全単射である。つまり、部分集合との全単射である。次に、 | S | が集合Sの測度を表すものとして定義する。以下では、 PとQの測度は1と仮定し、測度空間は確率空間となる。この距離は一般に、アースムーバー距離またはワッサーシュタイン距離と呼ばれる。 ${\displaystyle \pi :P\to Q}$ ${\displaystyle P'\subset P}$ ${\displaystyle Q'\subset Q}$ $${\displaystyle |P-Q|_{\pi }=|P\setminus P'|+|Q\setminus Q'|,}$$ ${\displaystyle |P-Q|_{\pi }}$

同様に、 を P上の計数測度とみなし て定義する。したがって、この定義はP が有限測度空間であることを要求している。最後に、 $${\displaystyle |\log P:Q|_{\pi }={\frac {\sup _{p\in P'}|\log p-\log \pi (p)|}{\log \min \left(|\operatorname {set} (P')|,|\operatorname {set} (Q')|\right)}}.}$$ ${\displaystyle |\operatorname {set} (P)|}$ $${\displaystyle {\text{dist}}_{\pi }(P,Q)=|P-Q|_{\pi }+|\log P:Q|_{\pi }.}$$

一連の入射的対応は、次の場合 に漸近的に同値となる。${\displaystyle \pi _{N}:P_{N}\to Q_{N}}$ $${\displaystyle {\text{dist}}_{\pi _{N}}(P_{N},Q_{N})\to 0\quad {\text{ as }}\quad N\to \infty .}$$

P ^Nと漸近的に等しい同次空間列H _Nが与えられたとき、 PのエントロピーH ( P )は次のように表される。 $${\displaystyle H(P)=\lim _{N\to \infty }{\frac {1}{N}}|\operatorname {set} (H_{N})|.}$$

参照

• クラメールの定理（大偏差）
• ノイズチャネル符号化定理
• シャノンの情報源符号化定理

注記

1. Cover & Thomas (1991)、51ページ。
2. ホーキンス、ジェーン・M. (2021).エルゴード力学：基礎理論から応用まで. 数学大学院テキスト. シャム、スイス: シュプリンガー. p. 204. ISBN 978-3-030-59241-7。
3. Algoet, Paul H.; Cover, Thomas M. (1988). 「シャノン・マクミラン・ブライマン定理のサンドイッチ証明」(PDF) . The Annals of Probability . 16 (2): 899– 909. doi :10.1214/aop/1176991794. JSTOR  2243846. 2016年12月6日時点のオリジナル(PDF)からのアーカイブ。
4. Petersen, Karl E. (1983). 「6.2. シャノン・マクミラン・ブライマン定理」. エルゴード理論. Cambridge Studies in Advanced Mathematics. Cambridge: Cambridge University Press. ISBN 978-0-521-38997-6。
5. ポリコット、マーク、ユリ、ミチコ (1998). 「12.4. シャノン・マクミラン・ブリーマン定理」. 動的システムとエルゴード理論. ロンドン数学会学生用テキスト. ケンブリッジ: ケンブリッジ大学出版局. ISBN 978-0-521-57294-1。
6. ミーシャ・グロモフ(2013). 「構造の探求 第1部：エントロピーについて」. (5ページ参照。等分配性は「ベルヌーイ近似定理」と呼ばれている。)

参考文献

ジャーナル記事

• クロード・E・シャノン「通信の数学的理論」ベルシステム技術ジャーナル、1948年7月/10月号。
• セルジオ・ヴェルドゥとテ・サン・ハン. 「ノイズレス情報源符号化における漸近等分割性の役割」. IEEE Transactions on Information Theory , 43 (3): 847–857, 1997. doi :10.1109/18.568696.

教科書

• Cover, Thomas M. ; Thomas, Joy A. (1991). 『情報理論の要素』（初版）. ホーボーケン, ニュージャージー州: Wiley. ISBN 978-0-471-24195-9。
• マッケイ、デイビッド・JC（2003年）『情報理論、推論、学習アルゴリズム』ケンブリッジ大学出版局、ISBN 0-521-64298-1。