Notation iii
Preface ix
1 Independent Random Sequences 1
1.1 Denumerable Sequences . . . . . . . . . . . . . . . . . . . . . . . 1
1.1.1 Sequences of Events . . . . . . . . . . . . . . . . . . . . . 7
1.1.2 Independence . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.2 Analytic Tools . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.2.1 Generating Functions . . . . . . . . . . . . . . . . . . . . 12
1.2.2 Characteristic Functions . . . . . . . . . . . . . . . . . . . 13
1.2.3 Laplace Transforms . . . . . . . . . . . . . . . . . . . . . 15
1.2.4 Moment Generating Functions and Cram´er Transforms . 17
1.2.5 From Entropy to Entropy Rate . . . . . . . . . . . . . . . 19
1.3 Sums and Random Sums . . . . . . . . . . . . . . . . . . . . . . . 23
1.3.1 Sums of Independent Variables . . . . . . . . . . . . . . . 23
1.3.2 Random Sums . . . . . . . . . . . . . . . . . . . . . . . . 27
1.3.3 Random Walks . . . . . . . . . . . . . . . . . . . . . . . . 29
1.4 Convergence of Random Sequences . . . . . . . . . . . . . . . . . 30
1.4.1 Different Types of Convergence . . . . . . . . . . . . . . . 30
1.4.2 Limit Theorems . . . . . . . . . . . . . . . . . . . . . . . 33
1.5 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
2 Conditioning and Martingales 51
2.1 Conditioning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
2.1.1 Conditioning with Respect to an Event . . . . . . . . . . 52
2.1.2 Conditional Probabilities . . . . . . . . . . . . . . . . . . 53
2.1.3 Conditional Distributions . . . . . . . . . . . . . . . . . . 56
2.1.4 Conditional Expectation . . . . . . . . . . . . . . . . . . . 57
2.1.5 Conditioning and Independence . . . . . . . . . . . . . . . 63
2.1.6 Practical Determination . . . . . . . . . . . . . . . . . . . 65
2.2 The Linear Model . . . . . . . . . . . . . . . . . . . . . . . . . . 68
2.3 Stopping Times . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
2.4 Discrete-Time Martingales . . . . . . . . . . . . . . . . . . . . . . 73
2.4.1 Definitions and Properties . . . . . . . . . . . . . . . . . . 73
2.4.2 Classical Inequalities . . . . . . . . . . . . . . . . . . . . . 78
2.4.3 Martingales and Stopping Times . . . . . . . . . . . . . . 81
2.4.4 Convergence of Martingales . . . . . . . . . . . . . . . . . 84
2.4.5 Square Integrable Martingales . . . . . . . . . . . . . . . . 86
2.5 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
3 Markov Chains 99
3.1 General Properties . . . . . . . . . . . . . . . . . . . . . . . . . . 99
3.1.1 Transition Functions with Examples . . . . . . . . . . . . 99
3.1.2 Martingales and Markov Chains . . . . . . . . . . . . . . 107
3.1.3 Stopping Times and Markov Chains . . . . . . . . . . . . 109
3.2 Classification of States . . . . . . . . . . . . . . . . . . . . . . . . 111
3.3 Stationary Distribution and Asymptotic Behavior . . . . . . . . . 116
3.4 Periodic Markov chains . . . . . . . . . . . . . . . . . . . . . . . 123
3.5 Finite Markov Chains . . . . . . . . . . . . . . . . . . . . . . . . 127
3.5.1 Specific Properties . . . . . . . . . . . . . . . . . . . . . . 127
3.5.2 Application to Reliability . . . . . . . . . . . . . . . . . . 132
3.6 Branching Processes . . . . . . . . . . . . . . . . . . . . . . . . . 135
3.7 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139
4 Continuous Time Stochastic Processes 153
4.1 General Notions . . . . . . . . . . . . . . .