Asymptotyczna właściwość ekwipartycji - Asymptotic equipartition property

Teoria informacji
Entropia Entropia różnicowa Entropia warunkowa Wspólna entropia Wzajemna informacja Warunkowe informacje wzajemne Entropia względna Szybkość entropii Ograniczenie gęstości punktów dyskretnych Teoria informacji o skończonej długości bloku
Asymptotyczna właściwość ekwipartycji Teoria współczynnika-zniekształcenia
Twierdzenie Shannona o kodowaniu źródłowym Pojemność kanału Twierdzenie o kodowaniu zaszumionych kanałów Twierdzenie Shannona-Hartleya
v T mi

W teorii informacji , asymptotycznej nieruchomość ekwipartycji ( AEP ) jest ogólną właściwością próbek wyjściowych o stochastycznym źródła . Jest to fundamentalne dla koncepcji typowego zbioru używanego w teoriach kompresji danych .

Z grubsza rzecz ujmując, twierdzenie to stwierdza, że ​​chociaż istnieje wiele serii wyników, które mogą być wygenerowane przez losowy proces, ten faktycznie uzyskany najprawdopodobniej pochodzi z luźno zdefiniowanego zestawu wyników, z których wszystkie mają w przybliżeniu taką samą szansę na to, że zostaną faktycznie zrealizowane. . (Jest to konsekwencja prawa wielkich liczb i teorii ergodycznej ). Chociaż istnieją indywidualne wyniki, które mają wyższe prawdopodobieństwo niż jakikolwiek wynik w tym zbiorze, ogromna liczba wyników w zbiorze niemal gwarantuje, że wynik będzie pochodził z ustawić. Jednym ze sposobów intuicyjnego zrozumienia tej własności jest twierdzenie Craméra o dużym odchyleniu, który stwierdza, że ​​prawdopodobieństwo dużego odchylenia od średniej maleje wykładniczo wraz z liczbą próbek. Takie wyniki są badane w teorii dużych odchyleń ; intuicyjnie, to duże odchylenia naruszałyby ekwipartycję, ale jest to mało prawdopodobne.

W dziedzinie generowania liczb pseudolosowych generator kandydatów o nieokreślonej jakości, którego sekwencja wyjściowa leży zbyt daleko poza typowym zbiorem według niektórych kryteriów statystycznych, jest odrzucany jako niewystarczająco losowy. Tak więc, chociaż typowy zbiór jest luźno zdefiniowany, pojawiają się praktyczne pojęcia dotyczące dostatecznej typowości.

Definicja

Biorąc pod uwagę stacjonarny ergodyczny proces stochastyczny w czasie dyskretnym w przestrzeni prawdopodobieństwa , asymptotyczna własność ekwipartycji jest twierdzeniem, że ${\ Displaystyle X}$ ${\ Displaystyle (\ Omega, B, p)}$

${\ Displaystyle - {\ Frac {1} {n}} \ log p (X_ {1}, X_ {2}, \ kropki, X_ {n}) \ do H (X) \ quad {\ tekst {jako} }\quad n\do \infty }$

gdzie lub po prostu oznacza entropię szybkość z , który musi istnieć na wszystkich dyskretnych stacjonarnymi procesami tym ergodycznych nich. Asymptotyczna własność ekwipartycji jest udowodniona dla skończonych (tj. ) stacjonarnych ergodycznych procesów stochastycznych w twierdzeniu Shannona-McMillana-Breimana przy użyciu teorii ergodycznej oraz dla dowolnych źródeł iid bezpośrednio przy użyciu prawa wielkich liczb zarówno w przypadku wartości dyskretnych (gdzie jest po prostu entropią symbolu) i przypadkiem o wartościach ciągłych (gdzie H jest zamiast tego entropią różniczkową). Definicję asymptotycznej własności ekwipartycji można również rozszerzyć o pewne klasy procesów stochastycznych w czasie ciągłym, dla których typowy zbiór istnieje przez wystarczająco długi czas obserwacji. Zbieżność jest niemal pewna we wszystkich przypadkach. ${\ Displaystyle H (X)}$${\ Displaystyle H}$${\ Displaystyle X}$${\displaystyle |\omega |<\infty}$${\ Displaystyle H}$

Źródła iid w czasie dyskretnym

