Elements of Information Theory

Cover......Page 1
Title page......Page 4
ISBN- 9780471241959  Copyright @ 2006 by John Wiley & Sons......Page 5
Contents......Page 6
Preface To The Second Edition......Page 16
Preface To The First Edition......Page 18
Acknowledgements for the Second Edition......Page 22
Acknowledgements for the first Edition......Page 24
1. Introduction and Preview......Page 26
1.1 Preview of the Book......Page 30
2.1 Entropy......Page 38
2.2 Joint Entropy and Conditional Entropy......Page 41
2.3 Relative Entropy and Mutual Information......Page 44
2.4 Relationship Between Entropy and Mutual\rInformation......Page 45
2.5 Chain Rules for Entropy, Relative Entropy,\rand Mutual Information......Page 47
2.6 Jensen’s Inequality and Its Consequences......Page 50
2.7 Log Sum Inequality and Its Applications......Page 55
2.8 Data-Processing Inequality......Page 59
2.9 Sufficient Statistics......Page 60
2.10 Fano’s Inequality......Page 62
Summary......Page 66
Problems......Page 68
Historical Notes......Page 79
3. Asymptotic Equipartition Property......Page 82
3.1 Asymptotic Equipartition Property Theorem......Page 83
3.2 Consequences of the AEP: Data Compression......Page 85
3.3 High-Probability Sets and the Typical Set......Page 87
Problems......Page 89
Historical Notes......Page 94
4.1 Markov Chains......Page 96
4.2 Entropy Rate......Page 99
4.3 Example: Entropy Rate of a Random Walk on a Weighted Graph......Page 103
4.4 Second Law of Thermodynamics......Page 106
4.5 Functions of Markov Chains......Page 109
Summary......Page 112
Problems......Page 113
Historical Notes......Page 125
5.1 Examples of Codes......Page 128
5.2 Kraft Inequality......Page 132
5.3 Optimal Codes......Page 135
5.4 Bounds on the Optimal Code Length......Page 137
5.5 Kraft Inequality for Uniquely Decodable\rCodes......Page 140
5.6 Huffman Codes......Page 143
5.7 Some Comments on Huffman Codes......Page 145
5.8 Optimality of Huffman Codes......Page 148
5.9 Shannon–Fano–Elias Coding......Page 152
5.10 Competitive Optimality of the Shannon\rCode......Page 155
5.11 Generation of Discrete Distributions from\rFair Coins......Page 159
Summary......Page 166
Problems......Page 167
Historical Notes......Page 182
6.1 The Horse Race......Page 184
6.2 Gambling and Side Information......Page 189
6.3 Dependent Horse Races and Entropy Rate......Page 191
6.4 The Entropy of English......Page 193
6.5 Data Compression and Gambling......Page 196
6.6 Gambling Estimate of the Entropy of English......Page 198
Summary......Page 200
Problems......Page 201
Historical Notes......Page 207
7. Channel Capacity......Page 208
7.1.1 Noiseless Binary Channel......Page 209
7.1.2 Noisy Channel with Nonoverlapping\rOutputs......Page 210
7.1.3 Noisy Typewriter......Page 211
7.1.4 Binary Symmetric Channel......Page 212
7.1.5 Binary Erasure Channel......Page 213
7.2 Symmetric Channels......Page 214
7.4 Preview of the Channel Coding Theorem......Page 216
7.5 Definitions......Page 217
7.6 Jointly Typical Sequences......Page 220
7.7 Channel Coding Theorem......Page 224
7.8 Zero-Error Codes......Page 230
7.9 Fano’s Inequality and the Converse to the Coding\rTheorem......Page 231
7.10 Equality in the Converse to the Channel Coding\rTheorem......Page 233
7.11 Hamming Codes......Page 235
7.12 Feedback Capacity......Page 241
7.13 Source–Channel Separation Theorem......Page 243
Summary......Page 247
Problems......Page 248
Historical Notes......Page 265
8.1 Definitions......Page 268
8.2 AEP for Continuous Random Variables......Page 270
8.3 Relation of Differential Entropy to Discrete Entropy......Page 272
8.4 Joint and Conditional Differential Entropy......Page 274
8.5 Relative Entropy and Mutual Information......Page 275
8.6 Properties of Differential Entropy, Relative Entropy,\rand Mutual Information......Page 277
Problems......Page 281
Historical Notes......Page 284
9. Gaussian Channel......Page 286
9.1 Gaussian Channel: Definitions......Page 288
9.2 Converse to the Coding Theorem for Gaussian\rChannels......Page 293
9.3 Bandlimited Channels......Page 295
9.4 Parallel Gaussian Channels......Page 299
9.5 Channels with Colored Gaussian Noise......Page 302
9.6 Gaussian Channels with Feedback......Page 305
Summary......Page 314
Problems......Page 315
Historical Notes......Page 324
10.1 Quantization......Page 326
10.2 Definitions......Page 328
10.3.1 Binary Source......Page 332
10.3.2 Gaussian Source......Page 335
10.3.3 Simultaneous Description of Independent GaussianRandom Variables......Page 337
10.4 Converse to the Rate Distortion Theorem......Page 340
10.5 Achievability of the Rate Distortion Function......Page 343
10.6 Strongly Typical Sequences and Rate Distortion......Page 350
10.7 Characterization of the Rate Distortion Function......Page 354
10.8 Computation of Channel Capacity and the Rate\rDistortion Function......Page 357
Summary......Page 360
Problems......Page 361
Historical Notes......Page 370
11.1 Method of Types......Page 372
11.2 Law of Large Numbers......Page 380
11.3 Universal Source Coding......Page 382
11.4 Large Deviation Theory......Page 385
11.5 Examples of Sanov’s Theorem......Page 389
11.6 Conditional Limit Theorem......Page 391
11.7 Hypothesis Testing......Page 400
11.8 Chernoff–Stein Lemma......Page 405
11.9 Chernoff Information......Page 409
11.10 Fisher Information and the Cram´er–Rao\rInequality......Page 417
Summary......Page 422
Problems......Page 424
Historical Notes......Page 433
12.1 Maximum Entropy Distributions......Page 434
12.2 Examples......Page 436
12.3 Anomalous Maximum Entropy Problem......Page 438
12.4 Spectrum Estimation......Page 440
12.5 Entropy Rates of a Gaussian Process......Page 441
12.6 Burg’s Maximum Entropy Theorem......Page 442
Summary......Page 445
Problems......Page 446
Historical Notes......Page 450
13. Universal Source Coding......Page 452
13.1 Universal Codes and Channel Capacity......Page 453
13.2 Universal Coding for Binary Sequences......Page 458
13.3 Arithmetic Coding......Page 461
13.4 Lempel–Ziv Coding......Page 465
13.4.1 Sliding Window Lempel–Ziv\rAlgorithm......Page 466
13.4.2 Tree-Structured Lempel–Ziv\rAlgorithms......Page 467
13.5.1 Sliding Window Lempel–Ziv\rAlgorithms......Page 468
13.5.2 Optimality of Tree-Structured Lempel–Ziv\rCompression......Page 473
Summary......Page 481
Problems......Page 482
Historical Notes......Page 486
14. Kolmogorov Complexity......Page 488
14.1 Models of Computation......Page 489
14.2 Kolmogorov Complexity: Definitions\rand Examples......Page 491
14.3 Kolmogorov Complexity and Entropy......Page 498
14.4 Kolmogorov Complexity of Integers......Page 500
14.5 Algorithmically Random and Incompressible\rSequences......Page 501
14.6 Universal Probability......Page 505
14.7 Kolmogorov complexity......Page 507
14.8 \\Omega......Page 509
14.9 Universal Gambling......Page 512
14.10 Occam’s Razor......Page 513
14.11 Kolmogorov Complexity and Universal\rProbability......Page 515
14.12 Kolmogorov Sufficient Statistic......Page 521
14.13 Minimum Description Length Principle......Page 525
Summary......Page 526
Problems......Page 528
Historical Notes......Page 532
15. Network Information Theory......Page 534
15.1.1 Single-User Gaussian Channel......Page 538
15.1.2 Gaussian Multiple-Access Channel\rwith m Users......Page 539
15.1.3 Gaussian Broadcast Channel......Page 540
15.1.4 Gaussian Relay Channel......Page 541
15.1.5 Gaussian Interference Channel......Page 543
15.1.6 Gaussian Two-Way Channel......Page 544
15.2 Jointly Typical Sequences......Page 545
15.3 Multiple-Access Channel......Page 549
15.3.1 Achievability of the Capacity Region for the\rMultiple-Access Channel......Page 555
15.3.2 Comments on the Capacity Region for theMultiple-Access Channel......Page 557
15.3.3 Convexity of the Capacity Region of the Multiple-AccessChannel......Page 559
15.3.4 Converse for the Multiple-Access Channel......Page 563
15.3.5 m-User Multiple-Access Channels......Page 568
15.3.6 Gaussian Multiple-Access Channels......Page 569
15.4 Encoding of Correlated Sources......Page 574
15.4.1 Achievability of the Slepian–Wolf Theorem......Page 576
15.4.2 Converse for the Slepian–Wolf Theorem......Page 580
15.4.3 Slepian–Wolf Theorem for Many Sources......Page 581
15.4.4 Interpretation of Slepian–Wolf Coding......Page 582
15.5 Duality Between Slepian–Wolf Encoding and\rMultiple-Access Channels......Page 583
15.6 Broadcast Channel......Page 585
15.6.1 Definitions for a Broadcast Channel......Page 588
15.6.2 Degraded Broadcast Channels......Page 589
15.6.3 Capacity Region for the Degraded Broadcast Channel......Page 590
15.7 Relay Channel......Page 596
15.8 Source Coding with Side Information......Page 600
15.9 Rate Distortion with Side Information......Page 605
15.10 General Multiterminal Networks......Page 612
Summary......Page 619
Problems......Page 621
Historical Notes......Page 634
16.1 The Stock Market: Some Definitions......Page 638
16.2 Kuhn–Tucker Characterization of the Log-Optimal\rPortfolio......Page 642
16.3 Asymptotic Optimality of the Log-Optimal\rPortfolio......Page 644
16.4 Side Information and the Growth Rate......Page 646
16.5 Investment in Stationary Markets......Page 648
16.6 Competitive Optimality of the Log-Optimal\rPortfolio......Page 652
16.7 Universal Portfolios......Page 654
16.7.1 Finite-Horizon Universal Portfolios......Page 656
16.7.2 Horizon-Free Universal Portfolios......Page 663
16.8 Shannon–McMillan–Breiman Theorem\r(General AEP)......Page 669
Summary......Page 674
Problems......Page 677
Historical Notes......Page 680
17.1 Basic Inequalities of Information Theory......Page 682
17.2 Differential Entropy......Page 685
17.3 Bounds on Entropy and Relative Entropy......Page 688
17.4 Inequalities for Types......Page 690
17.5 Combinatorial Bounds on Entropy......Page 691
17.6 Entropy Rates of Subsets......Page 692
17.7 Entropy and Fisher Information......Page 696
17.8 Entropy Power Inequality and Brunn–Minkowski\rInequality......Page 699
17.9 Inequalities for Determinants......Page 704
17.10 Inequalities for Ratios of Determinants......Page 708
Problems......Page 711
Historical Notes......Page 712
Bibliography......Page 714
List of Symbols......Page 748
A......Page 752
B......Page 753
C......Page 755
E......Page 758
G......Page 760
H......Page 761
I......Page 762
L......Page 763
M......Page 764
P......Page 767
R......Page 768
S......Page 769
T......Page 771
V......Page 772
Z......Page 773