An Application of Ergodic Theory : The Shannon-McMillan Breiman Theorem
| Title: | An Application of Ergodic Theory : The Shannon-McMillan Breiman Theorem |
| Author(s): | Kuukka, Antti Oskari |
| Contributor: | University of Helsinki, Faculty of Science, Department of Mathematics and Statistics |
| Discipline: | Applied Mathematics |
| Language: | English |
| Acceptance year: | 2013 |
| Abstract: |
The subject of this Master's Thesis is Shannon-McMillan-Breiman theorem, a famous and important result in information theory. Since the theorem is a statement about ergodic stochastic processes and its proof utilises Birkho 's ergodic theorem, a whole chapter has been devoted to ergodic theory.
Ergodic theory has developed into a large branch of mathematics, and so the Chapter 1 is only a brief glance at the subject. Nevertheless, we will prove one of the most important theorems in ergodic theory, the before-mentioned Birkho 's ergodic theorem. This theorem is a strong statement about the average behaviour of certain stochastic processes (or dynamical systems), and it can be seen as a generalisation of the Strong Law of Large Numbers.
Chapter 2 discusses information theory and the Shannon-McMillan-Breiman theorem. No previous knowledge about information theory is assumed, and therefore the chapter starts with an introduction to information theory. All fundamental de nitions and theorems concerning the entropy of discrete random variables are provided. After this introduction, we study the entropy of stochastic processes, which in turn leads us to the Asymptotic Equipartition Property (the AEP). Informally, a stochastic process has the AEP if almost all sample paths belong to a rather thin set, called the set of typical sequences, which despite having few elements contains most of the probability mass. Then we prove that independent and identically distributed processes have the AEP, and consider its consequences and applications such as data compression. After this, we present the Shannon-McMillan-Theorem which states that stationary, ergodic processes with infite state space have the AEP. The rest of the thesis is then devoted to the rather long, but interesting proof of the theorem.
Työn päätavoitteena on todistaa eräs versio informaatioteorian kuuluisasta tuloksesta, Shannon-McMillan-Breiman -teoreemasta. Koska tämä lause liittyy ergodisiin stokastisiin prosesseihin ja sen todistuksessa tarvitaan ergoditeorian tuloksia, olen ottanut ergoditeorian toiseksi tasavertaiseksi pääaiheeksi Shannon-McMillan-Breiman -teoreeman rinnalle.
Lukijalta ei oleteta esitietovaatimuksena ergoditeoriasta tai informaatioteorista mitään. Vaikka mittateoreettisen todennäköisyysteorian ja Markovin ketjujen perusteet oletetaan tunnetuiksi, kappaleessa 0 käydään läpi tiettyjä todennäköisyysteorian osa-alueita, jotka eivät alan peruskursseille mahdu. Näitä ovat esimerkiksi ääretönulotteisiin jonoavaruuksiin konstruoitavat sigma-algebrat, diskreettiaikainen martingaalikonvergenssiteoria, Radon-Nikodym - lauseeseen perustuva ehdollinen todennäköisyys, sekä tasainen integroituvuus.
Kappale 1 käsittelee ergoditeoriaa. Koska ergoditeoria on hyvin laaja matematiikan osa-alue, tämä kappale on aiheeseen vain lyhyt johdatus. Eräs alan tärkeimmistä tuloksista, Birkhoffin ergodilause kuitenkin esitetään kappaleessa todistuksineen. Ergoditeorian voidaan ajatella olevan matematiikan osa-alue, joka tutkii ilmiöiden keskimääräistä käyttäytymistä. Birkhoffin ergodilauseesta esimerkiksi seuraa lähes välittömästi vahva suurten lukujen laki sekä se, että pelkistymättömän ja jaksottoman Markovin ketjun tietyssä tilassa viettämä suhteellinen aika on asymptoottisesti sama kuin tasapainojakauman kyseistä tilaa koskeva pistetodennäköisyys. Kappaleen lopuksi määritellään käsite ergodinen stokastinen prosessi, joita Shannon-McMillan-Breiman -lauseen väite koskee.
Kappaleen 2 aiheena on informaatioteoria ja Shannon-McMillan-Breiman -lause. Koska lukijalta ei oleteta minkäänlaista etukäteistietoa informaatioteoriasta, kappale alkaa johdatuksella informaatioteoriaan. Johdatuksessa keskitytään ennen kaikkea diskreettien satunnaismuuttujien entropiaan, jota koskevia lauseita ja aputuloksia esitetään runsaasti. Tämän jälkeen satunnaismuuttujien entropiasta siirrytään stokastisten prosessien entropian tutkimiseen, jonka jälkeen on mahdollista esittää käsite asymptoottinen tasapartitiointiominaisuus. Karkeasti ottaen voidaan sanoa, että diskreetillä stokastisella prosessilla on asymptoottinen tasapartitiointiominaisuus, mikäli melkein kaikki sen realisaatiot kuuluvat alkioiden lukumäärältään pieneen, mutta todennäköisyysmassaltaan suureen tyypillisten jonojen joukkoon, joka käsitteenä määritellään kappaleessa tarkasti. Esimerkiksi tasapainoista kolikkoa heitettäessä tyypillisiä jonoja ovat sellaiset realisaatiot, joissa noin puolet heitoista on klaavoja. Paljastuu, että realisaatioiden jakamisella tyypillisiin ja ei-tyypillisiin jonoihin on mielenkiintoisia sovelluksia kuten tiedon tiivistäminen.
Shannon-McMillan-Breiman -lause sanoo, että stationaarisella, ergodisella stokastisella prosessilla, jolla on äärellinen tila-avaruus, on asymptoottinen tasapartitiointiominaisuus. Kappaleen 2 pituudesta huomattava osuus liittyy tämän tuloksen todistamiseen. Todistus on monivaiheinen, ja se hyödyntää runsaasti erilaisia tuloksia informaatioteorian ulkopuolelta sekä punoo yhteen työssä aiemmin johdetut tulokset. Birkhoffin ergodilause ja kappaleessa 0 esitettävä Levyn martingaalikonvergenssilause ovat erityisen tärkeässä roolissa.
|
Files in this item
| Files | Size | Format | View |
|---|---|---|---|
| AEP.pdf | 546.7Kb |
This item appears in the following Collection(s)
-
Faculty of Science [4247]