Probability in electrical engineering and computer scicence

【实例截图】

【核心代码】

Contents
1 PageRank: A ................................................................ 1
1.1 Model................................................................ 1
1.2 Markov Chain ....................................................... 3
1.2.1 General Definition ....................................... 4
1.2.2 Distribution After n Steps and Invariant Distribution .. 4
1.3 Analysis ............................................................. 5
1.3.1 Irreducibility and Aperiodicity.......................... 5
1.3.2 Big Theorem ............................................. 6
1.3.3 Long-Term Fraction of Time ............................ 7
1.4 Illustrations.......................................................... 8
1.5 Hitting Time......................................................... 10
1.5.1 Mean Hitting Time....................................... 10
1.5.2 Probability of Hitting a State Before Another.......... 11
1.5.3 FSE for Markov Chain .................................. 12
1.6 Summary ............................................................ 13
1.6.1 Key Equations and Formulas............................ 14
1.7 References........................................................... 14
1.8 Problems ............................................................ 14
2 PageRank: B ................................................................ 21
2.1 Sample Space ....................................................... 21
2.2 Laws of Large Numbers for Coin Flips............................ 23
2.2.1 Convergence in Probability.............................. 24
2.2.2 Almost Sure Convergence............................... 25
2.3 Laws of Large Numbers for i.i.d. RVs ............................. 27
2.3.1 Weak Law of Large Numbers ........................... 28
2.3.2 Strong Law of Large Numbers .......................... 28
2.4 Law of Large Numbers for Markov Chains ....................... 30
2.5 Proof of Big Theorem .............................................. 32
2.5.1 Proof of Theorem 1.1 (a) ................................ 32
2.5.2 Proof of Theorem 1.1 (b) ................................ 33
2.5.3 Periodicity................................................ 34
2.6 Summary ............................................................ 36
2.6.1 Key Equations and Formulas............................ 36
xv
xvi Contents
2.7 References........................................................... 37
2.8 Problems ............................................................ 37
3 Multiplexing: A ............................................................. 39
3.1 Sharing Links ....................................................... 39
3.2 Gaussian Random Variable and CLT .............................. 42
3.2.1 Binomial and Gaussian .................................. 45
3.2.2 Multiplexing and Gaussian .............................. 46
3.2.3 Confidence Intervals ..................................... 46
3.3 Buffers............................................................... 48
3.3.1 Markov Chain Model of Buffer ......................... 49
3.3.2 Invariant Distribution .................................... 50
3.3.3 Average Delay ........................................... 51
3.3.4 A Note About Arrivals................................... 53
3.3.5 Little’s Law .............................................. 53
3.4 Multiple Access..................................................... 54
3.5 Summary ............................................................ 55
3.5.1 Key Equations and Formulas............................ 56
3.6 References........................................................... 56
3.7 Problems ............................................................ 56
4 Multiplexing: B ............................................................. 59
4.1 Characteristic Functions ............................................ 59
4.2 Proof of CLT (Sketch) .............................................. 60
4.3 Moments of N (0,1) ............................................... 61
4.4 Sum of Squares of 2 i.i.d. N (0,1) ................................ 62
4.5 Two Applications of Characteristic Functions..................... 63
4.5.1 Poisson as a Limit of Binomial ......................... 63
4.5.2 Exponential as Limit of Geometric ..................... 64
4.6 Error Function....................................................... 65
4.7 Adaptive Multiple Access .......................................... 66
4.8 Summary ............................................................ 68
4.8.1 Key Equations and Formulas............................ 68
4.9 References........................................................... 68
4.10 Problems ............................................................ 68
5 Networks: A ................................................................. 71
5.1 Spreading Rumors .................................................. 71
5.2 Cascades............................................................. 72
5.3 Seeding the Market ................................................. 73
5.4 Manufacturing of Consent.......................................... 74
5.5 Polarization.......................................................... 76
5.6 M/M/1 Queue...................................................... 78
5.7 Network of Queues ................................................. 81
5.8 Optimizing Capacity................................................ 84
5.9 Internet and Network of Queues ................................... 87
Contents xvii
5.10 Product-Form Networks ............................................ 87
5.10.1 Example .................................................. 89
5.11 References........................................................... 89
5.12 Problems ............................................................ 90
6 Networks—B ................................................................ 93
6.1 Social Networks..................................................... 93
6.2 Continuous-Time Markov Chains.................................. 95
6.2.1 Two-State Markov Chain................................ 96
6.2.2 Three-State Markov Chain .............................. 100
6.2.3 General Case ............................................. 103
6.2.4 Uniformization........................................... 106
6.2.5 Time Reversal............................................ 108
6.3 Product-Form Networks ............................................ 108
6.4 Proof of Theorem 5.7 ............................................... 110
6.5 References........................................................... 113
7 Digital Link—A............................................................. 115
7.1 Digital Link ......................................................... 115
7.2 Detection and Bayes’ Rule ......................................... 116
7.2.1 Bayes’ Rule .............................................. 116
7.2.2 Circumstances vs. Causes ............................... 118
7.2.3 MAP and MLE........................................... 118
7.2.4 Binary Symmetric Channel.............................. 119
7.3 Huffman Codes ..................................................... 121
7.4 Gaussian Channel................................................... 124
7.4.1 BPSK ..................................................... 125
7.5 Multidimensional Gaussian Channel .............................. 127
7.5.1 MLE in Multidimensional Case......................... 128
7.6 Hypothesis Testing.................................................. 128
7.6.1 Formulation .............................................. 129
7.6.2 Solution .................................................. 130
7.6.3 Examples ................................................. 131
7.7 Summary ............................................................ 137
7.7.1 Key Equations and Formulas............................ 138
7.8 References........................................................... 138
7.9 Problems ............................................................ 138
8 Digital Link—B ............................................................. 143
8.1 Proof of Optimality of the Huffman Code......................... 143
8.2 Proof of Neyman–Pearson Theorem 7.4........................... 144
8.3 Jointly Gaussian Random Variables................................ 145
8.3.1 Density of Jointly Gaussian Random Variables ........ 146
8.4 Elementary Statistics................................................ 149
8.4.1 Zero-Mean? .............................................. 149
8.4.2 Unknown Variance....................................... 151
xviii Contents
8.4.3 Difference of Means ..................................... 152
8.4.4 Mean in Hyperplane?.................................... 153
8.4.5 ANOVA .................................................. 154
8.5 LDPC Codes ........................................................ 154
8.6 Summary ............................................................ 160
8.6.1 Key Equations and Formulas............................ 161
8.7 References........................................................... 161
8.8 Problems ............................................................ 161
9 Tracking—A ................................................................ 163
9.1 Examples ............................................................ 163
9.2 Estimation Problem................................................. 163
9.3 Linear Least Squares Estimates .................................... 165
9.3.1 Projection................................................. 168
9.4 Linear Regression................................................... 170
9.5 A Note on Overfitting............................................... 172
9.6 MMSE............................................................... 173
9.6.1 MMSE for Jointly Gaussian............................. 178
9.7 Vector Case.......................................................... 180
9.8 Kalman Filter........................................................ 182
9.8.1 The Filter................................................. 183
9.8.2 Examples ................................................. 184
9.9 Summary ............................................................ 187
9.9.1 Key Equations and Formulas............................ 187
9.10 References........................................................... 187
9.11 Problems ............................................................ 187
10 Tracking: B.................................................................. 193
10.1 Updating LLSE ..................................................... 193
10.2 Derivation of Kalman Filter ........................................ 195
10.3 Properties of Kalman Filter......................................... 197
10.3.1 Observability............................................. 198
10.3.2 Reachability.............................................. 200
10.4 Extended Kalman Filter ............................................ 200
10.4.1 Examples ................................................. 201
10.5 Summary ............................................................ 203
10.5.1 Key Equations and Formulas............................ 204
10.6 References........................................................... 204
11 Speech Recognition: A ..................................................... 205
11.1 Learning: Concepts and Examples................................. 205
11.2 Hidden Markov Chain .............................................. 206
11.3 Expectation Maximization and Clustering......................... 209
11.3.1 A Simple Clustering Problem ........................... 209
11.3.2 A Second Look........................................... 210
Contents xix
11.4 Learning: Hidden Markov Chain................................... 212
11.4.1 HEM...................................................... 212
11.4.2 Training the Viterbi Algorithm.......................... 213
11.5 Summary ............................................................ 213
11.5.1 Key Equations and Formulas............................ 213
11.6 References........................................................... 213
11.7 Problems ............................................................ 214
12 Speech Recognition: B ..................................................... 217
12.1 Online Linear Regression........................................... 217
12.2 Theory of Stochastic Gradient Projection ......................... 219
12.2.1 Gradient Projection ...................................... 220
12.2.2 Stochastic Gradient Projection .......................... 224
12.2.3 Martingale Convergence................................. 226
12.3 Big Data ............................................................. 226
12.3.1 Relevant Data ............................................ 227
12.3.2 Compressed Sensing..................................... 232
12.3.3 Recommendation Systems .............................. 236
12.4 Deep Neural Networks ............................................. 237
12.4.1 Calculating Derivatives .................................. 239
12.5 Summary ............................................................ 240
12.5.1 Key Equations and Formulas............................ 240
12.6 References........................................................... 240
12.7 Problems ............................................................ 240
13 Route Planning: A .......................................................... 243
13.1 Model................................................................ 243
13.2 Formulation 1: Pre-planning ....................................... 244
13.3 Formulation 2: Adapting ........................................... 245
13.4 Markov Decision Problem.......................................... 247
13.4.1 Examples ................................................. 248
13.5 Infinite Horizon ..................................................... 253
13.6 Summary ............................................................ 254
13.6.1 Key Equations and Formulas............................ 254
13.7 References........................................................... 254
13.8 Problems ............................................................ 254
14 Route Planning: B .......................................................... 259
14.1 LQG Control ........................................................ 259
14.1.1 Letting N → ∞ ......................................... 261
14.2 LQG with Noisy Observations ..................................... 262
14.2.1 Letting N → ∞ ......................................... 264
14.3 Partially Observed MDP............................................ 265
14.3.1 Example: Searching for Your Keys ..................... 265
14.4 Summary ............................................................ 267
14.4.1 Key Equations and Formulas............................ 267
xx Contents
14.5 References........................................................... 267
14.6 Problems ............................................................ 268
15 Perspective and Complements ............................................ 271
15.1 Inference............................................................. 271
15.2 Sufficient Statistic................................................... 272
15.2.1 Interpretation............................................. 274
15.3 Infinite Markov Chains ............................................. 274
15.3.1 Lyapunov–Foster Criterion.............................. 276
15.4 Poisson Process ..................................................... 277
15.4.1 Definition................................................. 277
15.4.2 Independent Increments ................................. 277
15.4.3 Number of Jumps ........................................ 279
15.5 Boosting ............................................................. 280
15.6 Multi-Armed Bandits ............................................... 282
15.7 Capacity of BSC .................................................... 284
15.8 Bounds on Probabilities ............................................ 288
15.8.1 Applying the Bounds to Multiplexing .................. 290
15.9 Martingales.......................................................... 294
15.9.1 Definitions................................................ 294
15.9.2 Examples ................................................. 295
15.9.3 Law of Large Numbers ................................. 300
15.9.4 Wald’s Equality .......................................... 301
15.10 Summary ............................................................ 302
15.10.1 Key Equations and Formulas............................ 302
15.11 References........................................................... 302
15.12 Problems ............................................................ 303
Correction to: Probability in Electrical Engineering
and Computer Science........................................................... C1
Correction to: Probability in Electrical Engineering
and Computer Science (Funding Information) ............................... C3
A Elementary Probability .................................................... 309
A.1 Symmetry ........................................................... 309
A.2 Conditioning ........................................................ 310
A.3 Common Confusion ................................................ 312
A.4 Independence........................................................ 313
A.5 Expectation.......................................................... 315
A.6 Variance ............................................................. 318
A.7 Inequalities .......................................................... 320
A.8 Law of Large Numbers ............................................. 320
A.9 Covariance and Regression......................................... 321
A.10 Why Do We Need a More Sophisticated Formalism?............. 323
A.11 References........................................................... 324
A.12 Solved Problems .................................................... 324
Contents xxi
B Basic Probability............................................................ 329
B.1 General Framework................................................. 329
B.1.1 Probability Space ........................................ 329
B.1.2 Borel–Cantelli Theorem................................. 330
B.1.3 Independence............................................. 331
B.1.4 Converse of Borel–Cantelli Theorem................... 332
B.1.5 Conditional Probability.................................. 332
B.1.6 Random Variable......................................... 333
B.2 Discrete Random Variable.......................................... 334
B.2.1 Definition................................................. 334
B.2.2 Expectation............................................... 335
B.2.3 Function of a RV......................................... 336
B.2.4 Nonnegative RV.......................................... 337
B.2.5 Linearity of Expectation................................. 337
B.2.6 Monotonicity of Expectation............................ 338
B.2.7 Variance, Standard Deviation ........................... 338
B.2.8 Important Discrete Random Variables .................. 339
B.3 Multiple Discrete Random Variables .............................. 341
B.3.1 Joint Distribution ........................................ 342
B.3.2 Independence............................................. 343
B.3.3 Expectation of Function of Multiple RVs .............. 343
B.3.4 Covariance ............................................... 344
B.3.5 Conditional Expectation................................. 346
B.3.6 Conditional Expectation of a Function ................. 347
B.4 General Random Variables ......................................... 347
B.4.1 Definitions................................................ 348
B.4.2 Examples ................................................. 348
B.4.3 Expectation............................................... 350
B.4.4 Continuity of Expectation ............................... 353
B.5 Multiple Random Variables ........................................ 354
B.5.1 Random Vector........................................... 354
B.5.2 Minimum and Maximum of Independent RVs ......... 356
B.5.3 Sum of Independent Random Variables ................ 357
B.6 Random Vectors..................................................... 357
B.6.1 Orthogonality and Projection............................ 359
B.7 Density of a Function of Random Variables....................... 360
B.7.1 Linear Transformations.................................. 360
B.7.2 Nonlinear Transformations .............................. 362
B.8 References........................................................... 367
B.9 Problems ............................................................ 367
References......................................................................... 375
Index............................................................................... 377