1
$\begingroup$

Consider a discrete-parameter Markov chain $\{X_n, n ≥ 0\}$ with state space $E$, transition probability matrix $P$ and initial-state probabilities $p(0)$ given by $E = \{0, 1, 2, 3\}$,

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

and $p(0) =(0\;\; 0\;\; 0\;\; 1)$. How can one simulate an observation $X_{10}$ of the chain at time $n = 10$?

$\endgroup$
  • 2
    $\begingroup$ Have you considered to take the probability of moving from state $4$ to state $j, \, j\in E$ in $n$ steps? I.e., $P_{3j}^{(10)}$, which is the $3j$ entry of $P^{10}$? $\endgroup$ – V. Vancak Dec 15 '15 at 22:31
  • 1
    $\begingroup$ Indeed, the probability distribution at time $10$ will be given by the last row of $P^{10}$. So you can just sample from that. $\endgroup$ – Ian Dec 15 '15 at 22:33
  • 1
    $\begingroup$ @Ian Is that really a simulation? The last row of $P^{10}$ isnt that the exact probability distribution of $X_{10}$? That doesnt seem like much of a simulation. Isnt OPs question more about learning a simulation technique for more complicated problems? (Im probably way off tho...im still far from knowing even the theory) $\endgroup$ – JKnecht Dec 18 '15 at 22:59
  • 1
    $\begingroup$ @JKnecht The distribution of outcomes is the same either way. The only difference is whether you get to compute trajectories. $\endgroup$ – Ian Dec 19 '15 at 1:33
  • $\begingroup$ It was a couple of weeks after this was posted.that I posted R code for the requested simulation. Please let me know current status of this question for you. Do you understand method and purpose of simulation? $\endgroup$ – BruceET Dec 28 '15 at 17:25
3
$\begingroup$

For simplicity in simulation, I have changed the sample space to $E = \{1,2,3,4\}.$ With this notation, notice that there will be a last visit to 'transient' state 4. On each visit to state 4 there is a 50-50 chance of movement to state 1 or 2, and no possibility of return to state 4 from there. So by simulating $X_{10}$ repeatedly, you're checking how likely the chain can still visit state 4 after the tenth transition, and how likely it is that the chain has gotten 'absorbed' into 'persistent' states 1 and 2 by then.

In order to simulate the first ten $transitions$ of the chain repeatedly as required, you need to know how to do the simulation once. Here is such a simulation using R statistical software. We begin by entering the transition matrix $P$ and then using it for simulation. (The transition matrix $P$ can be written on a single line, but it is easier to visualize as entered below.

 P = (1/4)*matrix(c(0,4,0,0,
                    4,0,0,0,
                    0,0,2,2,
                    1,1,1,1), nrow=4, byrow=T)

 m = 11  # number of steps simulated
 x = numeric(m); x[1] = 4  # null 11-vector; chain starts in state 4.
 for (i in 2:m) {
   x[i] = sample(1:4, 1, prob=P[x[i-1],])   # applicable row of P used
}
x
## 4 2 1 2 1 2 1 2 1 2 1

Two additional runs give

## 4 3 4 3 3 4 1 2 1 2 1
## 4 4 4 2 1 2 1 2 1 2 1

Now, for $B = 100,000$ simulations of the state visited after 10 transitions, we wrap an outer loop around the program above.

 P = (1/4)*matrix(c(0,4,0,0,
                    4,0,0,0,
                    0,0,2,2,
                    1,1,1,1), nrow=4, byrow=T)
 B = 100000;  PATH = matrix(0, nrow=B, ncol=11)
 for (j in 1:B)  {
   m = 11  # number of steps simulated
   x = numeric(m); x[1] = 4  # (initially null) 11-vector; chain starts in state 4.
   for (i in 2:m) {
     x[i] = sample(1:4, 1, prob=P[x[i-1],])   # applicable row of P used for sim
   }
 PATH[j,] = x
 }
 table(PATH[,11])/B

 ##       1       2       3       4 
 ## 0.48006 0.48189 0.01855 0.01950 
 P10[4,]
 ## 0.48122883 0.48122883 0.01877117 0.01877117

The last row of $P^{10}$ shown above is found by matrix multiplication (code not shown). As suggested in the Comments by @Ian and @user230329 there is very good agreement with the simulation results.

An advantage of capturing all of the steps visited in the matrix PATH is that a similar comparison can be made for results after four transitions:

 table(PATH[,5])/B

 ##       1       2       3       4 
 ## 0.39295 0.39473 0.10562 0.10670 
 P4[4,]
 ## 0.3945313 0.3945313 0.1054688 0.1054688

Here we see that already after only just a few steps the chain has more likely than not moved from the transient states to the persistent ones.

My guess is that the reason you were asked to do some simulation is to develop intuition how the chain moves. Perhaps soon in your continuing study of Markov chains you will see analytic formulas for the mean time spent in various transient states before 'absorption' into the persistent states.

$\endgroup$
  • 1
    $\begingroup$ Great post. Very useful for me. I did a simulation of this using uniform random variables but this is much better and a lot easier to apply to more complex problems. $\endgroup$ – JKnecht Jan 2 '16 at 22:41
  • $\begingroup$ @JKnecht: Ultimately, of course, most simulations are based on Unif(0,1) pseudorandom numbers. (So you can say most simulations actually take place inside a B-dim hypercube.) Certainly, the 'sample' function in R is based in Unif(0,1). But 'sample' is enormously useful for a wide range of applications. Some of them, incl. Markov chains, perhaps not immediately obvious. maybe also see roughly related post at math.stackexchange.com/questions/1595606. $\endgroup$ – BruceET Jan 6 '16 at 18:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy