Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
2  
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
add comment

1 Answer 1

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.