# Expected time of mouse's survival (stochastic matrix)

In the following wikipedia page explaining stochastic matrices, there is an example with 5 boxes and a cat and a mouse where they jump to a left or right box at every turn and it explains how to calculate the number of steps for the cat to catch the mouse.

http://en.wikipedia.org/wiki/Stochastic_matrix

My question is that at the bottom of the page, a formula is given that shows how many steps it takes starting from one of 4 possible states (inverse of I - T multiplied by 1). For instance, 2.75 means if the cat is in the box 5 and the mouse is in the box 1, then after 2.75 steps the cat catches the mouse.

Could you explain what the inverse of (I-T) is in this context? How do they come up with the formula on the right?

-
The inverse of $I-T$ is $I+T+T^2+T^3+\cdots$ – Did Mar 3 '12 at 13:44
But I would certainly not compute the mean nor the distribution of the time before lunch using T. – Did Mar 3 '12 at 16:57
Could you explain where does I-T come from in this context? And why is it I+T+T^2+T^3+...? – CEGRD Mar 4 '12 at 12:44
See answer.  – Did Mar 4 '12 at 13:57

The question is based on a Markov chain, say $(X_n)_{n\geqslant0}$, with finite state space $S$ and transition matrix $Q$, and on two states of this Markov chain, say $o$ and $e$. One is interested in $v_o=\mathrm E_o(T_e)$ where $T_e=\inf\{n\geqslant0\mid X_n=e\}$.

A productive idea in this context is to consider the quantities $v_x=\mathrm E_x(T_e)$ for every starting point $x$ in $S$ at the same time. Then $v_e=0$ and, for every $x\ne e$, conditionining on the first step $X_1$, $$v_x=1+\sum\limits_yQ(x,y)v_y.$$ This last sum is in fact restricted to $y\ne e$ since $v_e=0$ hence, introducing the matrix $T$ indexed by $S\setminus\{e\}$ defined by $T(x,y)=Q(x,y)$ for every $x\ne e$ and $y\ne e$, one gets $(I-T)V=\mathbf 1$ where $V=(v_x)_{x\ne e}$ and $\mathbf 1=(1)_{x\ne e}$.

One can check that $T^n$ converges to the null matrix when $n\to\infty$, hence $$(I-T)(I+T+\cdots+T^n)=I-T^{n+1}$$ converges to $I$, and one can imagine that the inverse of $I-T$ exists and is exactly the so-called Green matrix $G=\sum\limits_{n\geqslant0}T^n$. One is left with $V=G\mathbf 1$, in particular, $$v_o=(G\mathbf 1)_o=\sum\limits_{x\ne e}G(o,x)=\sum\limits_{x\ne e}(I-T)^{-1}(o,x)=\sum\limits_{x\ne e}\sum\limits_{n\geqslant0}T^n(o,x).$$ This is the formula in the WP page you linked to. So, everything is perfect, one simply has to write down $T$, to compute $G=(I-T)^{-1}$, to pick up the coordinates $(o,x)$ of $G$ and, to sum these over $x\ne e$, the result being the desired $v_o=\mathrm E_o(T_e)$.

...But it happens, as hinted at in the comments, that this general result is not necessary in the cat-and-mouse example. Let us see why.

As explained on the WP page, the states of the (cat,mouse) Markov chain are state $o=(1,5)$, state $u=(2,4)$, states $w'=(1,3)$ and $w''=(3,5)$, and state $e=$ cat eats mouse. The transitions of this Markov chain on $\{o,u,w',w'',e\}$ are $$p_{o,u}=1,\quad p_{u,w'}=p_{u,w''}=p_{u,o}=p_{u,e}=\tfrac14,\quad p_{w',u}=p_{w'',u}=p_{w',e}=p_{w'',e}=\tfrac12.$$ Since states $w'$ and $w''$ are equivalent, one can group them into a single state $w$. The transitions of the modified Markov chain on $\{o,u,w,e\}$ are $$p_{o,u}=1,\quad p_{u,w}=\tfrac12,\quad p_{u,o}=p_{u,e}=\tfrac14,\quad p_{w,u}=p_{w,e}=\tfrac12.$$ Applying our very first remark to this last Markov chain, one gets the system of equations $$v_o=1+v_u,\quad v_u=1+\tfrac12v_w+\tfrac14v_o,\quad v_w=1+\tfrac12v_u.$$ This is solved easily, starting from the last equation and goind backwards towards the first one: one gets $v_u=1+\frac12(1+\frac12v_u)+\frac14v_o$, that is, $(1-\frac14)v_u=1+\frac12+\frac14v_0$, which yields an equation in $v_o$ only, namely, $v_0=1+\frac43(\frac32+\frac14v_0)=1+2+\frac13v_0$.

One gets finally $v_0=\mathrm E_o(T_e)=\frac32\cdot3=\frac92$, and one sees that the explicit computation of the inverse of $I-T$ is not necessary here.

-