Asymptotische Gleichverteilungseigenschaft - Asymptotic equipartition property

Informationstheorie
Entropie Differentielle Entropie Bedingte Entropie Gemeinsame Entropie Gegenseitige Information Bedingte gegenseitige Information Relative Entropie Entropierate Grenzdichte diskreter Punkte Informationstheorie mit endlicher Blocklänge
Asymptotische Gleichverteilungseigenschaft Rate-Distortion-Theorie
Das Quellcodierungstheorem von Shannon Kanalkapazität Codierungstheorem für verrauschte Kanäle Satz von Shannon-Hartley
v T e

In der Informationstheorie ist die asymptotische Gleichverteilungseigenschaft ( AEP ) eine allgemeine Eigenschaft der Ausgabeabtastwerte einer stochastischen Quelle . Es ist grundlegend für das Konzept der typischen Menge, das in Theorien der Datenkompression verwendet wird .

Grob gesagt besagt das Theorem, dass, obwohl es viele Ergebnisreihen gibt, die durch einen zufälligen Prozess erzeugt werden können, das tatsächlich produzierte höchstwahrscheinlich aus einer lose definierten Menge von Ergebnissen stammt, die alle ungefähr die gleiche Chance haben, das tatsächlich realisierte zu sein . (Dies ist eine Folge des Gesetzes der großen Zahlen und der ergodischen Theorie .) Obwohl es einzelne Ergebnisse gibt, die eine höhere Wahrscheinlichkeit haben als jedes Ergebnis in dieser Menge, garantiert die große Anzahl von Ergebnissen in der Menge fast, dass das Ergebnis aus dem einstellen. Eine Möglichkeit, die Eigenschaft intuitiv zu verstehen, ist das große Abweichungstheorem von Cramér , das besagt, dass die Wahrscheinlichkeit einer großen Abweichung vom Mittelwert exponentiell mit der Anzahl der Stichproben abnimmt. Solche Ergebnisse werden in der Theorie der großen Abweichungen untersucht ; intuitiv sind es die großen Abweichungen, die die Gleichverteilung verletzen würden, aber diese sind unwahrscheinlich.

Auf dem Gebiet der Pseudozufallszahlenerzeugung wird ein Kandidatengenerator von unbestimmter Qualität, dessen Ausgangssequenz nach einigen statistischen Kriterien zu weit außerhalb des typischen Satzes liegt, als nicht ausreichend zufällig abgelehnt. Obwohl die typische Menge lose definiert ist, ergeben sich daher praktische Vorstellungen bezüglich ausreichender Typizität.

Definition

Bei einem zeitdiskreten stationären ergodischen stochastischen Prozess auf dem Wahrscheinlichkeitsraum ist die asymptotische Gleichverteilungseigenschaft eine Aussage, dass ${\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}$

wobei oder einfach die Entropierate von bezeichnet , die für alle zeitdiskreten stationären Prozesse einschließlich der ergodischen existieren muss . Die asymptotische equipartition Eigenschaft ist für finite-wertige (dh bewiesen ) stationären ergodischen stochastischen Prozesse in der Shannon-McMillan-Breiman Theorems die Ergodentheorie und für jegliche Verwendung IId Quellen direkt mit dem Gesetz der großen Zahlen sowohl in der diskretwertige Fall (wobei ist einfach die Entropie eines Symbols) und den stetigwertigen Fall (wobei H stattdessen die differentielle Entropie ist). Die Definition der asymptotischen Gleichverteilungseigenschaft kann auch für bestimmte Klassen zeitkontinuierlicher stochastischer Prozesse erweitert werden, für die eine typische Menge für eine ausreichend lange Beobachtungszeit existiert. Die Konvergenz ist in allen Fällen fast sicher nachgewiesen . ${\displaystyle H(X)}$${\displaystyle H}$${\displaystyle X}$${\displaystyle |\Omega |<\infty}$${\displaystyle H}$

Zeitdiskrete iid-Quellen

Gegeben ist eine iid - Quelle , die Werte im Alphabet annehmen kann , ihre Zeitreihe ist iid mit Entropie . Das schwache Gesetz der großen Zahlen ergibt die asymptotische Gleichverteilungseigenschaft mit Konvergenz der Wahrscheinlichkeit , ${\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|>\epsilon \right]=0\qquad\forall \epsilon >0.}$

da die Entropie gleich der Erwartung von ist

${\displaystyle -{\frac {1}{n}}\log p(X_{1},X_{2},\ldots,X_{n}).}$

Das starke Gesetz der großen Zahlen behauptet die stärkere fast sichere Konvergenz,

${\displaystyle \Pr\left[\lim_{n\to\infty}-{\frac{1}{n}}\log p(X_{1},X_{2},\ldots,X_{n} )=H(X)\rechts]=1.}$

Zeitdiskrete endlichwertige stationäre ergodische Quellen