Podane jest źródło iid , które może przyjmować wartości w alfabecie , jego szereg czasowy jest iid z entropią . Słabe prawo wielkich liczb daje asymptotyczną własność ekwipartycji ze zbieżnością prawdopodobieństwa , ${\ Displaystyle X}$${\displaystyle {\mathcal {X}}}$ ${\displaystyle X_{1},\ldots,X_{n}}$ ${\ Displaystyle H (X)}$

${\ Displaystyle \ lim _ {n \ do \ infty} \ Pr \ lewo [\ lewo | - {\ Frac {1} {n}} \ log p (X_ {1}, X_ {2}, \ ldots, X_ {n})-H(X)\right|>\epsilon \right]=0\qquad \forall \epsilon >0.}$

ponieważ entropia jest równa oczekiwaniu

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

Silne prawo wielkich liczb potwierdza silniejszą, prawie pewną zbieżność,

${\ Displaystyle \ Pr \ lewo [\ lim _ {n \ do \ infty} - {\ Frac {1} {n}} \ log p (X_ {1}, X_ {2}, \ ldots, X_ {n} )=H(X)\prawo]=1.}$

Stacjonarne źródła ergodyczne o skończonej wartości dyskretnej w czasie

Rozważmy przestrzeń próbek o skończonych wartościach , tj. dla stacjonarnego procesu ergodycznego w czasie dyskretnym , zdefiniowanego w przestrzeni prawdopodobieństwa . Asymptotyczna własność ekwipartycji dla takiego stochastycznego źródła jest znana jako twierdzenie Shannona-McMillana-Breimana , dzięki Claude Shannon , Brockway McMillan i Leo Breiman . ${\ Displaystyle \ Omega}$${\displaystyle |\omega |<\infty}$ ${\ Displaystyle X: = \ {X_ {n} \}}$ ${\ Displaystyle (\ Omega, B, p)}$

Dowód (szkic)

