N-Step Transition

N-Step Transition

Following up on Markov Chains Introduction

Question: If a Markov Chain is in state i at time m, what is the probability that n periods later it will be in state j?

Answer: $P({\text{X}}_{m+n}=j|{\text{X}}_m=i)=P({\text{X}}_n=j|{\text{X}}_0=i)=P_{ij}(n)$ Clearly, $P_{ij}(1)=p_{ij}$ (from the transition probability matrix P).

$$P_{ij}(2)=\sum _{k=1}^s{p}_{ij}{p}_{kj}$$

… the (i,j)-th element of ${\text{P}}^2$ Example:

t=0	t=1 odds	t=0	t=1 odds	t=0	t=1 odds
Sunny	0.7 sunny	Cloudy	0.2 sunny	Rainy	0.2 sunny
	0.2 cloudy		0.5 cloudy		0.2 cloudy
	0.1 rainy		0.3 rainy		0.6 rainy

What is probability it is sunny in 2 days when it is rainy today.

$P_{ij}(2)={\sum }_{k=1}^s{p}_{ik}{p}_{kj}=\left[\begin{array}{ccc}0.2& 0.2& 0.6\end{array}\right]\left[\begin{array}{c}0.7\\ 0.2\\ 0.2\end{array}\right]=0.3$

t=0: Rainy t=1: 0.2 sunny, 0.2 cloudy, 0.6 rainy t=2: 0.2(0.7) + 0.2(0.2) + 0.2(0.1), 0.2(0.2) + 0.2(0.5) + 0.2(0.3), 0.6(0.2) + 0.6(0.2) + 0.6(0.6) t=3: 0.2(0.7) + 0.2(0.2) + 0.6(0.2) = 0.3