Markov Chain Probability


Markov chain problems frequently come up in quantitative finance interview processes. In this lesson, we’ll explore what Markov chain probability is and walk through a typical Markov chain problem you might encounter.

Introduction to Markov Chain Probability

A Markov chain is a sequence of random variables with the property that given the present state, the future states and the past states are independent. In other words, in case the current state is known, the past states do not affect the future. Think for example about a cube. An ant is starting at a specific corner of the cube and it tries to reach the exact opposite corner of the cube by only walking straight to neighbor corners. It takes an ant a second to walk a side. A problem statement – containing a Markov chain – could be to compute the expected amount of time that the ant is walking before it reaches the opposite corner. The ant is moving randomly to one of either three neighbor corners. Past choices do not affect the next choice of the ant, which makes this a Markov chain problem. This section will elaborate on the Markov chain.

In case the problem contains a finite-state Markov chain with n-states, then the Markov chain can be described by an Quicklatex. Com d4a1ca8ee7fa73129a56b7f59a0d6c2d l3transition matrix P, given by Equation 1.

(1)   Quicklatex. Com c91fd168fb50cf22186f5f966420bd76 l3

where Quicklatex. Com 1c60c5f54b09e6cc9cfd44e36b4bcf9c l3 is the transition probability from state Quicklatex. Com 7f18e477a2aad0c34133fd11bbc363c6 l3 to state Quicklatex. Com e8518dc0300a20f271c3d1ba6cfe4c58 l3. Although a transition matrix Quicklatex. Com 10ed09194eeff311e056f144d59cb509 l3 already gives an overview of the possible paths, a transition graph makes it even more clear. All the possible and impossible transitions are easy to recognize in a transition graph. 

Markovchart
Figure 1 – Markov chain transition graph.

The corresponding transition matrix would be:

(2)   Quicklatex. Com ae482e274d49f02828b2ad82c19c76d5 l3

In the transition graph, we can see which state is accessible from which state(s). For example, state 4 is not directly accessible from state 1, because one has to apply first for the function before the applicant gets the offer. When two state are mutually accessible, then those state communicate. For example, states 2 and 3 do communicate, as do 1 and 2. State 4 is accessible from state 3, but does not communicate with state 3. A state Quicklatex. Com 7f18e477a2aad0c34133fd11bbc363c6 l3 is recurrent if for every state Quicklatex. Com e8518dc0300a20f271c3d1ba6cfe4c58 l3 that is accessible from Quicklatex. Com 7f18e477a2aad0c34133fd11bbc363c6 l3, Quicklatex. Com 7f18e477a2aad0c34133fd11bbc363c6 l3 is also accessible from Quicklatex. Com e8518dc0300a20f271c3d1ba6cfe4c58 l3. A state is called transient when it is not recurrent. 

In every problem statement, we are looking for a certain answer. This answer should be the end of the Markov chain, also called the absorbing state. It is impossible to leave this state. In the example with the ant, the absorbing state is when the ant reached the exact opposite corner with respect to the corner from where it started. In the transition graph above, the absorbing state is state number 4. In this case it is assumed that one does not continue with looking for another job after the applicant gets a job offer in trading.

The problem statement could either aim for the probability to reach a specific absorbing state or for the expected number of steps or amount of time before reaching the absorption state. The equation to solve this problem can be derived from the law of total expectation. 

Let’s first elaborate on the probability to reach a specific absorption state Quicklatex. Com 071cc0f9414a59a322f3c965156eca54 l3. All states are denoted by Quicklatex. Com c2397fcb97b1979e76e93773c6d9a4e0 l3 for Quicklatex. Com 1a4ab2c48a7665fe6d7d713367f396f9 l3-states. The absorption state Quicklatex. Com d18e7266f97ee76176040cefb4cdef3e l3, and all other states are equal to zero. For every transient state Quicklatex. Com 7f18e477a2aad0c34133fd11bbc363c6 l3 we have the equation

(3)   Quicklatex. Com 897cde56af9419bca2c5cedd1e383f8c l3

The equation to solve the number of steps Quicklatex. Com de39b480e0c000ddb2eb10d3fc34c661 l3 before reaching the absorption state is slightly different. Here, the absorption state Quicklatex. Com cbf6738d653bb05ee5a8d2d7021da53b l3. For every transient state Quicklatex. Com 7f18e477a2aad0c34133fd11bbc363c6 l3 we have the equation 

(4)   Quicklatex. Com 0427f96c0a242c4a88ef6b264937b84d l3

These equations can be solved by writing out the equation from the starting point. Note: the ‘1’ in this question stands for each new step that has to be taken to go to the next state. If we would have been talking in terms of time, for example seconds, the ‘1’ in this equation could be replaced by the number of seconds that it takes to reach a next stage.

Example of a Markov Chain Problem

Example: The ant starts at a specific corner of a cube and tries to reach the exact opposite corner of the cube. It only walks directly to neighbor corners with an equal probability, 1/3. Every time the ant travels to the next corner, a second passes. What is the expected number of seconds that it takes the ant to reach the exact opposite corner?

Solution: First start with numbering all corners to get a clear overview of all states. The ant starts at Quicklatex. Com 6d328cd15fca358a96df198d9d63dde6 l3 and wants to reach Quicklatex. Com 071cc0f9414a59a322f3c965156eca54 l3.

Cubemc
Figure 2 – Imagination of the cube.

Now we can start writing out all state equations:

(5)   Quicklatex. Com 33171af9cfb6e7d9467c8498f9ca6843 l3

(6)   Quicklatex. Com e345fb5a514e90884fe358f034fcd59e l3

(7)   Quicklatex. Com be01933f42bbc5f3ea9140761cde61a5 l3

Quicklatex. Com 071cc0f9414a59a322f3c965156eca54 l3 is equal to zero as we explained before. We can now substitute Quicklatex. Com 1b90afa533029900ead1f3be20f24777 l3 in Quicklatex. Com 0592f30b2eb1ff8da90cd3cf0036881e l3. This gives us:

(8)   Quicklatex. Com 3f76993b09f2f17cad2b612b5b780007 l3

(9)   Quicklatex. Com 988b5aea4a043410ac4b9fbee7f199e7 l3

(10)   Quicklatex. Com 787a9d90f7cdbf003177f7b971a95e03 l3

Now we can substitute Quicklatex. Com 0592f30b2eb1ff8da90cd3cf0036881e l3 in Quicklatex. Com 6d328cd15fca358a96df198d9d63dde6 l3:

(11)   Quicklatex. Com 9cd2b38a6cb05054f1e1b78fc5f06695 l3

(12)   Quicklatex. Com 3b0f2dee9769165bdb1b30c1f892a23c l3

(13)   Quicklatex. Com d86615e17fc44fc5e579888ede053db7 l3

In other words, the expected time that it takes the ant to reach the corner in the exact opposite corner is equal to ten seconds. Other problems and solutions can be found in de exercises section.