35
$\begingroup$

Someone asked a question about self-avoiding random walks, and it made me think of the following:

Consider a piece that starts at a corner of an ordinary $8 \times 8$ chessboard. At each turn, it moves one step, either up, down, left, or right, with equal probability, except that it must stay on the board, of course, and it must not return to a square previously visited.

Clarification. On any given step, if the piece has $n$ available moves (excluding those that would put the piece on a previously visited square), it chooses randomly and uniformly from those $n$ moves. Example: Starting from a corner, at first move, $n = 2$, and either move is chosen with probability $1/2$. Next move, $n = 2$ also, because it cannot return to the corner, and so either of the two other moves are chosen with probability $1/2$. On the third move, if it is on the edge, $n = 2$, while if it is off the edge, $n = 3$. And so on.

It is possible for the piece to be deadlocked at some point prior to completing a tour of the chessboard. For instance, if it starts at lower left, and moves up, right, right, down, left, it is now stuck.

What is the probability that it completes the tour? Is there a method that answers this question besides exhaustive enumeration? What about $n \times n$ chessboards for $n \geq 3$? (The problem is trivial for $n = 1$ or $2$.)


Analysis for $n = 3$, as another clarification:

Let the chessboard be labelled $(1, 1)$ through $(3, 3)$, and the piece starts at $(1, 1)$. Without loss of generality, the piece moves to $(2, 1)$. Then:

  • With probability $1/2$, the piece moves to the center square $(2, 2)$ on its second move. From there, only one move permits completion of the tour—the move to $(1, 2)$—and in that case, the tour is guaranteed to complete. This move is chosen with probability $1/3$.

  • With probability $1/2$, the piece moves to $(3, 1)$ on its second move. It is then forced to move to $(3, 2)$.

    • With probability $1/2$, it then moves to $(3, 3)$ on its fourth move and is guaranteed to complete the tour.

    • Otherwise, also with probability $1/2$, it moves to the center square $(2, 2)$ on its fourth move. From there, it moves to $(1, 2)$ with probability $1/2$ (and is then guaranteed to complete the tour), or to $(2, 3)$ also with probability $1/2$ (and is then unable to complete the tour).

Thus, the probability of completing the tour on a $3 \times 3$ board is

$$ p_3 = \frac{1}{2} \times \frac{1}{3} + \frac{1}{2} \times \left( \frac{1}{2} + \frac{1}{2} \times \frac{1}{2} \right) = \frac{1}{6} + \frac{3}{8} = \frac{13}{24} $$


Update. An exhaustive enumeration in floating point yielded the following:

For $n = 8, p_n = 0.000006751027716$

$\endgroup$
  • $\begingroup$ @Nikunj The question isn't whether the tour is possible (it obviously is), it's about the probability that a series of random movements completes the tour. $\endgroup$ – DylanSp Mar 3 '16 at 20:54
  • $\begingroup$ @DylanSp and that is why I deleted my comment right after posting, but somehow it is magically still there :P $\endgroup$ – Nikunj Mar 3 '16 at 20:55
  • $\begingroup$ You could rephrase the problem as "the probability that a self-avoiding random walk on a grid is an hamiltonian path". $\endgroup$ – Graffitics Mar 3 '16 at 21:57
  • 2
    $\begingroup$ @String: You are right: computing the probabilities is as easy as counting the number of paths. I can confirm your results: $p(3)=13/24$, $p(4)=487/3456$, $p(5)= 621\,799/23\,887\,872$ and $p(6)= 3\,764\,115\,767/1\,486\,016\,741\,376$. $\endgroup$ – Aretino Mar 4 '16 at 14:34
  • 1
    $\begingroup$ This might be remotely relevant? arxiv.org/pdf/1607.02433 . See the self-avoiding edge-covering sections. One would need to transform their "edge" into vertices which in turn shall be transformed into your `chess board position'. $\endgroup$ – Lee David Chung Lin Sep 30 '16 at 9:50
2
$\begingroup$

Let’s solve a more general version of your problem:

Suppose a piece stands in the vertice $v$ of a graph $G = (V, E)$. At each turn, it moves along any edge starting from the vertex it is in currently, with equal probability, except that it must not return to a vertex previously visited.

Let’s denote such probability as $P(G, v)$, then the problem is solved by the recurrent formula:

$$P(G, v) = \begin{cases} 1 & \quad |V| = 1 \\ \frac{\Sigma_{(v, w) \in E} P(G\setminus v, w)}{deg(v)} & \quad |V| > 1 \end{cases}$$

Here $G\setminus v$ stands for a graph that is constructed by removing $v$ and all adjacent edges.

Using that formula the exact probability can always be calculated.

And the probability for $n \times n$ chessboard from your initial question is calculated by this wee piece of code in Python (which is the direct implementation of the aforementioned formula):

import numpy
from fractions import Fraction

def rec(A, n):
    if (A.size == 1):
        return Fraction(1, 1)
    else:
        k = numpy.sum(A[n][:])
        if (k == 0):
            return Fraction(0, 1)
        else:
            res = Fraction(0, 1)
            for i in range(A.shape[0]):
                if A[n][i] == 1:
                    if i < n:
                        res += rec(numpy.delete(numpy.delete(A, (n), axis = 0), (n), axis = 1), i)
                    else:
                        res += rec(numpy.delete(numpy.delete(A, (n), axis = 0), (n), axis = 1), i - 1)
            res = res*Fraction(1, int(k))
            return res


n = int(input())
A = numpy.zeros((n*n, n*n))
for i in range(n):
    for j in range(n):
        for k in range(n):
            for l in range(n):
                if (i - j == 1 and k == l) or (j - i == 1 and k == l) or (k - l == 1 and i == j) or (l - k == 1 and i == j):
                    A[n*i + k][n*j + l] = 1
print(rec(A, 0))

I should also mention, that the function "rec" is designed here to solve the generalised problem, with its arguments being exactly the adjacency matrix of $G$ and the number of its column corresponding to $v$

$\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.