First Course in Probability and Markov Chains

Giuseppe Modica and Laura Poggiolini,Dipartimento di Sistemi e Informatica, Università di Firenze, Italy

• Preface xi1 Combinatorics 11.1 Binomial coefficients 11.1.1 Pascal triangle 11.1.2 Some properties of binomial coefficients 21.1.3 Generalized binomial coefficients and binomial series 31.1.4 Inversion formulas 41.1.5 Exercises 61.2 Sets, permutations and functions 81.2.1 Sets 81.2.2 Permutations 81.2.3 Multisets 101.2.4 Lists and functions 111.2.5 Injective functions 121.2.6 Monotone increasing functions 121.2.7 Monotone nondecreasing functions 131.2.8 Surjective functions 141.2.9 Exercises 161.3 Drawings 161.3.1 Ordered drawings 161.3.2 Simple drawings 171.3.3 Multiplicative property of drawings 171.3.4 Exercises 181.4 Grouping 191.4.1 Collocations of pairwise different objects 191.4.2 Collocations of identical objects 221.4.3 Multiplicative property 231.4.4 Collocations in statistical physics 241.4.5 Exercises 242 Probability measures 272.1 Elementary probability 282.1.1 Exercises 292.2 Basic facts 332.2.1 Events 342.2.2 Probability measures 362.2.3 Continuity of measures 372.2.4 Integral with respect to a measure 392.2.5 Probabilities on finite and denumerable sets 402.2.6 Probabilities on denumerable sets 422.2.7 Probabilities on uncountable sets 442.2.8 Exercises 462.3 Conditional probability 512.3.1 Definition 512.3.2 Bayes formula 522.3.3 Exercises 542.4 Inclusion–exclusion principle 602.4.1 Exercises 633 Random variables 683.1 Random variables 683.1.1 Definitions 693.1.2 Expected value 753.1.3 Functions of random variables 773.1.4 Cavalieri formula 803.1.5 Variance 823.1.6 Markov and Chebyshev inequalities 823.1.7 Variational characterization of the median and of the expected value 833.1.8 Exercises 843.2 A few discrete distributions 913.2.1 Bernoulli distribution 913.2.2 Binomial distribution 913.2.3 Hypergeometric distribution 933.2.4 Negative binomial distribution 943.2.5 Poisson distribution 953.2.6 Geometric distribution 983.2.7 Exercises 1013.3 Some absolutely continuous distributions 1023.3.1 Uniform distribution 1023.3.2 Normal distribution 1043.3.3 Exponential distribution 1063.3.4 Gamma distributions 1083.3.5 Failure rate 1103.3.6 Exercises 1114 Vector valued random variables 1134.1 Joint distribution 1134.1.1 Joint and marginal distributions 1144.1.2 Exercises 1174.2 Covariance 1204.2.1 Random variables with finite expected value and variance 1204.2.2 Correlation coefficient 1234.2.3 Exercises 1234.3 Independent random variables 1244.3.1 Independent events 1244.3.2 Independent random variables 1274.3.3 Independence of many random variables 1284.3.4 Sum of independent random variables 1304.3.5 Exercises 1314.4 Sequences of independent random variables 1404.4.1 Weak law of large numbers 1404.4.2 Borel–Cantelli lemma 1424.4.3 Convergences of random variables 1434.4.4 Strong law of large numbers 1464.4.5 A few applications of the law of large numbers 1524.4.6 Central limit theorem 1594.4.7 Exercises 1635 Discrete time Markov chains 1685.1 Stochastic matrices 1685.1.1 Definitions 1695.1.2 Oriented graphs 1705.1.3 Exercises 1725.2 Markov chains 1735.2.1 Stochastic processes 1735.2.2 Transition matrices 1745.2.3 Homogeneous processes 1745.2.4 Markov chains 1745.2.5 Canonical Markov chains 1785.2.6 Exercises 1815.3 Some characteristic parameters 1875.3.1 Steps for a first visit 1875.3.2 Probability of (at least) r visits 1895.3.3 Recurrent and transient states 1915.3.4 Mean first passage time 1935.3.5 Hitting time and hitting probabilities 1955.3.6 Exercises 1985.4 Finite stochastic matrices 2015.4.1 Canonical representation 2015.4.2 States classification 2035.4.3 Exercises 2055.5 Regular stochastic matrices 2065.5.1 Iterated maps 2065.5.2 Existence of fixed points 2095.5.3 Regular stochastic matrices 2105.5.4 Characteristic parameters 2185.5.5 Exercises 2205.6 Ergodic property 2225.6.1 Number of steps between consecutive visits 2225.6.2 Ergodic theorem 2245.6.3 Powers of irreducible stochastic matrices 2265.6.4 Markov chain Monte Carlo 2285.7 Renewal theorem 2335.7.1 Periodicity 2335.7.2 Renewal theorem 2345.7.3 Exercises 2396 An introduction to continuous time Markov chains 2416.1 Poisson process 2416.2 Continuous time Markov chains 2466.2.1 Definitions 2466.2.2 Continuous semigroups of stochastic matrices 2486.2.3 Examples of right-continuous Markov chains 2566.2.4 Holding times 259Appendix A Power series 261A.1 Basic properties 261A.2 Product of series 263A.3 Banach space valued power series 264A.3.2 Exercises 267Appendix B Measure and integration 270B.1 Measures 270B.1.1 Basic properties 270B.1.2 Construction of measures 272B.1.3 Exercises 279B.2 Measurable functions and integration 279B.2.1 Measurable functions 280B.2.2 The integral 283B.2.3 Properties of the integral 284B.2.4 Cavalieri formula 286B.2.5 Markov inequality 287B.2.6 Null sets and the integral 287B.2.7 Push forward of a measure 289B.2.8 Exercises 290B.3 Product measures and iterated integrals 294B.3.1 Product measures 294B.3.2 Reduction formulas 296B.3.3 Exercises 297B.4 Convergence theorems 298B.4.1 Almost everywhere convergence 298B.4.2 Strong convergence 300B.4.3 Fatou lemma 301B.4.4 Dominated convergence theorem 302B.4.5 Absolute continuity of integrals 305B.4.6 Differentiation of the integral 305B.4.7 Weak convergence of measures 308B.4.8 Exercises 312Appendix C Systems of linear ordinary differential equations 313C.1 Cauchy problem 313C.1.1 Uniqueness 313C.1.2 Existence 315C.2 Efficient computation of eQt 317C.2.1 Similarity methods 317C.2.2 Putzer method 319C.3 Continuous semigroups 321References 324Index 327

"This is useful not only as review material to mathematics students, but also to students in the engineering and information sciences which may be curious about theoretically understanding the material presented before."  (Zentralblatt MATH, 1 August 2013)