This book is about finite-alphabet stationary processes, which are important in
physics, engineering, and data compression. The book is designed for use in graduate
courses, seminars or self study for students or faculty with some background in measure
theory and probability theory. The focus is on the combinatorial properties of typical
finite sample paths drawn from a stationary, ergodic process. A primary goal, only
partially realized, is to develop a theory based directly on sample path arguments, with
minimal appeals to the probability formalism. A secondary goal is to give a careful
presentation of the many models for stationary finite-alphabet processes that have been
developed in probability theory, ergodic theory, and information theory.
The two basic tools for a sample path theory are a packing lemma, which shows how
"almost" packings of integer intervals can be extracted from coverings by overlapping
subintervals, and a counting lemma, which bounds the number of n -sequences that can
be partitioned into long blocks subject to the condition that most of them are drawn from
collections of known size. These two simple ideas, introduced by Ornstein and Weiss
in 1980, immediately yield the two fundamental theorems of ergodic theory, namely,
the ergodic theorem of Birkhoff and the entropy theorem of Shannon, McMillan, and
Breiman. The packing and counting ideas yield more than these two classical results,
however, for in combination with the ergodic and entropy theorems and further simple
combinatorial ideas they provide powerful tools for the study of sample paths. Much of
Chapter I and all of Chapter II are devoted to the development of these ideas.
The classical process models are based on independence ideas and include the i.i.d.
processes, Markov chains, instantaneous functions of Markov chains, and renewal and
regenerative processes. An important and simple class of such models is the class of
concatenated-block processes, that is, the processes obtained by independently concate-
nating fixed-length blocks according to some block distribution and randomizing the start.
Related models are obtained by block coding and randomizing the start, or by stationary
coding, an extension of the instantaneous function concept which allows the function to
depend on both past and future. All these models and more are introduced in the first
two sections of Chapter I. Further models, including the weak Bernoulli processes and
the important class of stationary codings of i.i.d. processes, are discussed in Chapter III
and Chapter IV.
Of particular note in the discussion of process models is how ergodic theorists think
of a stationary process, namely, as a measure-preserving transformation on a probability
space, together with a partition of the space. This point of view, introduced in Section 1.2,
leads directly to Kakutani's simple geometric representation of a process in terms of a
recurrent event, a representation that not only simplifies the discussion of stationary
renewal and regenerative processes but generalizes these concepts to the case where
times between recurrences are not assumed to be independent, but only stationary. A