# Probability, knight on a 5x5 chess board, expected return time.

1. May 15, 2012

### Gregg

1. The problem statement, all variables and given/known data

I have a knight on a chess board that is 5x5. I have numbered each position on the board by the amount of steps it takes from that position to get back to the centre.

It looks roughly like this

$\begin{array}{ccccc} 4 & 1 & 2 & 1 & 4 \\ 1 & 2 & 3 & 2 & 1 \\ 2 & 3 & 0 & 3 & 2 \\ 1 & 2 & 3 & 2 & 1 \\ 4 & 1 & 2 & 1 & 4 \end{array}$

I have made this into a random walk Markov chain with transition matrix.

$\left( \begin{array}{ccccc} 0 & 1 & 0 & 0 & 0 \\ \frac{1}{3} & 0 & \frac{2}{3} & 0 & 0 \\ 0 & \frac{1}{2} & 0 & \frac{1}{2} & 0 \\ 0 & 0 & \frac{2}{3} & 0 & \frac{1}{3} \\ 0 & 0 & 0 & 1 & 0 \end{array} \right)$

The question is the expected return time starting from the centre.

I have solved the set of equations

$k_i^{\{A\}} = 0, \text{ if } i\in A$
$k_i^{\{A\}} = 1+\sum_j p_{ij} k_j^{\{A\}}, \text{ if } i\in A^C$

I get

$k_0^{\{0\}} = 0$
$k_1^{\{0\}} = 11$
$k_2^{\{0\}} = 15$
$k_3^{\{0\}} = 17$
$k_4^{\{0\}} = 18$

What do I do with these?

Edit: my guess is: Since $P_{01} = 1$ the answer is $11+1=12$

If this is the case, say if there was some probability of hitting all of the other states from 0, would the expected return time be $k^{\{0\}} = 1 + \sum_{j} p_{ij} k_j^{\{0\}}$ ?

Last edited: May 15, 2012