# Math Help - Markov chain

1. ## Markov chain

Hi, can you help me with this problem, please?
I have tried but I am not sure what to do exactly...
Yn - sum of n independent rolls of a fair die.
Find lim P{Yn is a multiple of 13), n->inf

How can I define the appropriat Markov chain?
I know that after defining it I can use the limiting probability

If you can help me with this will be greatly appreciated.

Thank you!

2. Originally Posted by bamby
Hi, can you help me with this problem, please?
I have tried but I am not sure what to do exactly...
Yn - sum of n independent rolls of a fair die.
Find lim P{Yn is a multiple of 13), n->inf

How can I define the appropriat Markov chain?
I know that after defining it I can use the limiting probability

If you can help me with this will be greatly appreciated.

Thank you!
Let the state be $X_n$ be the value of $Y_n \text{ mod } 13$

and distribution vector $(x_{n,0},x_{n,1},\ ..\ ,x_{n,12})$

where $x_{n,i}=Pr(Y_n \equiv i \text{ mod } 13)$.

Now write the transition matrix for this process.

CB

3. But that is the point - I don't know the transititon matrix.
I know that the multiples of 13 are i mod 13

4. Originally Posted by bamby
But that is the point - I don't know the transititon matrix.
I know that the multiples of 13 are i mod 13
The point is that if you throw a single dice you may assume that each of the faces comes up with probability 1/6 and the faces show the values 1,2,3,4,5,6.

From that you can work out the transition matrix.

So if $X_n=8$, then:

$X_{n+1}=9$ with prob $1/6$,

$X_{n+1}=10$ with prob $1/6$,

$X_{n+1}=11$ with prob $1/6$,

$X_{n+1}=11$ with prob $1/6$,

$X_{n+1}=0$ with prob $1/6$,

$X_{n+1}=1$ with prob $1/6$.

CB

5. So, I have got for the transition matrix

A=[0 1/6 1/6 1/6 1/6 1/6 1/6 0 0 0 0 0 0;
0 0 1/6 1/6 1/6 1/6 1/6 1/6 0 0 0 0 0;
0 0 0 1/6 1/6 1/6 1/6 1/6 1/6 0 0 0 0;
0 0 0 0 1/6 1/6 1/6 1/6 1/6 1/6 0 0 0;
0 0 0 0 0 1/6 1/6 1/6 1/6 1/6 1/6 0 0;
0 0 0 0 0 0 1/6 1/6 1/6 1/6 1/6 1/6 0;
0 0 0 0 0 0 0 1/6 1/6 1/6 1/6 1/6 1/6;
1/6 0 0 0 0 0 0 0 1/6 1/6 1/6 1/6 1/6;
1/6 1/6 0 0 0 0 0 0 0 1/6 1/6 1/6 1/6;
1/6 1/6 1/6 0 0 0 0 0 0 0 1/6 1/6 1/6;
1/6 1/6 1/6 1/6 0 0 0 0 0 0 0 1/6 1/6;
1/6 1/6 1/6 1/6 1/6 0 0 0 0 0 0 0 1/6;
1/6 1/6 1/6 1/6 1/6 1/6 0 0 0 0 0 0 0]

and for the limit I raised it A^30 and got 0.0769
Is that correct?

Thank you so much!

6. Originally Posted by bamby
So, I have got for the transition matrix

A=[0 1/6 1/6 1/6 1/6 1/6 1/6 0 0 0 0 0 0;
0 0 1/6 1/6 1/6 1/6 1/6 1/6 0 0 0 0 0;
0 0 0 1/6 1/6 1/6 1/6 1/6 1/6 0 0 0 0;
0 0 0 0 1/6 1/6 1/6 1/6 1/6 1/6 0 0 0;
0 0 0 0 0 1/6 1/6 1/6 1/6 1/6 1/6 0 0;
0 0 0 0 0 0 1/6 1/6 1/6 1/6 1/6 1/6 0;
0 0 0 0 0 0 0 1/6 1/6 1/6 1/6 1/6 1/6;
1/6 0 0 0 0 0 0 0 1/6 1/6 1/6 1/6 1/6;
1/6 1/6 0 0 0 0 0 0 0 1/6 1/6 1/6 1/6;
1/6 1/6 1/6 0 0 0 0 0 0 0 1/6 1/6 1/6;
1/6 1/6 1/6 1/6 0 0 0 0 0 0 0 1/6 1/6;
1/6 1/6 1/6 1/6 1/6 0 0 0 0 0 0 0 1/6;
1/6 1/6 1/6 1/6 1/6 1/6 0 0 0 0 0 0 0]

and for the limit I raised it A^30 and got 0.0769
Is that correct?

Thank you so much!
Well it looks OK (but it can be dificult to be sure as there are two conventions for the matrix).

An alternative is to look at the solution of the equation:

$xA=x$

then the answer required is $x_1$.

CB