A First Course in Probability and Markov Chains

5

Discrete time Markov Chains

In this chapter we give a short survey of the properties of a class of simple stochastic processes, namely, the discrete time homogeneous Markov chains with discrete states, that widely appear both in pure and applied mathematics, and have many applications in science and technology, see e.g. [11–15].

After introducing stochastic matrices in 5.1, and discrete time stochastic processes and their transition matrices, we deal with discrete time Markov chains and the Markov properties in Section 5.2. Section 5.3 is devoted to computing a few interesting parameters related to a Markov chain. Convergence of the powers of the transition matrices and the characterization of the limit in terms of return times are investigated in Sections 5.5 and 5.7. Markov chains with a finite number of states are peculiar. The canonical form of a finite stochastic matrix is presented in Section 5.4; in Section 5.5 we discuss the convergence of powers of a finite regular transition matrix, the relation between the limit and the return times and, finally, summarize the relations between the parameters introduced in Section 5.3 and the transition matrix. In Section 5.6 we deal with the ergodic property of Markov chains with an irreducible transition matrix. This eventually leads to a probabilistic method for the computation of the expected value of a random variable, known as Markov chain Monte Carlo, which plays a prominent role in numerical and statistical applications. ...