Niech x oznacza jakiś mierzalny zbiór dla niektórych${\ Displaystyle x = X (A)}$${\ Displaystyle A \ w B}$ Sparametryzuj wspólne prawdopodobieństwo przez n i x as ${\ Displaystyle j (n, x): = p \ lewo (x_ {0} ^ {n-1} \ prawo).}$ Sparametryzuj prawdopodobieństwo warunkowe przez i , k oraz x as ${\ Displaystyle c (i, k, x): = p \ lewo (x_ {i} \ mid x_ {ik} ^ {i-1} \ prawej).}$ Przyjmij granicę prawdopodobieństwa warunkowego jako k → ∞ i oznacz ją jako ${\ Displaystyle c (i, x): = p \ lewo (x_ {i} \ mid x_ {- \ infty} ^ {i-1} \ prawej).}$ Argumentuj dwa pojęcia szybkości entropii ${\ Displaystyle \ lim _ {n \ do \ infty} \ operatorname {E} [- \ log j (n, X)] \ quad {\ tekst {i}} \ quad \ lim _ {n \ do \ infty} \mathrm {E} [-\log c(n,n,X)]}$ istnieją i są równe dla dowolnego procesu stacjonarnego, w tym stacjonarnego procesu ergodycznego X . Oznacz to jako H . Twierdzić, że oba ${\ Displaystyle {\ zacząć {wyrównany} c (i, k, X) i: = \ lewo \ {p \ lewo (X_ {i} \ mid X_ {ik} ^ {i-1} \ prawej) \ prawej \ }\\c(i,X)&:=\left\{p\left(X_{i}\mid X_{-\infty }^{i-1}\right)\right\}\end{aligned} }}$ gdzie i jest indeksem czasu, są stacjonarnymi procesami ergodycznymi, których średnie próbne zbiegają się prawie na pewno do pewnych wartości oznaczonych odpowiednio przez i .${\ Displaystyle H ^ {k}}$${\ Displaystyle H ^ {\ Infty}}$ Zdefiniuj k-tego rzędu przybliżenie Markowa do prawdopodobieństwa jako${\displaystyle a(n,k,x)}$ ${\ Displaystyle a (n, k, x): = p \ lewo (X_ {0} ^ {k-1} \ prawo) \ prod _ {i = k} ^ {n-1} p \ lewo (X_ { i}\mid X_{ik}^{i-1}\right)=j(k,x)\prod _{i=k}^{n-1}c(i,k,x)}$ Argumentuj, że jest to skończone na podstawie założenia o skończonej wartości.${\displaystyle a(n,k,X(\omega))}$ Wyraź jako średnią z próby i wykaż, że prawie na pewno jest zbieżna do H k${\ Displaystyle - {\ Frac {1} {n}} \ log a (n, k, X)}$${\displaystyle c(i,k,X)}$ Zdefiniuj miarę prawdopodobieństwa ${\ Displaystyle a (n, x): = p \ lewo (x_ {0} ^ {n-1} \ mid x_ {- \ infty} ^ {-1} \ po prawej).}$ Wyraź jako średnią z próby i wykaż, że prawie na pewno jest zbieżna do H ∞ .${\ Displaystyle - {\ Frac {1} {n}} \ log a (n, X)}$${\displaystyle c(i,X)}$ Argumentuj, że jako k → ∞ używając stacjonarności procesu.${\ Displaystyle H ^ {k} \ seaarrow H}$ Argumentuj, że H = H ∞ korzystając z twierdzenia o zbieżności martyngału Lévy'ego i założenia o wartości skończonej. Pokazują, że ${\ Displaystyle \ operatorname {E} \ lewo [{\ Frac {a (n, k, X)} {j (n, X)}} \ prawo] = a (n, k, X (\ Omega))}$ co jest skończone, jak argumentowano wcześniej. Pokazują, że ${\ Displaystyle \ operatorname {E} \ lewo [{\ Frac {j (n, X)} {a (n, X)}} \ prawej] = 1}$ przez uwarunkowanie nieskończonej przeszłości i powtarzanie oczekiwań.${\ Displaystyle X_ {- \ infty} ^ {-1}}$ Pokazują, że ${\ Displaystyle \ forall \ alfa \ w \ mathbb {R} \ : \ \ Pr \ lewo [{\ Frac {a (n, k, X)} {j (n, X)}} \ geq \ alfa \ prawej ]\leq {\frac {a(n,k,X(\Omega))}{\alfa }}}$ wykorzystując nierówność Markowa i wcześniej wyprowadzone oczekiwanie. Podobnie pokaż, że ${\ Displaystyle \ forall \ alfa \ w \ mathbb {R} \ : \ \ Pr \ lewo [{\ Frac {j (n, X)} {a (n, X)}} \ geq \ alfa \ prawej] \ leq {\frac {1}{\alfa }},}$ co jest równoważne ${\ Displaystyle \ forall \ alfa \ w \ mathbb {R} \ : \ \ Pr \ lewo [{\ Frac {1} {n}} \ log {\ Frac {j (n, X)} {a (n, X)}}\geq {\frac {1}{n}}\log \alpha \right]\leq {\frac {1}{\alpha }}.}$ Pokaż, że limsup z ${\ Displaystyle {\ Frac {1} {n}} \ log {\ Frac {a (n, k, X)} {j (n, X)}} \ quad {\ tekst {i}} \ quad {\ frac {1}{n}}\log {\frac {j(n,X)}{a(n,X)}}}$ są niedodatnie prawie na pewno, ustawiając α = n β dla dowolnego β > 1 i stosując lemat Borela-Cantellego . Pokaż, że liminf i limsup z ${\ Displaystyle - {\ Frac {1} {n}} \ log j (n, X)}$ są dolne i górne ograniczone odpowiednio przez H ∞ i H k przez rozbicie logarytmów z poprzedniego wyniku. Uzupełnij dowód, wskazując, że górna i dolna granica są pokazane wcześniej, aby zbliżyć się do H jako k → ∞.

Niestacjonarne źródło czasu dyskretnego wytwarzające niezależne symbole

Założenia stacjonarności/ergodyczności/identycznego rozkładu zmiennych losowych nie są niezbędne do zachowania asymptotycznej ekwipartycji. Rzeczywiście, jak jest całkiem jasne intuicyjnie, asymptotyczna własność ekwipartycji wymaga tylko pewnej formy prawa wielkich liczb do zachowania, które jest dość ogólne. Wyrażenie to musi być jednak odpowiednio uogólnione, a warunki precyzyjnie sformułowane.

