3
$\begingroup$

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?

  • 0
    See answer. $ $2012-03-04

1 Answers 1

4

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.