0

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.

MoronicHero
  • 81
  • 1
    What does this notation mean? $x = 1 + (T=0)P_{11} + (T= 1)P_{12}y + T(=2)P_{13}z+(T=3)P_{14}w$ Here you are multiplying numbers by sets. –  Oct 13 '16 at 17:27
  • Does state 1 correspond to row 1? The three states with the identity matrix (rows 2-4) should be then have minimum 1,2,3 hops respectively? Or am I misunderstanding the question? – mathreadler Oct 13 '16 at 17:27
  • @mathreadler yes – MoronicHero Oct 13 '16 at 17:29
  • @ByronSchmuland i mean that x is the expected number of steps to get to state 1 given you start in state 1. (T=0)is the case the r.v is 0. $P_{11}$ is the case that from state 1 it ends up in state 1 again, in which case 0 steps have occured... – MoronicHero Oct 13 '16 at 17:31
  • 1
    So what does the product $(T=0)P_{11}$ mean? –  Oct 13 '16 at 17:32
  • one of the values of the expectation equation for x? i'm not sure i understand. if it helps please see revised problem description for definition of T – MoronicHero Oct 13 '16 at 17:37
  • 1
    If I understand your question it should be $1\cdot 0.25+2\cdot 0.25 + 3\cdot 0.25 + 4\cdot 0.25$ I think. But it only becomes this easy because of the identity matrix. For a general matrix I think you need to consider the powers of $\bf P ; P^2, P^3, \cdots$ in some way.. – mathreadler Oct 13 '16 at 17:40
  • I have an old answer to another expectation question here where you may find something by some slight manipulation http://math.stackexchange.com/a/1912954/213607 – mathreadler Oct 13 '16 at 17:53
  • 1
    @mathreadler For a general matrix, a common technique for computing first-passage times is to modify the chain to make the target state a trapping state and then compute an expected aggregate “reward” for the modified chain. – amd Oct 13 '16 at 18:57
  • Yes or spend you could spend resources on recursively encouraging "neighbouring" elements. That has got to work. I could not imagine a configuration where it would not. – mathreadler Oct 13 '16 at 19:10

1 Answers1

2

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.$$

amd
  • 53,693