# Markov chain transition matrix and state vector order?

The typical way of performing state simulations using matrices is to perform the following kind of calculation:

$$x_{(k+1)}=Ax_{(k)}$$

However,

When the transition matrix $A$ is defined in the following way for example:

$$\begin{array}{r|lll} & \rlap{\text{next state}} \\ \text{current state} & 1 & 2 & 3 \\ \hline 1 & 0.5 & 0.5 & 0 \\ 2 & 0.8 & 0 & 0.2 \\ 3 & 0.9 & 0 & 0.1 \\ \end{array}$$

Then doing the above iteration with e.g. initial $x_0=\begin{bmatrix} 1&0&0 \\ \end{bmatrix}^T$, then

$$Ax_{(k)}=\begin{bmatrix} 0.5&0.8&0.9 \\ \end{bmatrix}^T$$

which is not the right calculation. The right one should result in

$$Ax_{(k)}=\begin{bmatrix} 0.5&0.5&0 \\ \end{bmatrix}^T$$

I.e. what should be calculated is actually

$$x_{(k+1)}=\begin{bmatrix} 1&0&0 \\ \end{bmatrix} A$$

What should I do in order to perform calculations in the form of

$$x_{(k+1)}=Ax_{(k)}$$

Transpose $A$? But isn't this then an unconventional way of expressing the transition matrix?

What I could also calculate is

$$x_{(k+1)}=x_{(k)}A$$

as given here.

• The formula provided in the slides you link to is for the probability, not for the state. Could you clarify your notations (or else point out how I misunderstood the question in my answer)? Thank you. – Xi'an Nov 22 '16 at 10:44
• @XI'an I'm simulating the probabilities. – mavavilj Nov 22 '16 at 12:39
• Then simulating is the wrong word: it should be computing, in which case the formula $p_{(k)}A$ is correct provided you write the probability vector as a row vector. – Xi'an Nov 22 '16 at 12:41

The typical way of performing state simulations using matrices is to perform the following kind of calculation: $$x_{(k+1)}=Ax_{(k)}$$

This is not correct. The Markov transition matrix $A$ should be handled by matrix algebra to compute the distribution of the chain after one or $n$ steps of the Markov transition, rather than to simulate the value of the next realisation of the Markov chain since randomness must be involved.

For instance, if the initial distribution is $$\mathbb{P}(X_{(0)}=x)=p_{(0)}=(0.5\ 0.0\ 0.5)$$the (marginal) distribution of $X_1$ is $$p_{(0)}A$$and the (marginal) distribution of $X_n$ is $$p_{(0)}A^n$$As an illustration in R, take

p0=c(0.5,0,0.5)
A=matrix(c(.5,.8,.9,.5,0,0,0,.2,.1),ncol=3)
p1=p0%*%A
pn=p0;for (i in 1:n) pn=pn%*%A


Formally, if one writes $x_{(k)}$ as a row vector of indicators, $\check x_{(k)}=(\mathbb{I}_{x_{(k)}=1},\ldots,\mathbb{I}_{x_{(k)}=p})$ then$$\check{x}_{(k)} A$$provides the probability distribution of $x_{(k+1)}$.

When interested in simulating the Markov sequence $(x_{(n)})$ the simulation must be sequential and use the current value of the chain, $x_{(n)}$, to index the row of $A$ setting the probability distribution for the next value, $x_{(n+1)}$, as in this R example:

T=1e6
x=rep(0,T)
x=sample(1:3,1)#random start
for (t in 2:T)
x[t]=sample(1:3,1,prob=A[x[t-1],])


and one can check that the frequencies stabilise at the predicted values:

> table(x)/T
x
1        2        3
0.620685 0.310545 0.068770
> pn
[,1]      [,2]       [,3]
[1,] 0.6206897 0.3103448 0.06896552