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])
[1] 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)
[1] 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))
[1] 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)
[1] 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)
[1] 20.02098

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

  1. 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.

  2. 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 ?

  3. Conceptos básicos de cadenas de Markov (para padres) [EN]

    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……

  4. 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!

  5. 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

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

  7. 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…

  8. 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.

Leave a Reply

Your email address will not be published. Required fields are marked *