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.


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

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}

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},


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

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),

is the unique solution to the equation

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

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

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

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

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..

2 thoughts on “Markov Chains: A Quick Review”

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: