Introduction to Discrete Time

Consider a stochastic process which moves through a countable set I of states. At stage n, the process decides where to go next by a random mechanism which depends only on the current state, and not on the previous history or even on the time n. These processes are called Markov chains with stationary transitions and countable state space. They are the object of study in the first part of this book. More formally, there is a countable set of states I, and a stochastic process X 0 X 1 … on some probability triple (X, F, P), with X n (x) ∈ I for all nonnegative integer n and x ∈ C. Moreover, there is a function P on I × I such that $$ \mathcal{P}\left\{ {{X_{{n + 1}}} = j\left| {{X_0}, \ldots, {X_n}} \right.} \right\} = P\left( {{X_n},j} \right) $$ That is, the conditional distribution of X n +1 given X 0, . . ., X n depends on X n , but not on n or on X 0, . . ., X n -1, The process X is said to be Markov with stationary transitions P, or to have transitions P. Suppose I is reduced to the essential range, namely the set of j with P{X n = j} > 0 for some n. Then the transitions P are unique, and form a stochastic matrix. Here is an equivalent characterization: X is Markov with stationary transitions P iff $$ \mathcal{P}\left\{ {{X_n} = {j_n}\,for\,n = 0, \ldots, N} \right\} = \mathcal{P}\left\{ {{X_0} = {j_0}} \right\}\prod\nolimits_{{n = 0}}^{{N - 1}} {P\left( {{j_n},{j_{{n + 1}}}} \right)} $$ for all N and j n ∈ I. If P{X 0 = j} = 1 for some j ∈ I, then X is said to start from j or to have starting state j. This involves no real loss in generality, as one sees by conditioning on X 0.