Prerequisite: Exposure to relevant concepts at undergraduate level and instructor consent
Apart from their intrinsic role in the theory of stochastic processes, Markov chains and regenerative processes form an important set of tools for analysis and optimization problems arising in many decision models.
A quick review of calculus based probability: Random variables, joint and marginal laws, conditional expectation. Stochastic processes, notion of sample paths, finite dimensional distribution functions, Kolmogorov's consistency theorem. Time averages and laws of large numbers.
Discrete time countable state Markov chains, definitions and characterizations, hitting times, first step analysis, stopping times and strong Markov property. Recurrence and transience. Communicating classes, invariant measures for irreducible chains, positive recurrent chains, ergodic theorem. Periodic chains, convergence in variation and coupling lemma. Absorption probabilities and criterion for transience. Discrete time renewal theory, elementary renewal and renewal reward theorems. Regenerative processes and their time averages.
Jump processes; jump chain and sojourn time construction of continuous time MCs, Poisson processes, birth-death processes. Forward and backward equations. Class structure, recurrence and transience, invariant distributions, convergence to equilibrium. Uniformization and time reversed chains.
Optional topics: Conditional expectation and conditional measures, Markov processes, Brownian motion, diffusions, Martingales, etc.
- P. Bremaud, Markov chains, Gibbs fields, Monte Carlo simulation and queues, 2001, Springer-Verlag, New York
- E. Cinlar, Introduction to stochastic processes, 1975, Prentice Hall Inc., Englewood Cliffs
- W. Feller, Introduction to probability theory and its applications, Volumes 1 and 2, (1975, 1966) John Wiley, New York
- G. R. Grimmett and D. R. Stirzaker, Probability and random processes, 3rd edition, 2001, Oxford University Press
- J. R. Norris, Markov chains, 1999, Cambridge University Press, Cambridge
- S. M. Ross, Stochastic processes, 2nd Edition, 1996, John Wiley, New York
- S. Resnick, Adventures in stochastic processes, 1992, Birkhauser Verlag, Boston
- D. W. Stroock, An introduction to Markov processes, 2005, Springer-Verlag, Berlin
- R. W. Wolff, Stochastic modelling and the theory of queues, 1989, Prentice Hall Inc., Englewood Cliffs