# Queen’s random walk

(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! ## 2 Answers 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). • Thank you. Typo corrected. – Anatoly Oct 20 '16 at 11:43 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.