# Basics on Markov Chain (for parents)

Markov chains is a very interesting and powerful tool. Especially for parents. Because if you think about it quickly, most of the games our kids are playing at are Markovian. For instance, snakes and ladders… It is extremely easy to write down the transition matrix, one just need to define all snakes and ladders. For the one above, we have,

```n=100
M=matrix(0,n+1,n+1+6)
rownames(M)=0:n
colnames(M)=0:(n+6)
for(i in 1:6){diag(M[,(i+1):(i+1+n)])=1/6}
M[,n+1]=apply(M[,(n+1):(n+1+6)],1,sum)
M=M[,1:(n+1)]
starting=c(4,9,17,20,28,40,51,54,62,
64,63,71,93,95,92)
ending  =c(14,31,7,38,84,59,67,34,19,
60,81,91,73,75,78)
for(i in 1:length(starting)){
v=M[,starting[i]+1]
ind=which(v>0)
M[ind,starting[i]+1]=0
M[ind,ending[i]+1]=M[ind,ending[i]+1]+v[ind]}```

So, why is it important to have a Markov Chain ? Because, once you’ve noticed that you had a Markov Chain game, you can derive anything you want. For instance, you can get the distribution after some turns,

```powermat=function(P,h){
Ph=P
if(h>1){
for(k in 2:h){
Ph=Ph%*%P}}
return(Ph)}
initial=c(1,rep(0,n))
COLOR=rev(heat.colors(101))
u=1:sqrt(n)
boxes=data.frame(
index=1:n,
ord=rep(u,each=sqrt(n)),
abs=rep(c(u,rev(u)),sqrt(n)/2))
position=function(h=1){
D=initial%*%powermat(M,h)
plot(0:10,0:10,col="white",axes=FALSE,
xlab="",ylab="",main=paste("Position after",h,"turns"))
segments(0:10,rep(0,11),0:10,rep(10,11))
segments(rep(0,11),0:10,rep(10,11),0:10)
for(i in 1:n){
polygon(boxes\$abs[i]-c(0,0,1,1),
boxes\$ord[i]-c(0,1,1,0),
col=COLOR[min(1+trunc(500*D[i+1]),101)],
border=NA)}
text(boxes\$abs-.5,boxes\$ord-.5,
boxes\$index,cex=.7)
segments(c(0,10),rep(0,2),c(0,10),rep(10,2))
segments(rep(0,2),c(0,10),rep(10,2),c(0,10))}```

Here, we have the following (note that I assume that once 100 is reached, the game is over) Assume for instance, that after 10 turns, your daughter accidentally drops her pawn out of the game. Here is the theoretical (unconditional) position of her pawn after 10 turns, so, if she claims she was either on 58, 59 or 60, here are the theoretical probabilities to be in each cell after 10 turns,

```> h=10
> (initial%*%powermat(M,h))[59:61]/
+ sum((initial%*%powermat(M,h))[59:61])
 0.1597003 0.5168209 0.3234788```

i.e. it is more likely she was on 59 (60th cell of the vector since we start in 0). You can also look at the distribution of the number of turns (at first with only one player).

```distrib=initial%*%M
game=rep(NA,1000)
for(h in 1:length(game)){
game[h]=distrib[n+1]
distrib=distrib%*%M}
plot(1-game[1:200],type="l",lwd=2,col="red",
ylab="Probability to be still playing")``` Once you have that survival distribution, you have the expected number of turns to finish the game,

```> sum(1-game)
 32.16499```

i.e. in 33 turns, on average, your daughter reaches the 100 cell. But in 50% of the games, it takes less than 29,

```> max(which(1-game>.5))
 29```

But assuming that you are playing with your daughter, and that the game is over once one player reaches the 100 cell, it is possible to get the survival distribution of the first time one of us reaches the 100 cell,

```plot((1-game[1:200])^2,type="l",lwd=2,col="blue",
ylab="Probability to be still playing (2 players)")``` Here, the expected number of turns before ending the game is

```> sum((1-game)^2)
 23.40439```

And if you ask your son to join the game, the survival distribution function is

```plot((1-game[1:200])^3,type="l",lwd=2,col="purple",
ylab="Probability to be still playing (3 players)")``` i.e. the expected number of turns before the end is now

```> sum((1-game)^3)
 20.02098```

## 16 thoughts on “Basics on Markov Chain (for parents)”

1. Brandon says:

Bonjour,

Quel est le nombre de coup moyen pour finir une partie si on ajoute les règles suivantes au jeu (séparément ou les deux en même temps) :

1 / “Si un joueur arrive sur une case déjà occupée par un joueur, le joueur déjà présent retourne à la case départ.”

2 / “Si un joueur arrive sur la case n°X alors il passe un tour.”

Merci.

1. Arthur Charpentier says:

bonjour
c’est plus compliqué pour le premier car il faut une chaine multivarirée dans le premier cas, mais ca reste Markovien….

2. Arthur says:

indeed… thanks !

3. Lippo says:

very nice! one question, possibly a copy-paste error:
should the plot for 2 players be plotted using (1-game[1:200])^2, and not ^3 ?

4. Nicolas says:

Ouais, vraiment un super example !!!

5. www.meneame.net says:

Las cadenas de Markov son una herramienta muy interesante y poderosa. Especialmente para los padres. Porque si piensas en ello rápidamente, la mayoría de los juegos en los que nuestros hijos estan jugando son Markovianos. Por ejemplo, el……

6. MK says:

Great post!

7. Freddy López says:

Great Arthur!! Recently I have turned to think (strongly) we have to do an effort to estimulate to our students with these type of fantastic examples… At the end, people need play with their knowledge; well, I think so… Thank you!

8. Arthur says:

Thanks Jason for the typo… unfortunately it would change all the results if I update it… so let’s keep it as it is, and we will all pretend that it is ok. By the way, I wrote another post – but in French – on optimal dice number, for each cell,
http://freakonometrics.blog.free.fr
An older post on Markov Chains in insurance (no-claim bonus)
http://freakonometrics.blog.free.fr
I have also some lecture notes – but in French – on Markov chains,
http://perso.univ-rennes1.fr/arthur

9. Lluís says:

Me too!!

I expected some basics on Markov Chains. Although it was a nice post.

Thanks

10. Jason says:

Great post. I hate to be “that guy,” but the final value in the ‘starting’ vector should be 99, not 92.

11. Claudio Shikida says:

Amazing example! Professors always have problem explaining the importance of markovian chains to students. This is a marvelous example. Just sent to my colleagues that have headache with their students when they start to explain the markov stuff…

12. Thomas says:

Bonjour
Au titre, j’espèrais trouver un mini-cours sur les chaînes de Markov, mais au final on a juste une application. Auriez-vous le temps de faire un billet sur les chaînes de Markov ?
Merci pour le blog !
T.

This site uses Akismet to reduce spam. Learn how your comment data is processed.