This book is about finite-alphabet stationary processes, which are important in physics, engineering, and data compression. 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. Features: Emphasis on recent combinatorial results about sample paths. Careful treatment of many models found to be useful in engineering. Applications of entropy ideas to coding, sample path structure, distribution estimation, recurrence times, waiting times, and prefix trees. Simplification, adaptation, and updating to the process setting of Ornstein isomorphism theory.
Author(s): Paul C. Shields
Series: Graduate Studies in Mathematics 13
Publisher: American Mathematical Society
Year: 1996
Language: English
Pages: 257
Title page......Page 1
Contents......Page 3
Preface......Page 5
I.1 Stationary processes......Page 9
I.2 The ergodic theory model......Page 21
I.3 The ergodic theorem......Page 41
I.4 Frequencies of finite blocks......Page 51
I.5 The entropy theorem......Page 59
I.6 Entropy as expected value......Page 64
I.7 Interpretations of entropy......Page 74
I.8 Stationary coding......Page 87
I.9 Process topologies......Page 95
I.10 Cutting and stacking......Page 111
II.1 Entropy and coding......Page 129
II.2 The Lempel-Ziv algorithm......Page 139
II.3 Empirical entropy......Page 145
II.4 Partitions of sample paths......Page 155
II.5 Entropy and recurrence times......Page 162
III.1 Rates of convergence......Page 173
III.2 Entropy and joint distributions......Page 182
III.3 The d-admissibility problem......Page 192
III.4 Blowing-up properties......Page 202
III.5 The waiting-time problem......Page 208
IV.1 Almost block-independence......Page 219
IV.2 The finitely determined property......Page 229
IV.3 Other B-process characterizations......Page 240
Bibliography......Page 247
Index......Page 253
