Markov chain transition matrix and state vector order?

Question

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.

Answer 1

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[1]=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