3
$\begingroup$

I do not understand the assumption $X_1, X_2, \cdots$ are i.i.d. ~p(x) in the AEP proofs I have seen. I have read some different sources for understanding the Asymptotic Equipartition Property. Using Cover & Thomas[1] as an example (page 51):

Theorem 3.1.1.(AEP): If $X_1, X_2, \cdots $ are i.i.d. ~p(x), then (...)

The proof is by using the weak law of large numbers and the fact that a statistic of independent random variables is also a random variable.

Shannon defines a Source X as an ergodic Markov chain of order k, therefore in the message $X^{(n)}=(X_1, X_2 ...X_n), X_i$ are not independent. The aforementioned AEP proof assumes a memoryless Markov chain. Why?

How can I be sure that the proof of AEP holds for a source that is an ergodic Markov chain?

[1]T. M. Cover and Joy A. Thomas. Elements of Information Theory. 2nd ed. OCLC: ocm59879802. Wiley-Interscience, 2006. isbn: 9780-471-2419-5-9.

Improve this question
$\endgroup$
4
  • $\begingroup$ The AEP is in chapter 3 of Cover and Thomas. Stochastic processes (i.e., ergodic Markov chains of order $k$) aren't even rigorously defined until chapter 4 of Cover and Thomas. You could look on Wikipedia. And I assume most of the sources you find online are copying the treatment in Cover & Thomas. $\endgroup$
    – Peter Shor
    Commented May 1, 2020 at 1:32
  • $\begingroup$ After looking at the outline of the proof for order $k$ Markov chains in wikipedia, I'm not at all surprised that Cover and Thomas introduce the AEP in the iid case. Their book was designed to be readable by engineers (as well as mathematicians). $\endgroup$
    – Peter Shor
    Commented May 1, 2020 at 1:46
  • $\begingroup$ Maybe a new proof is needed, that doesn't assume i.i.d random variables, to cover a source that is an ergodic Markov chain? $\endgroup$
    – auspicious99
    Commented May 2, 2020 at 4:07
  • $\begingroup$ After careful reading, I noticed that there is a historical note on the end of the chapter where he states that Shannon himself only proved to i.i.d. and McMillian proved for discrete stationary stochastic processes. The theorem is then called Shannon-McMillian. $\endgroup$
    – Fred Guth
    Commented May 5, 2020 at 2:47

1 Answer 1

Reset to default
3
$\begingroup$

Before we try to get into ergodic or whatever else, let's try to understand what phenomenon a mathematician or scientist is trying to (or could be trying to) model with AEP. Well

Asymptotic for very large $n$, a lot of coin flips, after a long time, etc ...

Equipartition Equally distributed amongst some boxes or bins, Uniformly random, Equilibrium state, "maximum entropy" (if you like statistical physics ... max. ent. is a misnomer if you don't ... see sec. 4.4 of Cover and Thomas), and here's a cool one heat death of the universe

Essentially (strong/weak) AEP is the Information Theory version of the (strong/weak) Law of Large Numbers. In general, if you satisfy some "Law of Large numbers", i.e. your deviations from the mean (or deviations from "typical behavior") decay "quickly" (say perhaps exponentially), then you satisfy an AEP of some kind.

There is a notion of Strong topicality that is used in Csiszár & Körner (Csiszár invented the method of types, a very powerful method in information theory) that might help you understand better i.e. strong typicality means that:

Strong Typicality: The percentage of $a$'s in $(x_1,...,x_n)$ is approximately equal to $p(a)$.

But what is the probability $p$ in this case!!! That is exactly the point, you have some "equilibrium state" $p$ if you are "ergodic." The point is that you start to behave like a bunch of coin flips at the limit, "when the Markov Process stabilizes."

"Ergodic" is just a vast generalization of i.i.d. with respect to "typical behavior."

The inclusions are (roughly) as follows

I.I.D. $\subset$ Stationary Markov $\subset$ "Ergodic" $\subset$ $Q$ is "isomorphic/asymptotically equivalent" to a free/independent product space $P^n$

If we keep trying to generalize further and further we eventually reach "abstract non-sense" land (which is a beautiful subject by the way, I personally recommend Aluffi and Awody).

Cover and Thomas are excellent expositors, they were trying to introduce you to the notion of "typical behavior" one baby step at a time. The point is not to jump to the most general possible statement of AEP but to understand the general principles behind the theory of Information; such as how one can "typically" communicate messages perfectly over a "noisy/imperfect" channel. For example, Csiszár & Körner introduce strong typicality early on so that they can get the best error bounds in their proofs right off the bat. Go ahead and try to read Csiszár & Körner casually; while Csiszár is one of the great giants of Information theory he is not necessarily the best expositor. As my fellow Peter (Peter$\cong$Pedro) was trying to point out it would just be poor exposition for him to have done that. The vast majority of applications in Network theory don't even use that, the noise in telephone networks is modeled as white noise in practice etc ...

By the way the proof you are looking for is Thm.16.8 in Cover and Thomas but I really don't recommend you try to attack that monster just yet. At least try out Sec.4.4 in Cover and Thomas first to get a rigorous explanation of some of the stuff I stated here.

Good luck on your mathematical adventures! Bon Voyage, Fred!

Improve this answer
$\endgroup$
8
  • 1
    $\begingroup$ This was really helpful. Thanks a lot! $\endgroup$
    – Fred Guth
    Commented May 5, 2020 at 2:49
  • $\begingroup$ I am really glad I was able to help. Take care! $\endgroup$
    – Pedro Juan Soto
    Commented May 5, 2020 at 3:20
  • 1
    $\begingroup$ Awesome! By the way, you wrote Pedro≅Pedro. You mean Pedro≅Peter, right? $\endgroup$
    – auspicious99
    Commented May 18, 2020 at 14:35
  • 1
    $\begingroup$ Hmm, Csiszár is not in the list of the Martians that you linked to? (en.wikipedia.org/wiki/The_Martians_(scientists)) $\endgroup$
    – auspicious99
    Commented May 18, 2020 at 14:42
  • $\begingroup$ Remember $\cong $ is isomorphic not equals ;) "Peter" and "Pedro" are isomorphic via a homomorphism of languages lol ... (isomorphic means "equivalent structures" in math and the etymology is greek "iso-" means equal and "morph" means form) $\endgroup$
    – Pedro Juan Soto
    Commented May 18, 2020 at 14:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.