2
$\begingroup$

On a chess board, one pawn is placed on the top left square and another on the lower right square.

In this scenario, each pawn is allowed to move one square up, down, left or right where possible.

If a 'round' involves each pawn being randomly moved to a new position one square away, what is the average number of 'rounds' before the two pawns are moved to the same square?

Further, is there a general solution to this problem if it is broadened to include boards that are $n$ squares by $n$ squares, $n > 1$.

Thanks in advance.

  • 0
    Got it! Thank you. This pushes me into a branch of mathematics that I'm not yet that familiar with, which is a good thing. Regards, Brian.2012-07-02

1 Answers 1

1

Consider the graph $G$ with vertices consisting of all ordered pairs $(x,y)$ of chessboard squares, and edges $(x,y) - (z,w)$ if $x$ is adjacent to $z$ and $y$ is adjacent to $w$ by allowed pawn-moves. Then your scenario is a random walk on the graph $G$. Let $A$ be the "diagonal" set of vertices $(x,x)$. You're asking for the expected time to hit $A$ starting at a particular vertex $a$. The standard way to calculate this is as follows: let $P$ be the transition matrix for the random walk, and $R$ the submatrix for rows and columns not in $A$. Then the expected time to hit $A$, starting in each vertex not in $A$, forms the vector ${\bf V} = (I - R)^{-1} {\bf 1}$, where $\bf 1$ is the vector of all $1$'s.

EDIT: Slight complication: moves only go from black squares to white or vice versa. There are two classes of vertices, those with both squares the same colour and those with squares of different colours. Fortunately the starting position and $A$ are both in the "same colour" class, so it is possible to hit $A$ from the starting position. $R$ should be the submatrix for rows and columns not in $A$ but in the "same colour" class.