Betrachten Sie einen endlichwertigen Stichprobenraum , dh für den zeitdiskreten stationären ergodischen Prozess , der auf dem Wahrscheinlichkeitsraum definiert ist . Die asymptotische Gleichverteilungseigenschaft für eine solche stochastische Quelle ist als das Shannon-McMillan-Breiman-Theorem bekannt , nach Claude Shannon , Brockway McMillan und Leo Breiman . ${\displaystyle \Omega}$${\displaystyle |\Omega |<\infty}$ ${\displaystyle X:=\{X_{n}\}}$ ${\displaystyle (\Omega,B,p)}$

Beweis (Skizze)

Sei x eine messbare Menge für einige${\displaystyle x=X(A)}$${\displaystyle A\in B}$ Parametrieren Sie die gemeinsame Wahrscheinlichkeit durch n und x als ${\displaystyle j(n,x):=p\left(x_{0}^{n-1}\right).}$ Parametrieren Sie die bedingte Wahrscheinlichkeit durch i , k und x als ${\displaystyle c(i,k,x):=p\left(x_{i}\mid x_{ik}^{i-1}\right).}$ Nimm den Grenzwert der bedingten Wahrscheinlichkeit als k → ∞ und bezeichne ihn als ${\displaystyle c(i,x):=p\left(x_{i}\mid x_{-\infty}^{i-1}\right).}$ Argumentieren Sie die beiden Begriffe der Entropierate ${\displaystyle \lim_{n\to\infty}\mathrm {E} [-\log j(n,X)]\quad {\text{and}}\quad \lim_{n\to \infty} \mathrm {E} [-\log c(n,n,X)]}$ existieren und sind für jeden stationären Prozess einschließlich des stationären ergodischen Prozesses X gleich . Man bezeichne es als H . Argumentiere, dass beides ${\displaystyle {\begin{aligned}c(i,k,X)&:=\left\{p\left(X_{i}\mid X_{ik}^{i-1}\right)\right\ }\\c(i,X)&:=\left\{p\left(X_{i}\mid X_{-\infty}^{i-1}\right)\right\}\end{ausgerichtet} }}$ wobei i der Zeitindex ist, sind stationäre ergodische Prozesse, deren Stichprobenmittel fast sicher gegen einige mit und bezeichnete Werte konvergieren .${\displaystyle H^{k}}$${\displaystyle H^{\infty}}$ Definieren Sie die Markov-Approximation k- ter Ordnung für die Wahrscheinlichkeit als${\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_{ik}^{i-1}\right)=j(k,x)\prod_{i=k}^{n-1}c(i,k,x)}$ Argumentieren Sie, dass aus der endlichen Wertannahme endlich ist.${\displaystyle a(n,k,X(\Omega))}$ Drücken Sie den Stichprobenmittelwert von aus und zeigen Sie, dass er fast sicher gegen H k . konvergiert${\displaystyle -{\frac {1}{n}}\log a(n,k,X)}$${\displaystyle c(i,k,X)}$ Definiere das Wahrscheinlichkeitsmaß ${\displaystyle a(n,x):=p\left(x_{0}^{n-1}\mid x_{-\infty}^{-1}\right).}$ Drücken Sie den Stichprobenmittelwert von aus und zeigen Sie, dass er fast sicher gegen H ∞ konvergiert .${\displaystyle -{\frac {1}{n}}\log a(n,X)}$${\displaystyle c(i,X)}$ Argumentieren Sie, dass für k → ∞ die Stationarität des Prozesses verwendet wird.${\displaystyle H^{k}\searrow H}$ Argumentieren Sie, dass H = H ∞ unter Verwendung des Martingal-Konvergenzsatzes von Lévy und der endlichen Wertannahme. Zeige, dass ${\displaystyle \mathrm {E} \left[{\frac {a(n,k,X)}{j(n,X)}}\right]=a(n,k,X(\Omega))}$ die, wie oben argumentiert, endlich ist. Zeige, dass ${\displaystyle \mathrm {E} \left[{\frac {j(n,X)}{a(n,X)}}\right]=1}$ durch Konditionierung auf die unendliche Vergangenheit und Iteration der Erwartung.${\displaystyle X_{-\infty}^{-1}}$ Zeige, dass ${\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}}}$ unter Verwendung der Markov-Ungleichung und des vorher abgeleiteten Erwartungswerts. Zeigen Sie auf ähnliche Weise, dass ${\displaystyle \forall\alpha\in\mathbb{R}\ :\\Pr\left[{\frac {j(n,X)}{a(n,X)}}\geq \alpha\right]\ leq {\frac{1}{\alpha}},}$ was äquivalent zu ist ${\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}}.}$ Zeigen Sie, dass limsup von ${\displaystyle {\frac {1}{n}}\log {\frac {a(n,k,X)}{j(n,X)}}\quad {\text{und}}\quad {\ frac {1}{n}}\log {\frac {j(n,X)}{a(n,X)}}}$ sind mit ziemlicher Sicherheit nicht positiv, wenn man α = n β für jedes β > 1 setzt und das Borel-Cantelli-Lemma anwendet . Zeigen Sie, dass liminf und limsup von ${\displaystyle -{\frac {1}{n}}\log j(n,X)}$ durch Aufbrechen der Logarithmen im vorherigen Ergebnis fast sicher durch H ∞ bzw. H k nach unten und oben begrenzt sind . Vervollständigen Sie den Beweis, indem Sie darauf hinweisen, dass die obere und untere Schranke zuvor gezeigt wurden, um sich H als k → ∞ zu nähern .

