Markov Chains

Basics

MarkovStep[K_,s_]:=RandomChoice[K[[s]]->Range[Dimensions[K][[2]]]]
MarkovChain[K_,s_,t_]:=NestList[MarkovStep[K,#]&,s,t]     (* A sample of t steps from a Markov chain with transition matrix K starting from state s *)

TransitionsOf[K_]:=Flatten[Table[If[K[[i,j]]>0,i\[DirectedEdge]j,{}],{i,Dimensions[K][[1]]},{j,Dimensions[K][[2]]}]]     (* The edges of the directed graph of probable transitions associated to the transition matrix K *)

Examples

(Subscript[RWC, 5])=(({{0, 0.5, 0, 0, 0.5}, {0.5, 0, 0.5, 0, 0}, {0, 0.5, 0, 0.5, 0}, {0, 0, 0.5, 0, 0.5}, {0.5, 0, 0, 0.5, 0}}));     (* Simple random walk on (Subscript[C, 5]) *)
(Subscript[K, 1])=(({{0.4, 0.3, 0, 0, 0.3}, {0.5, 0, 0.4, 0.1, 0.0}, {0, 0.5, 0, 0.5, 0}, {0.1, 0, 0.5, 0, 0.4}, {0.4, 0.1, 0, 0.5, 0}}));

Visualization

Active State

ActiveStateStyle[x_]:={_->Gray,x->Yellow}
MarkovActivePlot[K_,x_]:= Graph[TransitionsOf[K],VertexStyle->ActiveStateStyle[x],VertexSize->Medium]

Distribution

DistributionStateStyle[u_]:=Table[i->u[[i]],{i,1,Length[u]}]
MarkovDistributionPlot[K_,u_]:=Graph[TransitionsOf[K],VertexStyle->RGBColor[0.25,0.25,1],VertexSize->DistributionStateStyle[u]]

Example

u = {0.1, 0.2, 0.3, 0.15,0.25};

{MarkovActivePlot[(Subscript[RWC, 5]),2],MarkovDistributionPlot[(Subscript[RWC, 5]),u]}

Evolution

Evolution of the distribution

u = {0.05, 0.2, 0.35, 0.15,0.25};

Random walk on (Subscript[C, 5])

Animate[MarkovDistributionPlot[(Subscript[RWC, 5]),u.MatrixPower[(Subscript[RWC, 5]),t]],{t,0,100,1},AnimationRunning->False,AnimationRepetitions->1,AnimationRate->4]

(Subscript[K, 1])

Animate[MarkovDistributionPlot[(Subscript[K, 1]),u.MatrixPower[(Subscript[K, 1]),t]],{t,0,100,1},AnimationRunning->False,AnimationRepetitions->1,AnimationRate->4]

Evolution of the state

Random walk on (Subscript[C, 5])

(Subscript[X, 0])=3;     (* Initial state *)
T=100;   (* Number of time steps *)
X = MarkovChain[(Subscript[RWC, 5]),(Subscript[X, 0]),T];
Animate[MarkovActivePlot[(Subscript[RWC, 5]),X[[t+1]]],{t,0,T-1,1},AnimationRunning->False,AnimationRepetitions->1,AnimationRate->5]

(Subscript[K, 5])

(Subscript[X, 0])=3;     (* Initial state *)
T=100;   (* Number of time steps *)
X = MarkovChain[(Subscript[K, 1]),(Subscript[X, 0]),T];
Animate[MarkovActivePlot[(Subscript[K, 1]),X[[t+1]]],{t,0,T-1,1},AnimationRunning->False,AnimationRepetitions->1,AnimationRate->5]

Evolution of empirical distribution

Random walk on (Subscript[C, 5])

(Subscript[u, 0]) = {1, 0,0,0,0};     (* Distribution of the initial state *)
T=100;     (* Number of time steps *)
n=100;     (* Number of independent samples *)
(Subscript[XS, 0]) =RandomChoice[(Subscript[u, 0])->Range[Length[(Subscript[u, 0])]],n];     (* n independent samples from (Subscript[u, 0]) *)
XS =Table[MarkovChain[(Subscript[RWC, 5]),(Subscript[XS, 0])[[k]],T],{k,1,n}];
h = Table[Normalize[BinCounts[Transpose[XS][[t+1]],{0.5,Length[(Subscript[u, 0])]+0.5,1}],Total],{t,0,T-1}];     (* Empirical distribution of n independent runs in T consecutive steps *)
Animate[MarkovDistributionPlot[(Subscript[RWC, 5]),h[[t+1]]],{t,0,T-1,1},AnimationRunning->False,AnimationRepetitions->1,AnimationRate->4]

(Subscript[K, 5])

(Subscript[u, 0]) = {1, 0,0,0,0};     (* Distribution of the initial state *)
T=100;     (* Number of time steps *)
n=1000;     (* Number of independent samples *)
(Subscript[XS, 0]) =RandomChoice[(Subscript[u, 0])->Range[Length[(Subscript[u, 0])]],n];     (* n independent samples from (Subscript[u, 0]) *)
XS =Table[MarkovChain[(Subscript[K, 1]),(Subscript[XS, 0])[[k]],T],{k,1,n}];
h = Table[Normalize[BinCounts[Transpose[XS][[t+1]],{0.5,Length[(Subscript[u, 0])]+0.5,1}],Total],{t,0,T-1}];     (* Empirical distribution of n independent runs in T consecutive steps *)
Animate[MarkovDistributionPlot[(Subscript[K, 1]),h[[t+1]]],{t,0,T-1,1},AnimationRunning->False,AnimationRepetitions->1,AnimationRate->4]