Find expected amount of time it takes to get back to original state in Markov chain

888 Views Asked by At

Given irreducible PTM $ P = \begin{bmatrix} .25 & .25 & .25 & .25 \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0\\ 0 & 0 & 1 & 0\end{bmatrix}$

The stationary distribution is $[.4 .3 .2 .1]$

Given T is the minimum amount of steps it takes to return to state 1, find $E[T|X_0=1]$ $T= min\{{n>0:X_n=1}\} $ We have a system ofequations by computing the expectations conditioned on the first state $X_1$ let $x=E[T|X_0 = 1]$ $y = E[T|X_0 = 2]$ $z = E[T|X_0 = 3]$ $w = E[T|X_0 = 4]$

$x = 1 + (T=0)P_{11} + (T= 1)P_{12}y + T(=2)P_{13}z+(T=3)P_{14}w$

$y= 1 + (T=0)P_{21} + (T=1)P_{22}P_{21} + (T=2)P_{23}z$

$z= 1 + (T=0)P_{31} + (T=1)P_{32}y + (T=1)P_{33}P_{31}$

$w = 1 + (T=0)P_{41} + (T=2)P_{43}z$

Is this the right way to compute the expectations? After solving I got that $y = 1, z= 2 w=5, x = 6$ and $x$ did not tie out with being the reciprocal of $\frac{1}{.4}$ so I think I am not conditioning correctly.

1

There are 1 best solutions below

0
On BEST ANSWER

You clearly did something wrong, since $w=E[T\mid X_0=4]$ is obviously not equal to $5$.

Letting $x$, $y$, $z$, $w$ be as in the question, the system of equations should be something like $$ \begin{align}x&=1+P_{11}\cdot0+P_{12}y+P_{13}z+P_{14}w \\ y&=1+P_{21}\cdot0+P_{22}y+P_{23}z+P_{24}w \\ z&=1+P_{31}\cdot0+P_{32}y+P_{33}z+P_{34}w \\ w&=1+P_{41}\cdot0+P_{42}y+P_{43}z+P_{44}w \\ \end{align}$$ or more succinctly, $$\begin{bmatrix}x\\y\\z\\w\end{bmatrix}=P\begin{bmatrix}0\\y\\z\\w\end{bmatrix}+\begin{bmatrix}1\\1\\1\\1\end{bmatrix}.$$ This expands into $$\begin{align}x&=\frac14y+\frac14z+\frac14w+1\\y&=1\\z&=y+1\\w&=z+1\end{align}$$ with solution $y=1$, $z=2$, $w=3$ and $x=\frac52$.

For this particular matrix, the values $E[T\mid X_0=k]$ for states $k>1$ can be computed by inspection, since each of these states transitions to state $k-1$ with probability $1$, i.e., $E[T\mid X_0=k]=k-1$, so you can find $E[T\mid X_0=1]$ directly: $$P_{11}\cdot1+\sum_{k>1}P_{1k}(1+E[T\mid T_0=k]) = \frac14(1+2+3+4) = \frac52.$$