The Ergodic Theory of Discrete Sample Paths

THE ERGODIC THEORY OF DISCRETE SAMPLE PATHS......Page 1
Title Page......Page 2
Copyright Page......Page 3
Contents......Page 4
Preface......Page 6
I.1 Stationary processes......Page 10
I.1.a Examples......Page 14
I.1.b Probability tools......Page 20
I.1.c Exercises......Page 21
I.2 The ergodic theory model......Page 22
I.2.a Ergodic processes......Page 24
I.2.b Examples of ergodic processes......Page 25
I.2.c The return-time picture......Page 32
I.2.c.1 Processes associated with the return-time picture......Page 34
I.2.c.2 The tower construction......Page 37
I.2.d Exercises......Page 39
I.3.a Packings from coverings......Page 42
I.3.b The binary, ergodic process proof......Page 44
I.3.c The proof in the general case......Page 45
I.3.d Extensions of the packing lemma......Page 49
I.3.e Exercises......Page 50
I.4.a Frequencies for ergodic processes......Page 52
I.4.b The ergodic theorem and covering properties......Page 55
I.4.c The ergodic decomposition......Page 56
I.4.d Exercises......Page 59
I.5 The entropy theorem......Page 60
I.5.a The proof of the entropy theorem......Page 61
I.5.b Exercises......Page 64
I.6.a The entropy of a random variable......Page 65
I.6.b The entropy of a process......Page 68
I.6.c The entropy of i.i.d. and Markov processes......Page 71
I.6.d Entropy and types......Page 72
I.6.e Exercises......Page 74
I.7.a Entropy-typical sequences......Page 75
I.7.b The building-block concept......Page 78
I.7.c Entropy and prefix codes......Page 80
I.7.d Converting faithful codes to prefix codes......Page 84
I.7.e Rotation processes have entropy 0......Page 85
I.7.f Exercises......Page 87
I.8.a Approximation by finite codes......Page 88
I.8.b From block to stationary codes......Page 92
I.8.c A string-matching example......Page 94
I.9.a The weak topology......Page 96
I.9.b The d̅-metric......Page 98
I.9.b.1 The joining definition of d̅......Page 99
I.9.b.2 Empirical distributions and joinings......Page 103
I.9.b.3 Properties and interpretations of the d̅-distance......Page 105
I.9.b.4 Ergodicity, entropy, mixing, and d̅ limits......Page 108
I.9.c Exercises......Page 111
I.10 Cutting and stacking......Page 112
I.10.a The columnar representations......Page 113
I.10.b The basic cutting and stacking vocabulary......Page 116
I.10.c The final transformation and process......Page 119
I.10.d Independent cutting and stacking......Page 123
I.10.e Exercises......Page 128
II.1 Entropy and coding......Page 130
II.1.a Universal codes exist......Page 131
II.1.b Too-good codes do not exist......Page 133
II.1.c Nonexistence: second proof......Page 134
II.1.d Another proof of the entropy theorem......Page 138
II.1.e Exercises......Page 139
II.2 The Lempel–Ziv algorithm......Page 140
II.3 Empirical entropy......Page 146
II.3.a Strong-packing......Page 147
II.3.b Proof of the empirical-entropy theorem......Page 149
II.3.c Entropy estimation......Page 152
II.3.d Universal coding......Page 154
II.3.e Exercises......Page 155
II.4 Partitions of sample paths......Page 156
II.4.a Proof of the distinct-words theorem......Page 158
II.4.b Proof of the repeated-words theorem......Page 159
II.4.c Exercises......Page 162
II.5 Entropy and recurrence times......Page 163
II.5.a Entropy and prefix trees......Page 167
II.5.a.1 Proof of the prefix-tree theorem......Page 169
II.5.a.2 Proof of the finite-energy theorem......Page 171
II.5.a.3 A counterexample to the mean conjecture......Page 172
II.5.b Exercises......Page 173
III.1 Rates of convergence......Page 174
III.1.a Exponential rates for i.i.d. processes......Page 175
III.1.b The Markov and related cases......Page 178
III.1.c Counterexamples......Page 180
III.1.d Exercises......Page 182
III.2 Entropy and joint distributions......Page 183
III.2.a Proofs of admissibility and nonadmissibility......Page 185
III.2.b The weak Bernoulli case......Page 188
III.2.c Exercises......Page 192
III.3 The d̅-admissibility problem......Page 193
III.3.a Admissibility and nonadmissibility proofs......Page 194
III.3.b Strong-nonadmissibility examples......Page 196
III.3.b.1 A limit inferior result......Page 197
III.3.b.2 The general case......Page 201
III.4 Blowing-up properties......Page 203
III.4.a Blowing-up implies exponential rates......Page 205
III.4.b Finitary coding and blowing-up......Page 206
III.4.c Almost blowing-up and stationary coding......Page 207
III.4.d Exercises......Page 208
III.5 The waiting-time problem......Page 209
III.5.a Lower bound proofs......Page 211
III.5.b Proof of the exact-match waiting-time theorem......Page 212
III.5.c Proof of the approximate-match theorem......Page 213
III.5.d An exact-match counterexample......Page 214
III.5.e An approximate-match counterexample......Page 218
IV.1 Almost block-independence......Page 220
IV.1.a B-processes are ABI processes......Page 222
IV.1.b ABI processes are B-processes......Page 223
IV.1.c Mixing Markov and almost block-independence......Page 227
IV.1.d Exercises......Page 229
IV.2 The finitely determined property......Page 230
IV.2.a.1 I.i.d. processes are finitely determined......Page 232
IV.2.a.2 Mixing Markov processes are finitely determined......Page 235
IV.2.a.3 The finitely determined processes are d̅-closed......Page 237
IV.2.b Exercises......Page 240
IV.3.a The very weak Bernoulli and weak Bernoulli properties......Page 241
IV.3.b Very weak Bernoulli implies finitely determined......Page 242
IV.3.c The almost blowing-up characterization......Page 244
IV.3.d Exercises......Page 247
Bibliography......Page 248
Index......Page 254
Back Cover......Page 259