- A short introduction to Markov chains for dynamic programming
- Definition, Markov Property, some Potential Theory.
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 be the position of the counter on the board after the dice has been thrown times. The processes is a discrete time Markov chain. The following exercises should be fairly straight-forward.
Ex 1 [Transition Probabilities] Given that the counter is in square we let be the probability that you next go to square . I.e.
a) b) c)
Ans 1 a) b) c) .
Ex 2 [Continued] Calculate
c) d) .
Express your answer both numerically and in terms of sum of multiples of .
(Note that many probabilities can be calculated via matrix multiplication on .)
(Nb. the fact the process started at time does not effect the probability).
(Nb. For times and states in series we just multiply entries)
d) . (Nb. We have to sum over entries for times that we miss out) (Nb. Also, note that is the entry of the matrix ).
Ex 3 [Markov property] Show that
We see that given we are on square , the probability of reaching square is not effected by the path by which we reached square .
The calculation for is very similar and is [[MC:Ladders2]] part b).
In general, given that counter is on a square we will see that the next square reached by the counter on the next turn is not effected by the path that was used to reach the square. This is called the Markov Property.
Ex 4 [Jump chain construction] Convince yourself that if you were given the current square of the Markov chain and the throw of the dice , then this completely determines the next square .
This give a method for constructing and simulating Markov chains. We just need to keep track of the current state and generate an independent random variable to determine the next state.
Ans 4 Note that this essentially says that
for some function .
Certainly there is more than one could say here. However we will cover more in future exercises with a formal definition in place.
Markov Chain Definition
Let be a countable set.
Def [Initial Distribution/Transition Matrix] An initial distribution
is a positive vector whose components sums to one. A transition matrix is a postive matrix whose rows sum to one, that is, for
Def [Discrete Time Markov Chain] We say that a sequence of random variables is a discrete time Markov chain, with initial distribution and transition matrix if for ,
The first equality above 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 and future are conditionally independent of the present . Otherwise stated, is says that, when we know the past and present states , the distribution of the future states is only determined by the present state . 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.
Ex 5 [Constructing Markov Chains] Take a function , a random variable on , and , independent uniform random variables. Construct the sequence with the recursion
Show that is a discrete time Markov chain.
Ex 6 [continued] Show that all discrete time Markov chains can be constructed in this way.
Ex 7 [Markov Chains and Martingale Problems] Show that a sequence of random variables is a Markov chain if and only if, for all bounded functions , the process
is a Martingale with respect to the natural filtration of . Here for any matrix, say , we define
Markov Chains & Potential Theory
This is really just more resolvants.
Ex 8 [Markov Chains and Potential Functions] Let be a bounded function. Argue that for
solves the equation
Ex 9 [Continued][MC:Potential1.2] Show that is the unique bounded solution this equation.
Ans 9 Take any then . So
which, since , only holds if .
Ex 10 [Continued] Show that if the bounded function satisfies
then , .
Ans 10 Suppose that is a positive fn such that . Repeated substitution gives
Ex 11 Let be a subset of and let be the hitting time on i.e. and take argue that
solves the equation
Ex 12 [Continued] Argue that
solves the equation
(Compare the above with Bellman’s equation.)