Probability, Random Processes, and Ergodic Properties

1 Probability, Random Processes, and Ergodic PropertiesJanuary 2, 2010iiProbability, Random Processes, and Ergodic PropertiesRobert M. GrayInformation Systems LaboratoryElectrical Engineering DepartmentStanford UniversitySpringer-VerlagNew Yorkivc 1987 by Springer Verlag. Revised 2001, 2006, 2007, 2008 by Robert M. book is affectionately dedicated to the memory ofElizabeth Dubois Jordan Gray1906 1998R. Adm. Augustine Heard Gray, 1981 Sara Jean Dubois 1811 ?andWilliam Old Billy Gray1750 1825viContentsContentsviiPrefaceix1 Probability and Random Introduction .. Probability Spaces and Random Variables .. Random Processes and Dynamical Systems .. Distributions .. Extension .. Isomorphism ..192 Standard Extension of Probability Measures.

2 Standard Spaces .. Some Properties of standard spaces .. Simple standard spaces .. Metric Spaces .. Extension in Standard Spaces .. The Kolmogorov Extension Theorem .. Extension Without a Basis ..383 Borel Spaces and Polish Borel Spaces .. Polish Spaces .. Polish Schemes ..544 Introduction .. Discrete Measurements .. Quantization .. Expectation .. Time Averages .. Convergence of Random Variables .. Stationary Averages ..87viiviiiCONTENTS5 conditional Probability and Introduction .. Measurements and Events .. Restrictions of Measures .. Elementary conditional Probability .. Projections .. The Radon-Nikodym Theorem .. conditional Probability.

3 Regular conditional Probability .. conditional Expectation .. Independence and Markov Chains .. 1156 Ergodic Ergodic Properties of Dynamical Systems .. Some Implications of Ergodic Properties .. Asymptotically Mean Stationary Processes .. Recurrence .. Asymptotic Mean expectations .. Limiting Sample Averages .. Ergodicity .. 1427 Ergodic Introduction .. The Pointwise Ergodic Theorem .. Block AMS Processes .. The Ergodic Decomposition .. The Subadditive Ergodic Theorem .. 1608 Process Metrics and the Ergodic Introduction .. A Metric Space of Measures .. The Rho-Bar Distance .. Measures on Measures.

4 The Ergodic Decomposition Revisited .. The Ergodic Decomposition of Markov Processes .. Barycenters .. Affine Functions of Measures .. The Ergodic Decomposition of Affine Functionals .. 194 Bibliography197 Index201 PrefaceHistory and GoalsThis book has been written for several reasons, not all of which are academic. This material wasfor many years the first half of a book in progress on information and Ergodic theory. The intentwas and is to provide a reasonably self-contained advanced treatment of measure theory, probabilitytheory, and the theory of discrete time Random processes with an emphasis on general alphabetsand on Ergodic and stationary Properties of Random processes that might be neither Ergodic norstationary.

5 The intended audience was mathematically inclined engineering graduate students andvisiting scholars who had not had formal courses in measure theoretic probability. Much of thematerial is familiar stuff for mathematicians, but many of the topics and results have not previouslyappeared in original project grew too large and the first part contained much that would likely boremathematicians and discourage them from the second part. Hence I finally followed a suggestionto separate the material and split the project in two. The original justification for the presentmanuscript was the pragmatic one that it would be a shame to waste all the effort thus far more idealistic motivation was that the presentation had merit as filling a unique, albeit small,hole in the literature.

6 Personal experience indicates that the intended audience rarely has the time totake a complete course in measure and probability theory in a mathematics or statistics department,at least not before they need some of the material in their research. In addition, many of the existingmathematical texts on the subject are hard for this audience to follow, and the emphasis is not wellmatched to engineering applications. A notable exception is Ash s excellent text [1], which waslikely influenced by his original training as an electrical engineer. Still, even that text devotes littleeffort to Ergodic theorems, perhaps the most fundamentally important family of results for applyingprobability theory to real problems. In addition, there are many other special topics that are givenlittle space (or none at all) in most texts on advanced probability and Random processes.

7 Examplesof topics developed in more depth here than in most existing texts are the following: Random processes with standard alphabetsWe develop the theory of standard spaces as amodel of quite general process alphabets. Although not as general (or abstract) as examplesoften considered by probability theorists, standard spaces have useful structural propertiesthat simplify the proofs of some general results and yield additional results that may not holdin the more general abstract case. Three important examples of results holding for standardalphabets that have not been proved in the general abstract case are the Kolmogorov extensiontheorem, the Ergodic decomposition, and the existence of regular conditional probabilities. Infact, Blackwell [6] introduced the notion of a Lusin space, a structure closely related to astandard space, in order to avoid known examples of probability spaces where the Kolmogorovextension theorem does not hold and regular conditional probabilities do not exist.

8 StandardixxPREFACE spaces include the common models of finite alphabets (digital processes) and real alphabetsas well as more general complete separable metric spaces (Polish spaces). Thus they includemany function spaces, Euclidean vector spaces, two-dimensional image intensity rasters, basic theory of standard Borel spaces may be found in the elegant text of Parthasarathy[55], and treatments of standard spaces and the related Lusin and Suslin spaces may be foundin Christensen [10], Schwartz [62], Bourbaki [7], and Cohn [12]. We here provide a differentand more coding oriented development of the basic results and attempt to separate clearly theproperties of standard spaces, which are useful and easy to manipulate, from the demonstra-tions that certain spaces are standard, which are more complicated and can be skipped.

9 Thus,unlike in the traditional treatments, we define and study standard spaces first from a purelyprobability theory point of view and postpone the topological metric space considerations and nonergodic processesWe develop the theory of asymptotically mean sta-tionary processes and the Ergodic decomposition in order to model many physical processesbetter than can traditional stationary and Ergodic processes. Both topics are virtually absentin all books on Random processes, yet they are fundamental to understanding the limitingbehavior of nonergodic and nonstationary processes. Both topics are considered in Krengel sexcellent book on Ergodic theorems [41], but the treatment here is more detailed and in greaterdepth. We consider both the common two-sided processes, which are considered to have beenproducing outputs forever, and the more difficult one-sided processes, which better modelprocesses that are turned on at some specific time and which exhibit transient Properties and theoremsWe develop the notion of time averages along with that ofprobabilistic averages to emphasize their similarity and to demonstrate many of the implica-tions of the existence of limiting sample averages.

10 We prove the Ergodic theorem theorem forthe general case of asymptotically mean stationary processes. In fact, it is shown that asymp-totic mean stationarity is both sufficient and necessary for the classical pointwise or almosteverywhere Ergodic theorem to hold for all bounded measurements. We also prove the sub-additive Ergodic theorem of Kingman [39], which is useful for studying the limiting behaviorof certain measurements on Random processes that are not simple arithmetic averages. Theproofs are based on recent simple proofs of the Ergodic theorem developed by Ornstein andWeiss [52], Katznelson and Weiss [38], Jones [37], and Shields [64]. These proofs use codingarguments reminiscent of information and communication theory rather than the traditional(and somewhat tricky) maximal Ergodic theorem.