list of figures
1 introduction and preview
1.1 preview of the book / 5
2 entropy, relative entropy and mutual information
2.1 entropy / 12
2.2 joint entropy and conditional entropy / 15
2.3 relative entropy and mutual information / 18
2.4 relationship between entropy and mutual information / 19
2.5 chain rules for entropy, relative entropy and mutual information / 21
2.6 jensen's inequality and its consequences / 23
2.7 the log sum inequality and its applications / 29
2.8 data processing inequality / 32
2.9 the second law of thermodynamics / 33
2.10 sufficient statistics / 36
2.11 fano's inequality / 38
summary of chapter 2 / 40
problems for chapter 2 / 42
historical notes / 49
3 the asymptotic equipartition property
3.1 the aep / 51
.3.2 consequences of the aep: data compression / 53
3.3 high probability sets and the typical set / 55
summary of chapter 3 / 56
problems for chapter 3 / 57
historical notes / 59
4 entropy rates of a stochastic process 60
4.1 markov chains / 60
4.2 entropy rate / 63
4.3 example: entropy rate of a random walk on a weighted graph / 66
4.4 hidden markov models / 69
summary of chapter 4 / 71
problems for chapter 4 / 72
historical notes / 77
5 data compression 78
5.1 examples of codes / 79
5.2 kraft inequality / 82
5.3 optimal codes / 84
5.4 bounds on the optimal codelength / 87
5.5 kraft inequality for uniquely decodable codes / 90
5.6 huffman codes / 92
5.7 some comments on huffman codes / 94
5.8 optimality of huffman codes / 97
5.9 shannon-fano-elias coding / 101
5.10 arithmetic coding / 104
5.11 competitive optimality of the shannon code / 107
5.12 generation of discrete distributions from fair coins / 110
summary of chapter 5 / 117
problems for chapter 5 / 118
historical notes / 124
6 gambling and data compression 125
6.1 the horse race / 125
6.2 gambling and side information / 130
6.3 dependent horse races and entropy rate / 131
6.4 the entropy of english / 133
6.5 data compression and gambling / 136
6.6 gambling estimate of the entropy of english / 138
summary of chapter 6 / 140
problems for chapter 6 / 141
historical notes / 143
7 kolmogorov complexity
7.1 models of computation / 146
7.2 kolmogorov complexity: definitions and examples / 147
7.3 kolmogorov complexity and entropy / 153
7.4 kolmogorov complexity of integers / 155
7.5 algorithmically random and incompressible sequences / 156
7.6 universal probability / 160
7.7 the halting problem and the non-computability of kolmogorov complexity / 162
7.8 ω/ 164
7.9 universal gambling / 166
7.10 occam's razor / 168
7.11 kolmogorov complexity and universal probability / 169
7.12 the kolmogorov sufficient statistic / 175
summary of chapter 7 / 178
problems for chapter 7 / 180
historical notes / 182
8 channel capacity
8.1 examples of channel capacity / 184
8.2 symmetric channels / 189
8.3 properties of channel capacity / 190
8.4 preview of the channel coding theorem / 191
8.5 definitions / 192
8.6 jointly typical sequences / 194
8.7 the channel coding theorem / 198
8.8 zero-error codes / 203
8.9 fano's inequality and the converse to the coding theorem / 204
8.10 equality in the converse to the channel coding theorem / 207
8.11 hamming codes / 209
8.12 feedback capacity / 212
8.13 the joint source channel coding theorem / 215
summary of chapter 8 / 218
problems for chapter 8 / 220
historical notes / 222
9 differential entropy 224
9.1 definitions / 224
9.2 the aep for continuous random variables / 225
9.3 relation of differential entropy to discrete entropy / 228
9.4 joint and conditional differential entropy / 229
9.5 relative entropy and mutual information / 231
9.6 properties of differential entropy, relative entropy and mutual information / 232
9.7 differential entropy bound on discrete entropy / 234
summary of chapter 9 / 236
problems for chapter 9 / 237
historical notes / 238
10 the gaussian channel 239
10.1 the gaussian channel: definitions / 241
10.2 converse to the coding theorem for gaussian channels / 245
10.3 band-limited channels / 247
10.4 parallel gaussian channels / 250
10.5 channels with colored gaussian noise / 253
10.6 gaussian channels with feedback / 256
summary of chapter 10 / 262
problems for chapter 10 / 263
historical notes / 264
11 maximum entropy and spectral estimation 266
11.1 maximum entropy distributions / 266
11.2 examples / 268
11.3 an anomalous maximum entropy problem / 270
11.4 spectrum estimation / 272
11.5 entropy rates of a gaussian process / 273
11.6 burg's maximum entropy theorem / 274
summary of chapter 11 / 277
problems for chapter 11 / 277
historical notes / 278
12 information theory and statistics
12.1 the method of types / 279
12.2 the law of large numbers / 286
12.3 universal source coding / 288
12.4 large deviation theory / 291
12.5 examples of sanov's theorem / 294
12.6 the conditional limit theorem / 297
12.7 hypothesis testing / 304
12.8 stein's lemma / 309
12.9 chernoff bound / 312
12.10 lempel-ziv coding / 319
12.11 fisher information and the cramer-rao inequality / 326
summary of chapter 12 / 331
problems for chapter 12 / 333
historical notes / 335
13 rate distortion theory
13.1 quantization / 337
13.2 definitions / 338
13.3 calculation of the rate distortion function / 342
13.4 converse to the rate distortion theorem / 349
13.5 achievability of the rate distortion function / 351
13.6 strongly typical sequences and rate distortion / 358
13.7 characterization of the rate distortion function / 362
13.8 computation of channel capacity and the rate distortion function / 364
summary of chapter 13 / 367
problems for chapter 13 / 368
historical notes / 372
14 network information theory
14.1 gaussian multiple user channels / 377
14.2 jointly typical sequences / 384
14.3 the multiple access channel / 388
14.4 encoding of correlated sources / 407
14.5 duality between slepian-wolf encoding and multiple access channels / 416
14.6 the broadcast channel / 418
14.7 the relay channel / 428
14.8 source coding with side information / 432
14.9 rate distortion with side information / 438
14.10 general multiterminal networks / 444
summary of chapter 14 / 450
problems for chapter 14 / 452
historical notes / 457
15 information theory and the stock market 459
15.1 the stock market: some definitions / 459
15.2 kuhn-tucker characterization of the log-optimal portfolio / 462
15.3 asymptotic optimality of the log-optimal portfolio / 465
15.4 side information and the doubling rate / 467
15.5 investment in stationary markets / 469
15.6 competitive optimality of the log-optimal portfolio / 471
15.7 the shannon-mcmillan-breiman theorem / 474
summary of chapter 15 / 479
problems for chapter 15 / 480
historical notes / 481
16 inequalities in information theory 482
16.1 basic inequalities of information theory / 482
16.2 differential entropy / 485
16.3 bounds on entropy and relative entropy / 488
16.4 inequalities for types / 490
16.5 entropy rates of subsets / 490
16.6 entropy and fisher information / 494
16.7 the entropy power inequality and the brunnminkowski inequality / 497
16.8 inequalities for determinants / 501
16.9 inequalities for ratios of determinants / 505
overall summary / 508
problems for chapter 16 / 509
historical notes / 509
bibliography 510
list of symbols 526
index 529
点击看大图
)
加载中...
