Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Consider a random walk of a king on a standard chess board, which at each step moves to a uniformly random permitted square. What's the exact mean time to visit all squares (cover time), starting from a corner square?

Is there an algebraic solution?

share|improve this question
1  
Here is a relevant quote from Chapter 12 of Problems and Snapshots from the World of Probability by Blom, Holst, and Sandell. "This problem seems extremely difficult. According to simulation, consisting of one million rounds, the mean is approximately equal to 615." –  Byron Schmuland Jan 25 '13 at 17:53
    
@Byron: Strangely, the problem is underspecified in the book: "Place a king somewhere on an empty chessboard." From mjqxxxx's results from $597$ to $621$, it seems that the initial position might be meant to be selected at random. –  joriki Jan 26 '13 at 11:53
    
@joriki Yes, that makes sense. –  Byron Schmuland Jan 26 '13 at 15:30
    
What are the asymptotics for the mean time for an nxn board? –  user59761 Jan 26 '13 at 19:48

2 Answers 2

There is in principle no difficulty in answering this question. As I point out in my answer here, calculating the expected cover time of some set $\cal S$ reduces to calculating the expected hitting time of every possible non-empty subset $A$ of $\cal S$:

$$\mathbb{E}(\text{cover time})=\sum_A (-1)^{|A|-1} \mathbb{E}(T_A)$$

These hitting times are defined by $T_A=\inf(n\geq 0: X_n\in A)$.

Just to illustrate, let me show you the solution for a $2\times 2$ chessboard:

a small board

The expected time to cover the other 3 squares ${a,b,c}$ is equal to $$\mathbb{E}(T_{a})+\mathbb{E}(T_{b})+\mathbb{E}(T_{c})-\mathbb{E}(T_{a,b})-\mathbb{E}(T_{a,c})-\mathbb{E}(T_{b,c})+\mathbb{E}(T_{a,b,c})$$

Standard Markov chain theory uses linear algebra to find these expected hitting times $$\mathbb{E}(T_{a})=\mathbb{E}(T_{c})=3, \mathbb{E}(T_{b})=4, \mathbb{E}(T_{a,b})=\mathbb{E}(T_{b,c})=2, \mathbb{E}(T_{a,c})=\mathbb{E}(T_{a,b,c})=1$$

Putting it all together, we find that the expected cover time is $3+3+4-2-2-1+1=6$.

Note that I counted the king's initial position as already covered. If you require a return to your starting point you can modify the above technique.

The number of terms in the sum make this method impractical for an $8\times 8$ chessboard, however!


Added: If my calculations are correct, the expected cover time for the $3\times 3$ board is $${140803109038245\over 4517710919176}=31.1669$$

share|improve this answer
    
Hmmm, now my link is also messed up. –  Byron Schmuland Jan 25 '13 at 19:14
    
I don't know which of my minor changes (mainly removing periods from inside Latex expressions) did anything, but things look okay to me now. –  robjohn Jan 25 '13 at 20:12
    
Thanks! It looks OK now. –  Byron Schmuland Jan 25 '13 at 20:14
    
You cut your hair. :-( –  Asaf Karagila Jan 26 '13 at 18:14
    
It's my new look. –  Byron Schmuland Jan 26 '13 at 18:23

There is an algebraic solution; the mean cover time from any node in a graph is known to be rational and can be found in exponential time. It's not likely to have a simple form, though. Experimentally, I ran the following code:

import random

def reachable((i,j)):
   ok = lambda(q):(min(q)>=1 and max(q)<=8)
   return filter(ok, [(i-1,j-1), (i-1,j), (i-1,j+1), (i,j-1), (i,j+1), (i+1,j-1), (i+1,j), (i+1,j+1)])

def covertime(sq, rng=random.Random()):
   seen = set([sq])
   path = [sq]
   while len(seen)<64:
      path.append(rng.choice(reachable(path[-1])))
      seen.add(path[-1])
   return len(path)-1

I found that the mean cover time starting from a corner square was about $597$, while the mean cover time starting from a center square was larger, about $621$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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