<p>Before we try to get into <em>ergodic</em> 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 </p>

<blockquote>
  <p><strong>Asymptotic</strong> for very large <span class="math-container">$n$</span>, a lot of coin flips, after a long time, etc ... </p>
  
  <p><strong>Equipartition</strong> <a href="https://en.wikipedia.org/wiki/Equipartition_theorem" rel="nofollow noreferrer">Equally distributed amongst some boxes or bins</a>, Uniformly random, <a href="https://en.wikipedia.org/wiki/Thermodynamic_equilibrium" rel="nofollow noreferrer">Equilibrium state</a>, "maximum entropy" (if you like statistical physics ... <a href="https://www.google.com/books/edition/Elements_of_Information_Theory/VWq5GG6ycxMC?hl=en&amp;gbpv=1&amp;printsec=frontcover" rel="nofollow noreferrer">max. ent. is a misnomer if you don't ... see sec. 4.4 of Cover and Thomas</a>), and here's <a href="https://en.wikipedia.org/wiki/Heat_death_of_the_universe" rel="nofollow noreferrer">a cool one heat death of the universe</a></p>
</blockquote>

<p>Essentially (strong/weak) AEP is the Information Theory version of the (<a href="https://en.wikipedia.org/wiki/Law_of_large_numbers#Strong_law" rel="nofollow noreferrer">strong</a>/<a href="https://en.wikipedia.org/wiki/Law_of_large_numbers" rel="nofollow noreferrer">weak</a>) Law of Large Numbers. <strong>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.</strong></p>

<p>There is a notion of <a href="https://www.google.com/books/edition/Information_Theory/2gsLkQlb8JAC?hl=en&amp;gbpv=1&amp;dq=csiszar%20and%20korner%202nd%20ed&amp;printsec=frontcover" rel="nofollow noreferrer">Strong topicality that is used in Csiszár &amp; Körner</a> (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:</p>

<blockquote>
  <p><strong><em>Strong Typicality:</em></strong> The percentage of <span class="math-container">$a$</span>'s in <span class="math-container">$(x_1,...,x_n)$</span> is approximately equal to <span class="math-container">$p(a)$</span>. </p>
</blockquote>

<p>But what is the probability <span class="math-container">$p$</span> in this case!!! That is exactly the point, you have some "equilibrium state" <span class="math-container">$p$</span> 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." </p>

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

<p>The inclusions are (roughly) as follows </p>

<blockquote>
  <p>I.I.D. <span class="math-container">$\subset$</span> Stationary Markov <span class="math-container">$\subset$</span> "Ergodic" <span class="math-container">$\subset$</span> <span class="math-container">$Q$</span> is <a href="https://en.wikipedia.org/wiki/Asymptotic_equipartition_property#Category_theory" rel="nofollow noreferrer">"isomorphic/asymptotically equivalent" to a free/independent product space</a> <span class="math-container">$P^n$</span></p>
</blockquote>

<p>If we keep trying to generalize further and further we eventually reach <a href="https://en.wikipedia.org/wiki/Abstract_nonsense" rel="nofollow noreferrer">"abstract non-sense"</a> land (which is a beautiful subject by the way, I personally recommend <a href="https://www.google.com/books/edition/Algebra_Chapter_0/deWkZWYbyHQC?hl=en&amp;gbpv=1&amp;printsec=frontcover" rel="nofollow noreferrer">Aluffi</a> and <a href="https://www.google.com/books/edition/Category_Theory/UCgUDAAAQBAJ?hl=en&amp;gbpv=1&amp;printsec=frontcover" rel="nofollow noreferrer">Awody</a>).</p>

<p><strong><em>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.</em></strong> For example, <a href="https://www.google.com/books/edition/Information_Theory/2gsLkQlb8JAC?hl=en&amp;gbpv=1&amp;dq=csiszar%20and%20korner%202nd%20ed&amp;printsec=frontcover" rel="nofollow noreferrer">Csiszár &amp; Körner</a> 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 <a href="https://www.google.com/books/edition/Information_Theory/2gsLkQlb8JAC?hl=en&amp;gbpv=1&amp;dq=csiszar%20and%20korner%202nd%20ed&amp;printsec=frontcover" rel="nofollow noreferrer">Csiszár &amp; Körner</a> casually; while <a href="https://en.wikipedia.org/wiki/The_Martians_(scientists)" rel="nofollow noreferrer">Csiszár</a> is one of the great giants of Information theory he is not necessarily the best expositor. As my fellow <a href="https://cstheory.stackexchange.com/users/1677/peter-shor">Peter</a> (Peter<span class="math-container">$\cong$</span>Pedro) was trying to point out it would just be poor exposition for him to have done that. The vast majority of applications in <a href="https://www.google.com/books/edition/Network_Information_Theory/Ack2AAAAQBAJ?hl=en&amp;gbpv=1&amp;printsec=frontcover" rel="nofollow noreferrer">Network theory</a> don't even use that, the noise in telephone networks is modeled as white noise in practice etc ...</p>

<p><strong><em>By the way the proof you are looking for is <a href="https://www.google.com/books/edition/Elements_of_Information_Theory/VWq5GG6ycxMC?hl=en&amp;gbpv=1&amp;printsec=frontcover" rel="nofollow noreferrer">Thm.16.8 in Cover and Thomas</a> but I really don't recommend you try to attack that monster just yet. At least try out <a href="https://www.google.com/books/edition/Elements_of_Information_Theory/VWq5GG6ycxMC?hl=en&amp;gbpv=1&amp;printsec=frontcover" rel="nofollow noreferrer">Sec.4.4 in Cover and Thomas</a> first to get a rigorous explanation of some of the stuff I stated here.</em></strong></p>

<p>Good luck on your mathematical adventures! Bon Voyage, Fred!</p>

CC BY-SA 4.0
2020-05-05T02:49:21.803Z
This was really helpful. Thanks a lot!
Fred Guth
CC BY-SA 4.0
2020-05-05T03:20:25.253Z
I am really glad I was able to help. Take care!
Pedro Juan Soto
CC BY-SA 4.0
2020-05-18T14:35:11.887Z
Awesome! By the way, you wrote Pedro≅Pedro. You mean Pedro≅Peter, right?
auspicious99
CC BY-SA 4.0
2020-05-18T14:42:59.263Z
Hmm,  Csiszár is not in the list of the Martians that you linked to? (https://en.wikipedia.org/wiki/The_Martians_(scientists))
auspicious99
CC BY-SA 4.0
2020-05-18T14:51:05.570Z
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)
Pedro Juan Soto
CC BY-SA 4.0
2020-05-18T14:55:15.893Z
If Csiszár is not on the list well he should be lol ...he meets all the criteria ... Hungarian .... check ... so smart no one knows what the hell he is talking about ... check ... but it could be that he was born 1 decade too late to be on the list as well
Pedro Juan Soto
CC BY-SA 4.0
2020-05-18T14:57:00.693Z
This link https://en.wikipedia.org/wiki/Isomorphism#Relation_with_equality could be helpful
Pedro Juan Soto
CC BY-SA 4.0
2020-05-18T18:12:47.043Z
Ah ha haha XD my bad I didn't see what you meant sorry about that. Thanks I fixed it!
Pedro Juan Soto
CC BY-SA 4.0
2020-05-02T05:16:41.550Z
2020-05-18T18:13:10.840Z
2020-05-18T18:13:10.840Z
Pedro Juan Soto
<p>I do not understand the assumption <span class="math-container">$X_1, X_2, \cdots$</span> 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 &amp; Thomas[1] as an example (page 51):</p>

<blockquote>
  <p>Theorem 3.1.1.(AEP): If <span class="math-container">$X_1, X_2, \cdots $</span> are i.i.d. ~p(x), then (...)</p>
</blockquote>

<p>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.</p>

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

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

<p>[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.</p>

CC BY-SA 4.0
2020-05-01T01:32:20.610Z
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](https://en.wikipedia.org/wiki/Asymptotic_equipartition_property). And I assume most of the sources you find online are copying the treatment in Cover & Thomas.
Peter Shor 
CC BY-SA 4.0
2020-05-01T01:46:09.147Z
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).
Peter Shor 
CC BY-SA 4.0
2020-05-02T04:07:54.563Z
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?
auspicious99
CC BY-SA 4.0
2020-05-05T02:47:40.920Z
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.
Fred Guth
<it.information-theory><coding-theory><st.statistics><markov-chains><encoding>
Why Asymptotic Equipartition Property theorem proofs assume the source is memoryless?
Fred Guth
# Why Asymptotic Equipartition Property theorem proofs assume the source is memoryless?

(Asked by: username_0 on 2020-04-29)

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.

**Tags:** it.information-theory, coding-theory, st.statistics, markov-chains, encoding

> **Comments:**
> **username_1**: 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](https://en.wikipedia.org/wiki/Asymptotic_equipartition_property). And I assume most of the sources you find online are copying the treatment in Cover & Thomas.  
> **username_1**: 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).  
> **username_2**: 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?  
> **username_0**: 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.  

---

## 1 answers

### Answer by username_3 on 2020-05-02. Score: 3 | Accepted answer

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](https://en.wikipedia.org/wiki/Equipartition_theorem), Uniformly random, [Equilibrium state](https://en.wikipedia.org/wiki/Thermodynamic_equilibrium), "maximum entropy" (if you like statistical physics ... [max. ent. is a misnomer if you don't ... see sec. 4.4 of Cover and Thomas](https://www.google.com/books/edition/Elements_of_Information_Theory/VWq5GG6ycxMC?hl=en&gbpv=1&printsec=frontcover)), and here's [a cool one heat death of the universe](https://en.wikipedia.org/wiki/Heat_death_of_the_universe)

Essentially (strong/weak) AEP is the Information Theory version of the ([strong](https://en.wikipedia.org/wiki/Law_of_large_numbers#Strong_law)/[weak](https://en.wikipedia.org/wiki/Law_of_large_numbers)) 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](https://www.google.com/books/edition/Information_Theory/2gsLkQlb8JAC?hl=en&gbpv=1&dq=csiszar%20and%20korner%202nd%20ed&printsec=frontcover) (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](https://en.wikipedia.org/wiki/Asymptotic_equipartition_property#Category_theory) $P^n$

If we keep trying to generalize further and further we eventually reach ["abstract non-sense"](https://en.wikipedia.org/wiki/Abstract_nonsense) land (which is a beautiful subject by the way, I personally recommend [Aluffi](https://www.google.com/books/edition/Algebra_Chapter_0/deWkZWYbyHQC?hl=en&gbpv=1&printsec=frontcover) and [Awody](https://www.google.com/books/edition/Category_Theory/UCgUDAAAQBAJ?hl=en&gbpv=1&printsec=frontcover)).

***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](https://www.google.com/books/edition/Information_Theory/2gsLkQlb8JAC?hl=en&gbpv=1&dq=csiszar%20and%20korner%202nd%20ed&printsec=frontcover) 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](https://www.google.com/books/edition/Information_Theory/2gsLkQlb8JAC?hl=en&gbpv=1&dq=csiszar%20and%20korner%202nd%20ed&printsec=frontcover) casually; while [Csiszár](https://en.wikipedia.org/wiki/The_Martians_(scientists)) is one of the great giants of Information theory he is not necessarily the best expositor. As my fellow [Peter](https://cstheory.stackexchange.com/users/1677/peter-shor) (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](https://www.google.com/books/edition/Network_Information_Theory/Ack2AAAAQBAJ?hl=en&gbpv=1&printsec=frontcover) 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](https://www.google.com/books/edition/Elements_of_Information_Theory/VWq5GG6ycxMC?hl=en&gbpv=1&printsec=frontcover) 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](https://www.google.com/books/edition/Elements_of_Information_Theory/VWq5GG6ycxMC?hl=en&gbpv=1&printsec=frontcover) first to get a rigorous explanation of some of the stuff I stated here.***

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

> **Comments:**
> **username_0**: This was really helpful. Thanks a lot!  
> **username_3**: I am really glad I was able to help. Take care!  
> **username_2**: Awesome! By the way, you wrote Pedro≅Pedro. You mean Pedro≅Peter, right?  
> **username_2**: Hmm,  Csiszár is not in the list of the Martians that you linked to? (https://en.wikipedia.org/wiki/The_Martians_(scientists))  
> **username_3**: 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)  
> **username_3**: If Csiszár is not on the list well he should be lol ...he meets all the criteria ... Hungarian .... check ... so smart no one knows what the hell he is talking about ... check ... but it could be that he was born 1 decade too late to be on the list as well  
> **username_3**: This link https://en.wikipedia.org/wiki/Isomorphism#Relation_with_equality could be helpful  
> **username_3**: Ah ha haha XD my bad I didn't see what you meant sorry about that. Thanks I fixed it!  

---

