Markov Chains: A Quick Review

This section is intended as a brief introductory recap of Markov chains. A much fuller explanation and introduction is provided in standard texts e.g. Norris, Bremaud, or Levin & Peres (see references below).

Introductory example: snakes and ladders

We highlight some of the key properties of Markov chains: how to calculate transitions, how the past effects the current movement of the processes, how to construct a chain, what the long run behavior of the process may (or may not) look like. We give an initial example to better position our intuition.

Below in Figure [Snakes_and_ladders], we are given a game of snakes and ladders (or shoots and ladders in the US). Here a counter (coloured red) is placed on the board at the start. You roll a dice. You move along the numbered squares by an amount given by the dice. The objective is to get to the finish. If the counter lands on a square with a snake’s head, you must go back to the square at the snakes tail and, if you land on a square at the bottom of a ladder, go to the top of the ladder.

Screenshot 2019-01-26 at 11.11.14.png

We let $X_t$ be the position of the counter on the board after the dice has been thrown $t$ times. The processes $X=(X_t: t\in {\mathbb Z})$ is a discrete time Markov chain. Two things to note: First, note that given the counter is currently at a state, e.g. on square $5$ , the next square reached by the counter – or indeed the sequence of states visited by the counter after being on square $5$ – is not effected by the path that was used to reach the square. I.e. This is called the Markov Property. Second, notice each movement of the counter from one state is a function of two pieces of information the current state and the independent random roll of the dice. In this way we can construct (or simulate) the random process.

Definitions

Let $\mathcal{X}$ be a countable set. An initial distribution

$\lambda=(\lambda_x: x\in\mathcal{X})$

is a positive vector whose components sums to one. A transition matrix $P=(P_{xy} : x,y\in\mathcal{X})$ is a postive matrix whose rows sum to one, that is, for $x\in\mathcal{X}$

$\sum_{y\in\mathcal{X}} P_{xy}=1.$

With an initial distribution $\lambda$ and a transition matrix $P$ , you can define a Markov chain. Basically $\lambda_x$ determines the probability the process starts in state $x$ Vand $P_{xy}$ gives the probability of going to $y$ if you are currently in state $x$ .

Def [Discrete Time Markov Chain] We say that a sequence of random variables $X=(X_t:t\in\mathbb{Z}_+)$ is a discrete time Markov chain, with initial distribution $\lambda$ and transition matrix $P$ if for $x_0,...,x_{t+1}\in\mathcal{X}$ ,

$\begin{aligned} \mathbb{P}(X_0=x_0)=\lambda_0\end{aligned}$

and

Screenshot 2019-01-26 at 11.16.15.png

The condition is often called the Markov property and is the key defining feature of a Markov chain or, more generally, Markov process. It states that the past $(X_1,...,X_{t-1})$ and future $X_{t+1}$ are conditionally independent of the present $X_t$ . Otherwise stated, is says that, when we know the past and present states $(X_1,...,X_t)=(x_0,...,x_t)$ , the distribution of the future states $X_{t+1}, X_{t+2},...$ is only determined by the present state $X_t=x_t$ . Think of a board game like snakes and ladders, where you go in the future is only determined by where you are now and not how you got there; this is the Markov property.

The following proposition shows that the evolution of a Markov chain can be constructed from its the current state and an independent dice throw.

Prop 1 [Constructing Markov Chains] Take a function $f:\mathcal{X}\times [0,1] \rightarrow \mathcal{X}$ , $X_0$ a random variable on $\mathcal{X}$ , and $(U_t)_{t\geq 0}$ , independent uniform $[0,1]$ random variables. The sequence $(X_t)_{t\geq 0}$ constructed with the recursion

$X_{t+1}=f(X_t,U_t) \qquad\text{ for} \quad t=0,1,2,..$

is a discrete time Markov chain. Moreover all discrete time Markov chains can be constructed in this way.

The following proposition will be useful when we want to sum up a long sequence of rewards.

Prop 2 [Markov Chains and Potential Functions] For $r:\mathcal{X}\rightarrow \mathbb{R}_+$ be a bounded function and for $\beta \in (0,1)$ ,

$R(x) = \mathbb{E}_x \left[ \sum_{t=0}^{\infty} \beta^t r(X_t) \right]$

is the unique solution to the equation

$%\label{MC:Resolve} R(x) = \beta (PR) (x) + r(x), \qquad x\in\mathcal{X}.$

Moreover, if function $\tilde{R}:\mathcal{X} \rightarrow \mathbb{R}_+$ satisfies

$\tilde{R}(x) \geq \beta (P\tilde{R}) (x) + r(x), \qquad x\in\mathcal{X}.$

then $\tilde{R}(x) \geq R(x)$ , $x\in\mathcal{X}$ .

The following is an alternative formulation of the previous proposition.

Prop 3. Let $\partial \mathcal{X}$ be a subset of $\mathcal{X}$ and let $T$ be the hitting time on $\partial\mathcal{X}$ i.e. $T=\inf\{ t : X_t \in \partial \mathcal{X}\}$ and take $f: \partial X \rightarrow \mathbb{R}_+$ then

$R(x) = \mathbb{E}_x \left[ \sum_{t<T} r(X_t) + f(X_T) \mathbb{I} \left[ T solves the equation <img title=$

There is a close connection between Markov chains and Martingales that we will want to use later when considering Markov Decision Processes.

Prop 4 [Markov Chains and Martingale Problems] Show that a sequence of random variables $X=(X_t : t\in\mathbb{Z}_+)$ is a Markov chain if and only if, for all bounded functions $f:\mathcal{X} \rightarrow \mathbb{R}$ , the process

$M^f_t = f(X_t) - f(X_0) - \sum_{\tau =0}^{t-1} (P-I)f(X_\tau)$

is a Martingale with respect to the natural filtration of $X$ . Here for any matrix, say $Q$ , we define

$Qf(x) := \sum_{y\in\mathcal{X}} Q_{xy} f(y) .$

Some references

Norris, J.R., 1997. Markov chains. Cambridge University Press.
Bremaud, P., 2013. Markov chains: Gibbs fields, Monte Carlo simulation, and queues (Vol. 31). Springer Science & Business Media.
Levin, D.A. and Peres, Y., 2017. Markov chains and mixing times (Vol. 107). American Mathematical Soc..