2
$\begingroup$

(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!

$\endgroup$
3
$\begingroup$

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).

$\endgroup$
  • $\begingroup$ Thank you. Typo corrected. $\endgroup$ – Anatoly Oct 20 '16 at 11:43
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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