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

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

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

and

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