variance of number of steps in markov chain (rook move to top right)

1.3k Views Asked by At

I encountered this problem while studying Markov chains and I want to calculate the variance of the problem, i.e. variance of number of steps that a random walker rook make to reach from down-left square of a chess board to the top-right square for the fist time.

Update: I found the answer in wikipedia.

$$ N = (\begin{bmatrix} 1 & 0 \\ 0 & 1 \\ \end{bmatrix}-\begin{bmatrix} 6/7 & 1/7 \\ 1/2 & 3/7 \\ \end{bmatrix})^{-1}=\begin{bmatrix} 56 & 14 \\ 49 & 14 \\ \end{bmatrix} $$ Which 56+14=70 is the expected number of visits to states 0 and 1 before trapping, starting from state 0. Now for variance:

$$ t=\begin{bmatrix} 56 & 14 \\ 49 & 14 \\ \end{bmatrix} \begin{bmatrix} 1 \\ 1 \\ \end{bmatrix}=\begin{bmatrix} 70 \\ 63 \\ \end{bmatrix} \\ (2\begin{bmatrix} 56 & 14 \\ 49 & 14 \\ \end{bmatrix}-\begin{bmatrix} 1 & 0 \\ 0 & 1 \\ \end{bmatrix})\begin{bmatrix} 70 \\ 63 \\ \end{bmatrix}-\begin{bmatrix} 4900 \\ 3969 \\ \end{bmatrix}=14\begin{bmatrix} 331 \\ 328 \\ \end{bmatrix} $$

1

There are 1 best solutions below

1
On BEST ANSWER

The technique used to solve the other question shows that the generating function of the number of steps $T$ is such that $$E((1-s)^T)=\frac{(1-s)^2}{1+68s+29s^2},$$ from which the expansion of the RHS up to order $s^2$ yields $E(T)=70$ and $E(T^2)=9534$, hence $$\mathrm{var}(T)=4634.$$