You are currently browsing the tag archive for the ‘markov chain’ tag.

**Maths Games and Markov Chains**

This post carries on from the previous one on Markov chains – be sure to read that first if this is a new topic. The image above is of the Russian mathematician Andrey Markov [public domain picture from here] who was the first mathematician to work in this field (in the late 1800s).

**Creating a maths game**

Above I have created a simple maths game – based on the simplified rules of Monopoly. All players start at Go. All players roll 2 dice and add the scores and move that number of squares forward (after square 9 you move to square 1 etc). If you roll a double you get sent to Jail (square 9) – but are released on your next turn. If you land on square 5 you immediately are transported to Go (and end your turn).

The question is, if we play this game over the long run which famous mathematician will receive the most visits? (In order we have Newton (2), Einstein (3), Euler (4), Gauss (6), Euclid (7), Riemann (8)).

**Creating a Markov Chain**

The first task is to work out the probabilities of landing on each square for someone who is starting on any square. Using a sample space diagram you can work out the following:

p(move 2) = 0. p(move 3) = 2/36. p(move 4) = 2/36. p(move 5) = 4/36. p(move 6) = 4/36. p(move 7) = 6/36. p(move 8) = 4/36. p(move 9) = 4/36. p(move 10) = 2/36. p(move 11) = 2/36. p(move 12) = 0. p(double) = 6/36.

We can see that the only variation from the standard sample space is that we have separated the doubles – because they will move us to jail.

**Matrix representation**

I now need to create a 9×9 matrix which represents all the states of the game. The first subscript denotes where a player starts and the second subscript denotes where a player finishes after 1 turn. So for example m_13 denotes that a player will start on square 1 and finish on square 3, and p(m_13) is the probability that it will happen. If we do some (rather tedious!) calculations we get the following matrix:

We can note that the probability of ending up on square 5 is 0 because if you do land on it you are transported to Go. Equally you can’t start on square 5 – so the probability of starting there and arriving somewhere else is also 0. Also note that each row represents all possible states – so always adds up to 1.

Now all I need to do is raise this matrix to a large power. If I raise this to the power 100 this will give me the long term probabilities of which square people will land on. This will also give me a 9×9 matrix but I can focus on the first row which will tell me the long term probabilities of where people end up when starting at Go. This gives:

So I can see that the long term probabilities (to 3sf) show that Jail is going to be visited around 40% of the time, followed by Go (around 26.7% of the time). And the mathematician that receives the most visits will be Euclid (around 16.8%). We can logically see why this is true – if 40% of the time people are in Jail, then the next roll they are most likely to get a 7 which then takes them to this square.

**Extensions**

Clearly we can then refine our game – we could in theory use this to model the real game of Monopoly (though this would be quite complicated!) The benefit of Markov chains is that it is able to reduce complex rules and systems into a simple long term probability – which is hugely useful for making long term predictions.

**Life on the Beach with Markov Chains**

Markov chains are exceptionally useful tools for calculating probabilities – and are used in fields such as economics, biology, gambling, computing (such as Google’s search algorithm), marketing and many more. They can be used when we have the probability of a future event dependent on a current event. The image above is of the Russian mathematician Andrey Markov [public domain picture from here] who was the first mathematician to work in this field (in the late 1800s).

**Beach life**

The picture above is an example of a situation which can be modeled using a Markov chain. We have two states: Beach (state 1) and Home (state 2). In our happy life we spend all the hours of the day in either one of these two states. If we are on the beach then the probability we remain on the beach in one hour is 0.6 and the probability we go home in one hour is 0.4. If we are at home the probability we remain at home in one hour is 0.8 and the probability we go to the beach is 0.2. Hopefully you can see how this information is represented above.

**Using matrices**

First we need to represent our information in a matrix form. A general 2×2 matrix is written as:

Where the subscript tells you the row and column (e.g. a_12 tells you it is in the first row and 2nd column).

For our Markov chain we define the following matrix:

Here m_11 is the situation of starting in state 1 and moving to state 1. m_12 is the situation of starting in state 1 and moving to state 2. Therefore p(m_12) is the probability of starting in state 1 and moving to state 2. So for our beach existence we have:

The 0.6 shows that if we are already on the beach we have a 0.6 chance of still being on the beach in one hour.

**Where will we be in the future?**

The benefit of Markov chains is that they allow us to utilise computer power to now calculate where someone will be in the future – simply by taking the power of the matrix. To find the probabilities after 2 hours I can square my matrix:

Using the rules of matrix multiplication this then gives:

Which we can the calculate as:

I’ve used arrow notation here to represent the start and end state so p(m_1 arrow 1) means starting at 1 and ending at 1 after 2 hours. We can see that for someone who started in the beach, the chance of them being on the beach in 2 hours is 0.44. Equally the probability of someone who started in the house being on the beach in 2 hours is 0.28.

I can then carry on with matrix multiplication to work out where someone will likely be for any given number of hours in the future.

p(m_1 arrow 1) means starting at 1 and ending at 1 after n hours. So for example if I want to see where someone will be in 24 hours I simply do:

We can see that now it doesn’t actually matter (to 3sf anyway) where someone started – if they started on the beach there is a 0.333 chance they are on the beach in 24 hours, if they started in the house there is also a 0.333 chance they are on the beach in 24 hours. So I can conclude that as the number of hours increase towards infinity that the person in this scenario would spend 1/3 of their time on the beach and 2/3 of their time at home – not a bad life!

**A more demanding beach life**

We can see that things get much more complicated, even by adding an extra state. Now we have 3 possible states, Beach (state 1), Home (state 2) and SCUBA (state 3). This time we need a 3×3 matrix:

and as before we define our probability matrix as:

So from our diagram we have the following:

For example the 0.8 in row 2 column 2 shows that there is a 0.8 chance of starting in state 2 (Home) and ending in state 2 (Home) in one hour.

Then using our same notation we have:

Which shows that after 2 hours there is (for example) a 0.19 chance that someone who started in state 2 (Home) is now found in state 1 (Beach).

After 24 hours we have the following matrix:

So we notice the same situation as last time – as the number of hours increase it gets less important where we started from – we can see that to 3sf it doesn’t now matter where we started – the probability after 24 hours of being found on the beach is 0.407, the probability of being found at home is 0.333 and the probability of being found diving is 0.260.

Hopefully this is a quick example to demonstrate the power of Markov chains in working with probabilities. There is a lot more to explore (maybe in another post!)