Browsing by Author "Kuukka, Antti Oskari"

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.