Queen’s random walk

Question

(Queen’s random walk). A queen can move any number of squares horizontally, vertically, or diagonally. Let Xn be the sequence of squares that results if we pick one of queen’s legal moves at random.

$(a)$ Find the stationary distribution

$(b)$ Find the expected number of moves to return to corner $(1,1)$ when we start there .

So the answer is $\sum_{x∈S} deg(x)$$ = 1452$, and for the corner $deg(x) = 21$. expected number of moves to return to the corner $≈ 69.14.$

But there are no steps to the answer. I really appreciate if you could show me how to get to the answer, thanks!

Answer 1

The stationary distribution is defined as the normalized number of moves from a given position. In symbols, for a given position $x $ it is $\frac {deg (x)}{\sum_{x∈S} deg(x)}$, where $deg $ indicates the number of possible moves from $x $.

For a queen on a chessboard, if it is on any of the $28$ squares adjacent to the outer edge (including corners), there are $21$ possible moves ($7$ ranks, $7$ files and $7$ diagonals). If it is on any of the $20$ squares that are in the second concentric frame (i.e., all squares separated from the outer edge by one square), there are $23$ possible moves (because there are two additional diagonal moves). If it is on any of the $12$ squares that are in the third concentric frame (i.e., all squares separated from the outer edge by two squares), there are $25$ possible moves (because there are two further additional diagonal moves). Lastly, if the queen is on one of the 4 central squares, there are $27$ possible moves (again two further additional diagonal moves). So we have for the corner $deg (x)=21$ and for the total chessboard $$\sum_{x∈S} deg(x)= 28 \cdot 21 + 20 \cdot 23 + 12 \cdot 25 + 4 \cdot 27 = 1456$$

which leads to an expected number of moves of $1456 /21\approx 69.3$ to return to the corner.

Note that, in my opinion, the values of $1452$ (instead of $1456$) and the resulting $69.14$ (instead of $69.3$), both provided in the solutions that you cite, might be the result of a typo (the value of $1456$ is well established for problems on Queen random walks).

Answer 2

Here is a slightly easier way to calculate the sum $\sum_{x\in S}\deg(x)$ which, by the handshaking lemma, is equal to twice the number of edges in the queen's graph. In the $8\times8$ queen's graph, we have

Horizontal edges: $8\binom82=224$ of them, $\binom82$ on each row.

Vertical edges: likewise $224$ of them.

Diagonal edges with positive slope: $$\binom12+\binom22+\binom32+\binom42+\binom52+\binom62+\binom72+\binom82+\binom72+\binom62+\binom52+\binom42+\binom32+\binom22+\binom12=\binom82+2\binom83=140.$$ Diagonal edges with negative slope: another $140.$

The total number of edges is $224+224+140+140=\boxed{728}\ ,$
and so $\sum_{x\in S}\deg(x)=2\cdot728=\boxed{1456}\ .$

More generally, for the $m\times n$ queen's graph (queen moves on an $m\times n$ chessboard) where $m\ge n,$ the number of edges is $$m\binom n2+n\binom m2+2\left[(m-n+1)\binom n2+2\sum_{k=1}^{n-1}\binom k2\right]$$ $$=m\binom n2+n\binom m2+2(m-n+1)\binom n2+4\binom n3$$ $$=\boxed{(3m-2n+2)\binom n2+n\binom m2+4\binom n3}\ .$$ When $m=n$ this simplifies to $$(2n+2)\binom n2+4\binom n3=\boxed{\frac{n(n-1)(5n-1)}3}$$

which is OEIS sequence A144945.