In Chapter 12, we shall examine results for a large class of processes with memory, known as ergodic processes. We start this chapter with a quick review of the main concepts of ergodic theory, then state our main results: Shannon–McMillan theorem, compression limit, and asymptotic equipartition property (AEP). Subsequent sections are dedicated to proofs of the Shannon–McMillan and ergodic theorems. Finally, in the last section we introduce Kolmogorov–Sinai entropy, which associates to a fully deterministic transformation the measure of how “chaotic” it is. This concept plays a very important role in formalizing an apparent paradox: large mechanical systems (such as collections of gas particles) are on the one hand fully deterministic (described by Newton’s laws of motion) and on the other hand have a lot of probabilistic properties (Maxwell distribution of velocities, fluctuations, etc.). Kolmogorov–Sinai entropy shows how these two notions can coexist. In addition it was used to resolve a long-standing open problem in dynamical systems regarding isomorphism of Bernoulli shifts.

In the previous chapter we introduced the concept of variable-length compression and studied its fundamental limits (with and without the prefix-free condition). In some situations, however, one may desire that the output of the compressor always has a fixed length, say, k bits. Unless k is unreasonably large, then, this will require relaxing the losslessness condition. This is the focus of Chapter 11: compression in the presence of (typically vanishingly small) probability of error. It turns out allowing even very small error enables several beautiful effects: The possibility to compress data via matrix multiplication over finite fields (linear compression). The possibility to reduce compression length if side information is available at the decompressor (Slepian–Wolf). The possibility to reduce compression length if access to a compressed representation of side information is available at the decompressor (Ahlswede–Körner–Wyner).