Zakładamy, że źródło wytwarza niezależne symbole, z możliwie różnymi statystykami wyjściowymi w każdej chwili. Zakładamy, że statystyki procesu są całkowicie znane, to znaczy znany jest marginalny rozkład procesu widziany w każdej chwili. Wspólna dystrybucja jest tylko produktem marginalnym. Następnie, pod warunkiem (który może być złagodzony), że dla wszystkich i , dla pewnego M > 0, zachodzi następujące (AEP): ${\ Displaystyle \ operatorname {Var} [\ log p (X_ {i})] <M}$

${\ Displaystyle \ lim _ {n \ do \ infty} \ Pr \ lewo [\ \ lewo | - {\ Frac {1} {n}} \ log p (X_ {1}, X_ {2} \ ldots ,X_{n})-{\overline {H}}_{n}(X)\right|<\epsilon \right]=1\qquad \forall \epsilon >0}$

gdzie

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

Dowód

Dowód wynika z prostego zastosowania nierówności Markowa (zastosowanej do drugiego momentu . ${\ Displaystyle \ log (p (X_ {i}))}$ ${\ Displaystyle {\ zacząć {wyrównany} \ Pr \ lewo [\ lewo | - {\ 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{wyrównane}}}$ Jest oczywiste, że dowód jest słuszny, jeśli dowolny moment jest jednostajnie ograniczony dla r > 1 (ponownie przez nierówność Markowa zastosowaną do r -tego momentu).${\ Displaystyle \ operatorname {E} \ lewo [| \ log p (X_ {i}) | ^ {r} \ po prawej]}$${\ Displaystyle \ Box {}}$ Nawet ten warunek nie jest konieczny, ale biorąc pod uwagę niestacjonarny proces losowy, nie powinno być trudne sprawdzenie, czy asymptotyczna właściwość ekwipartycji jest zachowana przy użyciu powyższej metody.

Aplikacje

Asymptotyczna własność ekwipartycji dla niestacjonarnego procesu niezależnego od czasu dyskretnego prowadzi nas (między innymi) do twierdzenia o kodowaniu źródłowym dla źródła niestacjonarnego (z niezależnymi symbolami wyjściowymi) i twierdzenia o kodowaniu zaszumionego kanału dla niestacjonarnych kanałów bez pamięci.

Stacjonarne źródła ergodyczne czasu ciągłego

Funkcje czasu dyskretnego mogą być interpolowane do funkcji czasu ciągłego. Jeżeli taka interpolacja f jest mierzalna , możemy zdefiniować proces stacjonarny w czasie ciągłym odpowiednio jako . Jeśli asymptotyczna własność ekwipartycji zachodzi dla procesu w czasie dyskretnym, jak w przypadku iid lub ergodycznych przypadków stacjonarnych o skończonej wartości, pokazanych powyżej, to automatycznie obowiązuje dla procesu stacjonarnego w czasie ciągłym, wyprowadzonego z niej przez pewną mierzalną interpolację. tj ${\displaystyle {\tylda {X}}:=f\circ X}$

${\ Displaystyle - {\ Frac {1} {n}} \ log p ({\ tylda {X}} _ {0}^ {\ tau}) \ do H (X)}$

gdzie n odpowiada stopniowi swobody w czasie τ . nH ( X )/ τ i H ( X ) to odpowiednio entropia na jednostkę czasu i na stopień swobody, zdefiniowana przez Shannona .

Ważną klasą takiego procesu stacjonarnego w czasie ciągłym jest stacjonarny proces ergodyczny o ograniczonym paśmie, w którym przestrzeń próbki jest podzbiorem funkcji ciągłych . Asymptotyczna własność ekwipartycji zachodzi, jeśli proces jest biały, w którym to przypadku próbki czasowe są iid, lub istnieje T > 1/2 W , gdzie W jest nominalną szerokością pasma , tak że próbki czasu w odstępie T przyjmują wartości w skończonej W takim przypadku mamy do czynienia z stacjonarnym procesem ergodycznym o skończonej wartości w czasie dyskretnym. ${\displaystyle {\mathcal {L}}_{2}}$

Wszelkie operacje niezmienne w czasie zachowują również asymptotyczną własność ekwipartycji, stacjonarność i ergodyczność i możemy łatwo zmienić proces stacjonarny w niestacjonarny bez utraty asymptotycznej własności ekwipartycji poprzez zerowanie skończonej liczby próbek czasu w procesie.

Teoria kategorii

Kategoria teoretyczna definicja nieruchomości ekwipartycji jest przez Gromow . Mając ciąg potęg kartezjańskich przestrzeni miar P , ciąg ten dopuszcza asymptotycznie równoważny ciąg H _N jednorodnych przestrzeni miar ( tzn. wszystkie zbiory mają tę samą miarę; wszystkie morfizmy są niezmienne w ramach grupy automorfizmów, a zatem czynnik jako morfizm do obiektu terminala ). ${\ Displaystyle P ^ {N} = P \ razy \ cdots \ razy P}$

Powyższe wymaga zdefiniowania asymptotycznej równoważności . Jest to podane w postaci funkcji odległości, podając, jak bardzo korespondencja iniekcyjna różni się od izomorfizmu . Korespondencja iniekcyjna to częściowo zdefiniowana mapa, która jest bijekcją ; oznacza to, że jest to bijection między podzbiorem a . Następnie zdefiniuj ${\ Displaystyle \ pi : P \ do Q}$${\displaystyle P'\podzbiór P}$${\displaystyle Q'\podzbiór Q}$

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

gdzie | S | oznacza miarę zbioru S . W dalszej części przyjmujemy, że miara P i Q wynosi 1, tak że przestrzenie miar są przestrzeniami prawdopodobieństwa. Odległość ta jest powszechnie nazywana odległością maszyny do robót ziemnych lub metryką Wassersteina . ${\displaystyle |PQ|_{\pi}}$

Podobnie, zdefiniuj

${\ Displaystyle | \ log P: Q | _ {\ pi} = {\ Frac {\ sup _ {p \ w P'} | \ log p- \ log \ pi (p) |} {\ log \ min \ left(|\nazwa operatora {zbiór} (P')|,|\nazwa operatora {zbiór} (Q')|\right)}}}$

z przyjętym jako miara liczenia na P . Zatem definicja ta wymaga, aby P było przestrzenią miary skończonej. Wreszcie niech ${\displaystyle |\operator {zestaw} (P)|}$

${\ Displaystyle {\ tekst {odleg.}} _ {\ pi} (P, Q) = | PQ | _ {\ pi} + | \ log P: Q | _ {\ pi}}$

Sekwencja odpowiedników iniekcyjnych jest wtedy asymptotycznie równoważna, gdy ${\ Displaystyle \ pi _ {N}: P_ {N} \ do Q_ {N}}$

${\ Displaystyle {\ tekst {odleg.}} _ {\ pi _ {N}} (P_ {N}, Q_ {N}) \ do 0 \ quad {\ tekst {jako}} \ quad N \ do \ infty}$

Mając jednorodną sekwencję przestrzenną H _{N ,} która jest asymptotycznie równoważna P ^N , entropię H ( P ) P można przyjąć jako

${\ Displaystyle H (P) = \ Lim _ {N \ do \ Infty} {\ Frac {1} {N}} | \ Operatorname {zestaw} (H_ {N}) |}$

Zobacz też

• Twierdzenie o dużym odchyleniu Cramera
• Twierdzenie o kodowaniu źródłowym
• Twierdzenie o kodowaniu zaszumionych kanałów

Uwagi

Bibliografia

artykuły prasowe

• Claude E. Shannon. „ Matematyczna teoria komunikacji ”. Dziennik techniczny Bell System , lipiec/październik 1948.
• Algoet, Paul H.; Okładka, Thomas M. (1988). „Dowód kanapki twierdzenia Shannona-McMillana-Breimana” (PDF) . Roczniki prawdopodobieństwa . 16 (2): 899–909.
• Sergio Verdu i Te Sun Han. „Rola asymptotycznej ekwipartycji w bezszumowym kodowaniu źródłowym”. IEEE Transactions on Information Theory , 43 (3): 847-857, 1997.

Podręczniki

• Okładka, Thomas M.; Thomas, Radość A. (1991). Elementy teorii informacji (wyd. pierwsze). Hoboken, New Jersey: Wiley. Numer ISBN 978-0-471-24195-9.
• MacKay, David JC (2003). Teoria informacji, wnioskowanie i algorytmy uczenia się . Wydawnictwo Uniwersytetu Cambridge. Numer ISBN 0-521-64298-1.