Principal Data Scientist, Practice Lead for Data Science, AI, Big Data Technologies at Teradata. O’Reilly author on distributed computing and machine learning. ​

Natalino leads the definition, design and implementation of data-driven financial and telecom applications. He has previously served as Enterprise Data Architect at ING in the Netherlands, focusing on fraud prevention/detection, SoC, cybersecurity, customer experience, and core banking processes.

​Prior to that, he had worked as senior researcher at Philips Research Laboratories in the Netherlands, on the topics of system-on-a-chip architectures, distributed computing and compilers. All-round Technology Manager, Product Developer, and Innovator with 15+ years track record in research, development and management of distributed architectures, scalable services and data-driven applications.

Sunday, January 6, 2013

Markov chains and the game of the goose


In 1640, a new board game called “Game of the goose” appeared for the first time. The game of the goose was published in Venice (Italy) by Carlo Coriandoli. The first stamp of this game represents a family sitting at the table covered with food off all kind with a big roasted goose in the center.

My kids are very fond of these board games and every one and then they would draw their own board game of the goose. They love to design the board with plenty of zombies, lasers, giant spiders, treasures and monsters of all kind.

Regularly, these self-made boards would sport at least one, sometimes two uber-traps where you need to go back to the beginning and start all over. Big deal you would say. Kind of easy to skip that evil spot and reach the end of the game, and go back to my tech ramblings on the internet.

Well, this is not actually how it goes. I have noticed that during some games many players would systematically hit the uber-trap and re-start from zero many times during the same game, for the great amusement of my little devil who has designed the board.

Doing the maths

So what makes one board design a slower or faster game then the other? Fortunately mathematics comes to the rescue. A board game can be see as a markov chain, where the probability of moving to the next spot depends only on the position you are currently at and the chances provided by tossing a dice.

For example, if you are on the third position in the board, and you roll a single 6-face dice, you might end up on the fourth position up to the nineth position. The chance to end up on any of this positions is 1/6. This can be expressed by this equation:


