Find expected value of time to reach a state in Markov chain, by simulation

Question

Consider a time homogeneous Markov chain $ (X_n)_{n=0} $ with state space $E$, initial distribution $p(0)$ and transition probability matrix $P$ given by $E = \{0, 1, 2\}, p(0) = [1\;\; 0\;\; 0]$ and

P= $\begin{bmatrix}1/2 & 1/3 & 1/6\\0 & 2/3 & 1/3 \\0 & 0 & 1 \end{bmatrix}$

respectively. Find by a computer simulations an as good as is possible approximation of the expected value $\Bbb E(T)$ of the time $T = \min\{ n ∈ N : X_n = 2 \}$ it takes the chain to reach the state 2. Someone who can help me in doing some kind of pseudocode for this question, or some matlab code?

Answer 1

Probably easier for you to understand R than mathematica if you know matlab.

Ask if you dont understand what im doing.

Here is the code in R:

N = 10^4

T<-vector(length=N)

ptm <- proc.time()

for (k in 1:N) {
  i<-0
  X<-0


    while (X==0) {
    u=runif(1)


       if (1/6<u & u<1/2) {X<-1}
       else if (u<1/6) {X<-2}
       else {X<-0}

       i <- i+1
    }   

    while (X==1) {
    u=runif(1)

       if (u<1/3) {X<-2}

       i <- i+1
    }

# Done Save

T[k]<-i

}

 print(proc.time()-ptm)

 mean(T)

Answer 2

Let $\psi(i)$ be the expected time to reach state 2 from state i, where i ={0,1,2}.

Then $\psi(2) =0$

$\psi(1) = 1+ \frac{2}{3}\psi(1)+\frac{1}{2}\psi(2)$

$\psi(0) = 1+\frac{1}{2}\psi(0)+\frac{1}{3}\psi(1)+\frac{1}{6}\psi(2)$

Solve the system to find $\psi(0)$

The initial state is 0 and the expected time to reach state 2 from 0 is $\boxed{4}$

Answer 3

In Mathematica:

myP = {{1/2, 1/3, 1/6}, {0, 2/3, 1/3}, {0, 0, 1}};

ListPlot[Transpose[NestList[#.myP &, {1, 0, 0}, 10]], 
 AxesLabel -> {"step", "Probability"},
 Joined -> True,
 PlotLegends -> {"P[0]", "P[1]", "P[2]"} ]

The successive differences in probabilities for being in state $2$ are:

difProbs = Differences@NestList[#.myP &, {1, 0, 0}, 100][[All, 3]];

The expected value is:

N@Range[100].difProbs

(* 4 *)