zbMATH — the first resource for mathematics

The ergodic theory of discrete sample paths. (English) Zbl 0879.28031
Graduate Studies in Mathematics. 13. Providence, RI: American Mathematical Society (AMS). xi, 249 p. (1996).
The book deals with stationary processes with finitely many states, and, in particular, with combinatorial properties of typical finite sample paths, and with problems of coding and data compression. A number of models of finite alphabet processes such as i.i.d. processes, Markov chains, functions of Markov chains, and regenerative processes is discussed from the point of view of coding.
The first chapter discusses the product space model, the ergodic theorem, the Shannon-McMillan-Breiman theorem (called entropy theorem), stationary coding, and cutting and stacking constructions. Chapter 2 deals with general entropy related properties, the Lempel-Ziv algorithm, and the connection between entropy and recurrence times, and the growth of prefix trees. Chapter 3 deals with those properties that hold only for restricted classes of processes (rates of convergence for frequencies, estimation of joint distributions in the variational metric and the \(\overline d\)-metric, and a connection between entropy and waiting times. The final fourth chapter discusses various characterizations of the class of stationary codings of i.i.d. processes: finitely determined processes, very weak Bernoulli processes, blowing up characterizations, and almost block independence.
In spite of the words “Ergodic Theory” in the title of the book, the typical ergodic theoretic questions like the isomorphy problem are largely neglected. If a reader wants to study the ergodic theory background, he may wish to consult the book of D. J. Rudolph: “Fundamentals of measurable dynamics” (1990; Zbl 0718.28008)] which is not quoted. There is no mention of the Krieger generator theorem, though this theorem characterizes those ergodic processes which can be coded into finite alphabet processes. On the other hand, to my knowledge, this is the first book in which typical information theoretic coding questions (block codes, prefix tree problems) are discussed systematically for stationary processes.
The author usually sketches the ideas of a proof first before giving the details of the proofs. This helps to get a deeper understanding. Many of his formulations are made for easy remembrance (“too-good codes do not exist”, “blowing up implies exponential rates”). However, sometimes the new terminology for established notions may not be helpful. (Why are functions of a Markov chain called finite state processes?)
In summary, this is a very original book on a topic of current interest written by an experienced author.

28D20 Entropy and other invariants
28-01 Introductory exposition (textbooks, tutorial papers, etc.) pertaining to measure and integration
94A24 Coding theorems (Shannon theory)
94-01 Introductory exposition (textbooks, tutorial papers, etc.) pertaining to information and communication theory
28D05 Measure-preserving transformations
94A17 Measures of information, entropy
60G17 Sample path properties
60G10 Stationary stochastic processes