where i is the position I am currently at, j is the position I will reach after throwing the dice, and k in our case is an invariant, since the board game rules are always the same at any turn (you don't modify the board while you play on it).

Now, let's assume that the board has say 64 positions, where 0 is the start, and 63 is the finish.
Let's start easy and assume for the moment that there are no special positions in the game.

conceptual drawing of a 64-tile game of the goose.
Start is at position 0, the finish at position 63

The probability pi,j for the first dice roll are:
p0,1 = 1/6 , p0,2 = 1/6 , p0,3 = 1/6, p0,4 = 1/6, p0,5 = 1/6, p0,6 = 1/6

moreover:
p0,j = 0 for j =0, and for j>6

In general, since we always have to throw, we will always go on.
pii = 0 for every 0<= i <63

The only exception to this rule is p63,63 = 1

This means that you might keep throwing the dice, but nothing would happen since you reach the finish, so you stay in the finish. For common mortals this means you have won the game, for mathematicians it means that 63 is a persistant or recurrent position in the markov chain.

If we don't have any special spots is also impossible to go backward:
pij = 0 for every j <= i

Analysys of the fair game

If we all start from "start" (position zero), what is the probability to get to the finish after 1,3, 20, 100 rolls of the dice? This is the arcane that every consumed player would like to know and where the maths ultimately boils down.

First of all we need to know the full matrix of P = {pij with 0<= i,j <64 }
  • p63,63 = 1
  • pij = 0 for every 0<= j <= i  < 63
  • pij = 1/6 for every 1 <= j - i  <= 6 and i<=63-6
  • pi,63 = i-(63-6)/6 for every 1 <= j - i  <= 6 and 63-6< i<63

If the state space is finite, the transition probability distribution can be represented by a matrix, called the transition matrix, with the (i, j)th element of P equal to :


Since each row of P sums to one and all elements are non-negative, P is a right stochastic matrix.

Intuitively, in our case, after 63 rolls you will always get to the finish. Also it's impossible to get there in less than ceil(63/6) = 11  rolls. But what about the general formula? For time-invariant markov chains such as board games this is expressed by the  marginal distribution Pr(Xn = x) is the distribution over states at time n. The initial distribution is Pr(X0 = x). The evolution of the process through one time step is described by :


In particular, since we always start from the start (no cheating there eheheh), our distribution at step 0 (before rolling any dice) is a vector [1, 0, ... 0] , hence the distribution at step k can be represented by:

X = X P=  [1, 0, ... 0] PP0 j  

... i.e. the first row of the power k of the right stochastic matrix.

Thanks to Kolmogorov, we know now that the chance distribution at the step k in the game is provided simply by calculating the power of the stocastic matrix and then taking the first row.

The vector [0,0, ... , 1] is a stable chance distribution for this given game when k approaches infinity. It means that after rolling the dice really a lot of times, and supposing that there are no special positions you will and up at the finish position (duh). Therefore the stable distribution, after many many rolls, is that you will be with a probability of 1 at the finish, and with probability 0 anywhere else. In formula:


For our game, given the way we have constrcuted P, this implies that pi = [0, ....., 0, 1] is an eigenvector for the eigenvalue 1 of the stocastic matrix Pwhen k approaches infinity.


Some results of the fair game

Let's start by the first question:
How does the probability distribution look like after k dice throws?

Intuitively, after the first throw you have equal chance to end up on position 1,2,3,4,5,6 and this chance is 1/6. But the chance of ending up on position 10 on the third roll are more complex. I can roll 2, then again 2, and then 6, or 2, then 5, then 3. And so on. So basically the chance of being on a certain position after k rolls start to spread as the number of dice rolls increase.

chance of being on a certain position after k rolls
Each color displays the chance at a given turn of dice throwing.

You can see that the peak is moving on. It means that after a number of dice rolls you get closer to the end. Also not all the positions are equal. At each throw, the chance are higher that you will find yourself in a position close to the peak of the k-th curve.

Also interesting to note that the more you throw the more the probability chance curve spreads across a wider number of positions.

What about the end position?
Chance of reaching the end position after k rolls
As you can see the end position can be reached in at least 11 moves. However there is just about 1/10'000 chance that this will happen. Also, there is a very high probability (0.91) that you will finish in less than 20 rolls. Moreover, there is a very very tiny chance that you will throw 1, for 63 times in a row. Now, these are interesting results, I would say.

What about the cumulative chance of being at position 'n' during a whole game?

We are interested in understanding how probabile is to transit on a given position on the board during the entire game. This is the cumulative marginal distribution of the chance over the position on the board 'j'.

Since the game is fair, it is not possible to go backwards or to stay on the same position hence:


However the last formula hides a catch. It assumes that the events are all independent. It means that the chance of being at position j after say 10 rolls does not depend from the fact that we reached position j at the 7th roll. Is it true? In formula, can we demonstrate that:


In the fair game, the probability of being at position j after k rolls given the fact that we reach position j after h rolls,  can be broken down according to the following:

when h<k, 
then the probability after k rolls is zero, given that we have already passed the position j at roll h<k and we cannot go backwards

when k>h, 
then the probability ofter k rolls is zero, given that we will pass at position j at roll h>k and we can't stay on the same position during two different rolls.

Since the events are independent, the union of the probabilities, is the sum of the marginal probability of being at position j after 0, 1, 2, 3 ... k rolls.

Total chance of being at position 'n' during a whole game

In the fair game, there is a peak at position 6, and a small dip at the 7th after that we can conclude that the chance of being at a given position during the game is about 28%.

Already this information is quite interesting, if I would introduce a special position, say "go back to the start", there is about one chance out of four that you might fall there. If you would play this game with four people, definitely there is a quite high chance that somebody is bound to go back to the start.

Things get more interesting if the game is not fair and you introduce special spots. In this case, the cumulative chance cannot be calculated just but adding up the marginal distributing at each roll, because events can be correlated. Intuitively, this is due to the fact that you create jumps forward or backwards, potentially adding loops or multiple paths to a given position.

However, if the amount of special positions is limited, the chance distributions decay quite quickly and the correlations could still be neglected. For a formal definition of this phenomenon check the inclusion-exclusion principle wikipedia:inclusion-exclusion principle  and Boole's inequality wikipedia:boole-inequality.

Simulator!

I have fiddled out a quick simulator in javascript to let you play and design your own board game. Just add any special field by specifying where the special position leads to. Remember that 0 is the start position and 63 is the finish of the board game. If you don't enter any special position you will have the chance distribution of the fair game. Try to see what happens if you send back the players to the beginning when the fall on a the position before the end, by adding "on position 62  go to 0". Enjoy


Python coding:

If you prefer Python, I have written down a snippet using numpy and matplotlib.



Credits:

board game image: http://www.flickr.com/photos/bibliodyssey/
formula's and mathematics: http://en.wikipedia.org/wiki/Markov_chain