A First Course in Probability and Markov Chains

Preface xi

1 Combinatorics 1

1.1 Binomial coefficients 1

1.1.1 Pascal triangle 1

1.1.2 Some properties of binomial coefficients 2

1.1.3 Generalized binomial coefficients and binomial series 3

1.1.4 Inversion formulas 4

1.1.5 Exercises 6

1.2 Sets, permutations and functions 8

1.2.1 Sets 8

1.2.2 Permutations 8

1.2.3 Multisets 10

1.2.4 Lists and functions 11

1.2.5 Injective functions 12

1.2.6 Monotone increasing functions 12

1.2.7 Monotone nondecreasing functions 13

1.2.8 Surjective functions 14

1.2.9 Exercises 16

1.3 Drawings 16

1.3.1 Ordered drawings 16

1.3.2 Simple drawings 17

1.3.3 Multiplicative property of drawings 17

1.3.4 Exercises 18

1.4 Grouping 19

1.4.1 Collocations of pairwise different objects 19

1.4.2 Collocations of identical objects 22

1.4.3 Multiplicative property 23

1.4.4 Collocations in statistical physics 24

1.4.5 Exercises 24

2 Probability measures 27

2.1 Elementary probability 28

2.1.1 Exercises 29

2.2 Basic facts 33

2.2.1 Events 34

2.2.2 Probability measures 36

2.2.3 Continuity of measures 37

2.2.4 Integral with respect to a measure 39

2.2.5 Probabilities on finite and denumerable sets 40

2.2.6 Probabilities on denumerable sets 42

2.2.7 Probabilities on uncountable sets 44

2.2.8 Exercises 46

2.3 Conditional probability 51

2.3.1 Definition 51

2.3.2 Bayes formula 52

2.3.3 Exercises 54

2.4 Inclusion-exclusion principle 60

2.4.1 Exercises 63

3 Random variables 68

3.1 Random variables 68

3.1.1 Definitions 69

3.1.2 Expected value 75

3.1.3 Functions of random variables 77

3.1.4 Cavalieri formula 80

3.1.5 Variance 82

3.1.6 Markov and Chebyshev inequalities 82

3.1.7 Variational characterization of the median and of the expected value 83

3.1.8 Exercises 84

3.2 A few discrete distributions 91

3.2.1 Bernoulli distribution 91

3.2.2 Binomial distribution 91

3.2.3 Hypergeometric distribution 93

3.2.4 Negative binomial distribution 94

3.2.5 Poisson distribution 95

3.2.6 Geometric distribution 98

3.2.7 Exercises 101

3.3 Some absolutely continuous distributions 102

3.3.1 Uniform distribution 102

3.3.2 Normal distribution 104

3.3.3 Exponential distribution 106

3.3.4 Gamma distributions 108

3.3.5 Failure rate 110

3.3.6 Exercises 111

4 Vector valued random variables 113

4.1 Joint distribution 113

4.1.1 Joint and marginal distributions 114

4.1.2 Exercises 117

4.2 Covariance 120

4.2.1 Random variables with finite expected value and variance 120

4.2.2 Correlation coefficient 123

4.2.3 Exercises 123

4.3 Independent random variables 124

4.3.1 Independent events 124

4.3.2 Independent random variables 127

4.3.3 Independence of many random variables 128

4.3.4 Sum of independent random variables 130

4.3.5 Exercises 131

4.4 Sequences of independent random variables 140

4.4.1 Weak law of large numbers 140

4.4.2 Borel-Cantelli lemma 142

4.4.3 Convergences of random variables 143

4.4.4 Strong law of large numbers 146

4.4.5 A few applications of the law of large numbers 152

4.4.6 Central limit theorem 159

4.4.7 Exercises 163

5 Discrete time Markov chains 168

5.1 Stochastic matrices 168

5.1.1 Definitions 169

5.1.2 Oriented graphs 170

5.1.3 Exercises 172

5.2 Markov chains 173

5.2.1 Stochastic processes 173

5.2.2 Transition matrices 174

5.2.3 Homogeneous processes 174

5.2.4 Markov chains 174

5.2.5 Canonical Markov chains 178

5.2.6 Exercises 181

5.3 Some characteristic parameters 187

5.3.1 Steps for a first visit 187

5.3.2 Probability of (at least) r visits 189

5.3.3 Recurrent and transient states 191

5.3.4 Mean first passage time 193

5.3.5 Hitting time and hitting probabilities 195

5.3.6 Exercises 198

5.4 Finite stochastic matrices 201

5.4.1 Canonical representation 201

5.4.2 States classification 203

5.4.3 Exercises 205

5.5 Regular stochastic matrices 206

5.5.1 Iterated maps 206

5.5.2 Existence of fixed points 209

5.5.3 Regular stochastic matrices 210

5.5.4 Characteristic parameters 218

5.5.5 Exercises 220

5.6 Ergodic property 222

5.6.1 Number of steps between consecutive visits 222

5.6.2 Ergodic theorem 224

5.6.3 Powers of irreducible stochastic matrices 226

5.6.4 Markov chain Monte Carlo 228

5.7 Renewal theorem 233

5.7.1 Periodicity 233

5.7.2 Renewal theorem 234

5.7.3 Exercises 239

6 An introduction to continuous time Markov chains 241

6.1 Poisson process 241

6.2 Continuous time Markov chains 246

6.2.1 Definitions 246

6.2.2 Continuous semigroups of stochastic matrices 248

6.2.3 Examples of right-continuous Markov chains 256

6.2.4 Holding times 259

Appendix A Power series 261

A.1 Basic properties 261

A.2 Product of series 263

A.3 Banach space valued power series 264

A.3.2 Exercises 267

Appendix B Measure and integration 270

B.1 Measures 270

B.1.1 Basic properties 270

B.1.2 Construction of measures 272

B.1.3 Exercises 279

B.2 Measurable functions and integration 279

B.2.1 Measurable functions 280

B.2.2 The integral 283

B.2.3 Properties of the integral 284

B.2.4 Cavalieri formula 286

B.2.5 Markov inequality 287

B.2.6 Null sets and the integral 287

B.2.7 Push forward of a measure 289

B.2.8 Exercises 290

B.3 Product measures and iterated integrals 294

B.3.1 Product measures 294

B.3.2 Reduction formulas 296

B.3.3 Exercises 297

B.4 Convergence theorems 298

B.4.1 Almost everywhere convergence 298

B.4.2 Strong convergence 300

B.4.3 Fatou lemma 301

B.4.4 Dominated convergence theorem 302

B.4.5 Absolute continuity of integrals 305

B.4.6 Differentiation of the integral 305

B.4.7 Weak convergence of measures 308

B.4.8 Exercises 312

Appendix C Systems of linear ordinary differential equations 313

C.1 Cauchy problem 313

C.1.1 Uniqueness 313

C.1.2 Existence 315

C.2 Efficient computation of eQt 317

C.2.1 Similarity methods 317

C.2.2 Putzer method 319

C.3 Continuous semigroups 321

References 324

Index 327