MATLAB Examples

Simulate Random Walks Through Markov Chain

This example shows how to generate and visualize random walks through a Markov chain.

Consider this theoretical, right-stochastic transition matrix of a stochastic process.

$$P = \left[ {\begin{array}{*{20}{c}}
0&0&1/2&1/4&1/4&0&0\\
0&0&1/3&0&2/3&0&0\\
0&0&0&0&0&1/3&2/3\\
0&0&0&0&0&1/2&1/2\\
0&0&0&0&0&3/4&1/4\\
1/2&1/2&0&0&0&0&0\\
1/4&3/4&0&0&0&0&0
\end{array}} \right].$$

Create the Markov chain that is characterized by the transition matrix P.

P = [ 0   0  1/2 1/4 1/4  0   0 ;
      0   0  1/3  0  2/3  0   0 ;
      0   0   0   0   0  1/3 2/3;
      0   0   0   0   0  1/2 1/2;
      0   0   0   0   0  3/4 1/4;
     1/2 1/2  0   0   0   0   0 ;
     1/4 3/4  0   0   0   0   0 ];
mc = dtmc(P);

Plot a directed graph of the Markov chain and identify classes using node color and markers.

figure;
graphplot(mc,'ColorNodes',true);

mc represents a single recurrent class of with a period of 3.

Simulate one random walk of 20 steps through the chain. Start an a random initial state.

rng(1); % For reproducibility
numSteps = 20;
X = simulate(mc,numSteps);

X is a 21-by-1 vector containing the indices of states visited during the random walk. The first row contains the realized initial state.

Plot a heat map of the random walk.

figure;
simplot(mc,X);

The return time to any state is a multiple of three.

Show the random walk through as an animation through the digraph. Specify a frame rate of 1 second.

figure;
simplot(mc,X,'FrameRate',1,'Type','graph');

Simulate 100 random walks, 50 starting from state 1, 49 starting from state 2, and 1 starting from state 6. Plot a heat map of the simulation.

x0 = [50 49 0 0 0 1 0];
X1 = simulate(mc,numSteps,'X0',x0);

figure;
simplot(mc,X1);

X1 is a 20-by-100 matrix of random walks. The first 50 columns correspond to 50 walks starting from state 1, the next 49 columns correspond to the walks starting from state 2, and the last column corresponds to the walk starting from state 6.

The three periodic subclasses are evident.

View the realized transition matrix of the 100 random walks as a heat map.

figure;
simplot(mc,X1,'Type','transitions');

Visually compare the realized and theoretical transition matrices.

figure;
imagesc(mc.P);
colormap('jet');
axis square;
colorbar;
title('Theoretical Transition Matrix')

The transition matrices appear similar.