Nichtstationäre zeitdiskrete Quelle, die unabhängige Symbole erzeugt

Die Annahmen von Stationarität/Ergodizität/identischer Verteilung von Zufallsvariablen sind für die Asymptotische Gleichverteilungseigenschaft nicht unbedingt erforderlich. Tatsächlich erfordert die asymptotische Gleichverteilungseigenschaft, wie intuitiv ziemlich klar ist, nur eine Form des Gesetzes der großen Zahlen, das ziemlich allgemein ist. Der Ausdruck muss jedoch entsprechend verallgemeinert und die Bedingungen präzise formuliert werden.

Wir nehmen an, dass die Quelle unabhängige Symbole mit möglicherweise unterschiedlichen Ausgabestatistiken zu jedem Zeitpunkt produziert. Wir nehmen an, dass die Statistik des Prozesses vollständig bekannt ist, d. h. die Randverteilung des Prozesses zu jedem Zeitpunkt ist bekannt. Die gemeinsame Verteilung ist nur das Produkt der Randwerte. Dann gilt unter der Bedingung (die gelockert werden kann), dass für alle i , für einige M > 0 Folgendes gilt (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|<\epsilon \right]=1\qquad \forall \epsilon >0}$

wo

${\displaystyle {\overline {H}}_{n}(X)={\frac {1}{n}}H(X_{1},X_{2},\ldots,X_{n})}$

Nachweisen

Der Beweis folgt aus einer einfachen Anwendung der Markovschen Ungleichung (angewandt auf das zweite Moment von . ${\displaystyle \log(p(X_{i}))}$ ${\displaystyle {\begin{ausgerichtet}\Pr \left[\left|-{\frac {1}{n}}\log p(X_{1},X_{2},\ldots ,X_{n}) -{\overline {H}}(X)\right|>\epsilon \right]&\leq {\frac {1}{n^{2}\epsilon ^{2}}}\mathrm {Var} \left [\sum_{i=1}^{n}\left(\log(p(X_{i})\right)^{2}\right]\\&\leq {\frac {M}{n\ Epsilon ^{2}}}\to 0{\text{ as }}n\to \infty \end{aligned}}}$ Es ist offensichtlich, dass der Beweis gilt, wenn irgendein Moment für r > 1 gleichförmig beschränkt ist (wiederum durch die Markov-Ungleichung angewendet auf das r- te Moment).${\displaystyle \mathrm{E}\left[|\log p(X_{i})|^{r}\right]}$${\displaystyle \Box {}}$ Auch diese Bedingung ist nicht notwendig, aber bei einem instationären Zufallsprozess sollte es nicht schwierig sein zu testen, ob die asymptotische Gleichverteilungseigenschaft mit dem obigen Verfahren gilt.

Anwendungen

Die asymptotische Gleichverteilungseigenschaft für nichtstationäre zeitdiskrete unabhängige Prozesse führt uns (neben anderen Ergebnissen) zum Quellencodierungstheorem für nichtstationäre Quellen (mit unabhängigen Ausgangssymbolen) und zum Rauschkanalcodierungstheorem für nichtstationäre speicherlose Kanäle.

Zeitkontinuierliche stationäre ergodische Quellen

Zeitdiskrete Funktionen können in zeitkontinuierliche Funktionen interpoliert werden. Wenn eine solche Interpolation f ist messbar , können wir die zeitkontinuierliche stationären Prozess entsprechend als definieren . Wenn die asymptotische Gleichverteilungseigenschaft für den zeitdiskreten Prozess gilt, wie in den oben gezeigten iid- oder endlichwertigen stationären ergodischen Fällen, gilt sie automatisch für den zeitkontinuierlichen stationären Prozess, der durch eine messbare Interpolation daraus abgeleitet wird. dh ${\displaystyle {\tilde {X}}:=f\circ X}$

${\displaystyle -{\frac {1}{n}}\log p({\tilde {X}}_{0}^{\tau})\to H(X)}$

wobei n dem zeitlichen Freiheitsgrad τ entspricht . nH ( X ) / τ und H ( X ) ist die Entropie pro Zeiteinheit und pro Freiheitsgrad jeweils definiert durch Shannon .

Eine wichtige Klasse solcher zeitkontinuierlicher stationärer Prozesse ist der bandbegrenzte stationäre ergodische Prozess, wobei der Probenraum eine Teilmenge der kontinuierlichen Funktionen ist. Die asymptotische Gleichverteilungseigenschaft gilt, wenn der Prozess weiß ist, in diesem Fall sind die Zeitabtastwerte iid, oder es existiert T > 1/2 W , wobei W die nominale Bandbreite ist , so dass die T- beabstandeten Zeitabtastwerte Werte in einem endlichen . annehmen in diesem Fall haben wir den zeitdiskreten endlichwertigen stationären ergodischen Prozess. ${\displaystyle {\mathcal {L}}_{2}}$

Alle zeitinvarianten Operationen bewahren auch die asymptotische Gleichverteilungseigenschaft, Stationarität und Ergodizität, und wir können einen stationären Prozess leicht in einen instationären umwandeln, ohne die asymptotische Gleichverteilungseigenschaft zu verlieren, indem wir eine endliche Anzahl von Zeitabtastwerten im Prozess auf Null setzen.

Kategorientheorie

Eine kategorietheoretische Definition für die Gleichverteilungseigenschaft wird von Gromov gegeben . Gegeben eine Folge kartesischer Potenzen eines Maßraums P , lässt diese Folge eine asymptotisch äquivalente Folge H _N homogener Maßräume zu ( dh alle Mengen haben das gleiche Maß; alle Morphismen sind invariant unter der Gruppe der Automorphismen, also Faktor als Morphismus zum Terminalobjekt ). ${\displaystyle P^{N}=P\times \cdots\times P}$

Das Obige erfordert eine Definition der asymptotischen Äquivalenz . Dies wird in Form einer Distanzfunktion angegeben, die angibt, wie sehr sich eine injektive Korrespondenz von einem Isomorphismus unterscheidet . Eine injektive Korrespondenz ist eine teilweise definierte Abbildung , die eine Bijektion ist ; das heißt, es ist eine Bijektion zwischen einer Teilmenge und . Dann definiere ${\displaystyle \pi :P\to Q}$${\displaystyle P'\subset P}$${\displaystyle Q'\subset Q}$

${\displaystyle |PQ|_{\pi}=|P\smallsetminus P'|+|Q\smallsetminus Q'|}$

wo | S | bezeichnet das Maß einer Menge S . Im Folgenden wird das Maß von P und Q mit 1 angenommen, so dass die Maßräume Wahrscheinlichkeitsräume sind. Dieser Abstand wird allgemein als Erdbewegungsabstand oder Wasserstein-Metrik bezeichnet . ${\displaystyle |PQ|_{\pi}}$

Definiere in ähnlicher Weise

${\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)}}}$

wobei als Zählmaß auf P gilt . Daher erfordert diese Definition, dass P ein endlicher Maßraum ist. Schließlich lass ${\displaystyle |\operatorname {set} (P)|}$

${\displaystyle {\text{dist}}_{\pi}(P,Q)=|PQ|_{\pi}+|\log P:Q|_{\pi}}$

Eine Folge von injektiven Korrespondenzen ist dann asymptotisch äquivalent, wenn ${\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}$

Bei einer zu P ^N asymptotisch äquivalenten homogenen Raumfolge H _N kann die Entropie H ( P ) von P angenommen werden als

${\displaystyle H(P)=\lim_{N\to \infty }{\frac {1}{N}}|\operatorname {set} (H_{N})|}$

Siehe auch

• Cramérs großer Abweichungssatz
• Quellcodierungstheorem
• Codierungstheorem für verrauschte Kanäle

Anmerkungen

Verweise

Zeitungsartikel

• Claude E. Shannon. „ Eine mathematische Theorie der Kommunikation “. Bell System Technical Journal , Juli/Oktober 1948.
• Algoet, Paul H.; Cover, Thomas M. (1988). "Ein Sandwich-Beweis des Shannon-McMillan-Breiman-Theorems" (PDF) . Die Annalen der Wahrscheinlichkeit . 16 (2): 899–909.
• Sergio Verdu und Te Sun Han. "Die Rolle der asymptotischen Equipartition-Eigenschaft bei der rauschfreien Quellcodierung." IEEE Transactions on Information Theory , 43 (3): 847–857, 1997.

Lehrbücher

• Titelbild, Thomas M.; Thomas, Joy A. (1991). Elemente der Informationstheorie (erste Aufl.). Hoboken, New Jersey: Wiley. ISBN 978-0-471-24195-9.
• MacKay, David JC (2003). Informationstheorie, Inferenz und Lernalgorithmen . Cambridge University Press. ISBN 0-521-64298-1.