wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> Knight Circuit Time
        
(Message started by: william wu on Nov 22^nd, 2002, 3:43pm)

Title: Knight Circuit Time
Post by william wu on Nov 22^nd, 2002, 3:43pm

A knight is initially placed in the corner square of a chessboard. It then proceeds to move randomly across the board. What is the expected number of steps until the knight returns to its initial corner square position?

Title: Re: Knight Circuit Time
Post by towr on Nov 24^th, 2002, 1:10pm

Modeling it with finite-state/markov like models I get about 203.24 moves.. After 10000 steps, with 8.24147324812984e-22 still left on the board..
That's starting with an even distribution. So at the start each square has 1/64, which in each step gets distributed equally among any squares a knight can get in one jump. And at each step multiplying the value in the corner by the number of steps it took to get there, adding that to the total, and emptying the corner..

should be possible to do it mathematically.. But I don't know how :p

I have to wonder though if it's a fair assumption to say every starting square is equally likely.. The center squares are a more likely starting point.
I guess I'll run the simulation again with this in mind..
So starting everything in the corner, letting the knight run random for 10000 steps, then model the time till it get's back..
heh..
Almost the same, but not quite.. 204.44 steps or 205.44 depending on wether there were an even or uneven number of random steps before returning.. (so averaging to 204.94)

Title: Re: Knight Circuit Time
Post by towr on Nov 25^th, 2002, 12:47am

hmm, I guess there's yet another interpretation..
If the knight makes one step from the corner randomly, and then see in how many random steps it is back..
That gives 167 steps (not counting the first step away from the corner)

Title: Re: Knight Circuit Time
Post by SWF on Dec 1^st, 2002, 1:57pm

Since you are using a Markov type model, you may have a matrix giving the probability of transition in each step from one square to another. If you have a state vector with each component of the vector associated with a square on the board, the value of each vector component equals the probability of that square having the knight. Multiplying this vector by the Markov matrix gives a new vector containing the probability of each square having the knight one move later.

After many moves (represented by repeated matrix multiplications), the state vector reaches a steady value. This steady value of the state vector can be found by solving a system of linear equations: {x}=(M){x} subject to the additional constraint (all the equations in that system are not independent) that all the elements of {x} add to 1.

Solving that system of equations isn't as bad as it sounds. It can be done by inspection. Also by use of various symmetries, the number of equations needed can be reduced to 10. The result I get is exactly 168 moves, which matches your value (I count the first move). Solving the system of equations also gives values for each of the squares. For example, starting at one of the 4 squares in the center is expected to return in 42 moves.

Title: Re: Knight Circuit Time
Post by towr on Dec 1^st, 2002, 2:50pm

hmm.. I really should brush up on my linear algebra..
It's much nicer if you can get an exact formula, rather than a simulation..

interesting.. the corner has 2 paths leading to/from it, the center 8, and 8*42 = 2*168, so the expecten returntime * the number of paths from a square seem constant..

Title: Re: Knight Circuit Time
Post by william wu on Dec 7^th, 2002, 6:06am

I may have misread his post (yes the administrator messes up a lot around here), but I don't think SWF said explicitly that he's using the following fact: the expected number of steps to return to a state in a markov chain is the reciprocal of the stationary probability of being in that state. So once you solve for the stationary probability, you have your answer.

But how do you prove this fact relating stationary probability to expected return time? Well, I asked my GSI last Wednesday and he wouldn't tell me, because he said the proof takes about four pages! Perhaps someone has a better way to solve this problem.

Title: Re: Knight Circuit Time
Post by SWF on Dec 7^th, 2002, 6:10pm

Yes, I took reciprocal of steady probability to give expected number of steps between visits to each square. It seemed pretty obvious that this was the case, but seeming obvious is no proof.

I figured that for a large block N moves which begin and end on a corner, the expected number of times a move ends on the corner (with p being the steady probability of being there) is N*p. With N moves and N*p visits to the corner there are N*p-1 groups of moves between visits to the corner. Their expected length is N/(N*p-1), which for large N is 1/p.

Title: Re: Knight Circuit Time
Post by Nigel_Parsons on Apr 10^th, 2004, 3:05pm

Ever the optimist, I'll take the 1/6 chance of the knight landing back on his second move!

Title: Re: Knight Circuit Time
Post by grimbal on May 2^nd, 2004, 8:20am

on 11/25/02 at 00:47:28, towr wrote:

That gives 167 steps (not counting the first step away from the corner)

Hehe... I don't know if it is right, but 167 is a most unexpected number of moves, since it is must be an even number. Maybe we should speak about the average number of moves?
I don't think that can be solved without a computer. You have to solve a 64x64 matrix, maybe less using symetry.

Title: Re: Knight Circuit Time
Post by towr on May 2^nd, 2004, 9:11am

on 05/02/04 at 08:20:08, grimbal wrote:

Hehe... I don't know if it is right, but 167 is a most unexpected number of moves, since it is must be an even number.

It is even, if you include the first step (which I explicitly stated I didn't)..

Quote:

Maybe we should speak about the average number of moves?

Yes we should, as that's what was asked, the expected number. Which is the weighted average over each path (where the weight is the chance of the path occuring)

Quote:

I don't think that can be solved without a computer. You have to solve a 64x64 matrix, maybe less using symetry.

It depends on what and how you want to do it. The 64x64 matrix is mostly empty anyway, so it's not nearly as bad as you make it sound.

Title: Re: Knight Circuit Time
Post by grimbal on May 3^rd, 2004, 7:10am

1 - oops, ok
2 - agreed, I was just playing with the meaning of "expected"
3 - maybe I am just too lazy. Indeed, as someone mentionned, symetry brings the matrix down to 10x10.

Title: Re: Knight Circuit Time
Post by Eigenray on Jan 22^nd, 2007, 7:32am

on 12/07/02 at 06:06:22, william wu wrote:

But how do you prove this fact relating stationary probability to expected return time?

This seems to be pretty straight-forward, actually. Let A be the nxn transition matrix, with all columns summing to 1.

Let e be the row vector such that e_i is the expected time to get to state n from state i (and let e_n>0 be the expected time to return to state n). Then

e_i = 1 + [sum]_j<n A_ji e_j = 1 + (eA')_i,

where A' is the matrix A with last row replaced by 0s. Letting w be the row vector of all 1s, we therefore have

e = w + eA'
= w + eA - e_n v (*)

since eA = eA' + e_n v, where v is the last row of A.

Now let p be the column vector with p_i the stationary probability of being in state i, so that

p_i = [sum]_j A_ij p_j,

i.e., p = Ap. In particular, vp = p_n, and, since the entries of p add to 1, we also have wp = 1. So right-multiplying (*) by p gives

ep = wp + eAp - e_nvp
= 1 + ep - e_np_n,

so e_np_n = 1, as desired. (This seems to work for an infinite number of states as well, assuming e and p exist.)

Of course I have not shown that e and p actually exist. For this one needs to assume the matrix is regular: for some k, A^k has all positive entries. It's a standard result (Perron-Frobenius theorem), but I don't see a proof online. Consider the following:

Let B denote the upper-left (n-1)x(n-1) minor of A. Then B is the transition matrix of a process where things disappear once they enter state n. Since A is regular, there's a positive probability of going from state any state i to state n in k steps; in terms of B this is a positive probability of disappearing, so the sum of the i-th column of B^k is strictly less than 1. Then it's easy to see that powers of B^k converge to 0 (the largest entry decays exponentially), so B^k, and hence B, can't have 1 as an eigenvalue.

So (I-B) is invertible, and therefore the first (n-1) entries e' of e are uniquely defined by e' = (1,...,1) + e'B, and then e_n is determined by (*).

Since each column of A has sum 1, wA=w, so (A-I) is singular, so A has an eigenvector p with eigenvalue 1. On the other hand, the upper-left (n-1)x(n-1) minor of A-I is B-I, which is invertible, so A-I has rank n-1, so p is unique. (The fact that A^kv -> p for any v requires some more work though.)

Title: Re: Knight Circuit Time
Post by Grimbal on Aug 16^th, 2008, 9:41am

I realized that there is a simple way to compute the answer.

For each square, count the number of ways the knight can go. It gives a matrix:
2 3 4 4 4 4 3 2
3 4 6 6 6 6 4 3
4 6 8 8 8 8 6 4
4 6 8 8 8 8 6 4
4 6 8 8 8 8 6 4
4 6 8 8 8 8 6 4
3 4 6 6 6 6 4 3
2 3 4 4 4 4 3 2

The probability for the knight to be in each cell is proportional to these values. If you imagine these are points and the points are sent evenly along all routes, then one point is sent along each possible route and the same number comes in from other cells. So it is a stable configuration.
The sum of the matrix is 336, so the probability to be in the corner is 2/336 = 1/168. That means that in the long run, the knight will return to the corner every 168 moves, or in other terms, it takes 168 moves on average to return to the top left corner.

Title: Re: Knight Circuit Time
Post by Eigenray on Aug 16^th, 2008, 1:34pm

Nice observation! It only works for symmetric graphs though. For non-symmetric graphs you can have two vertices with the same in- and out-degrees, but different stationary probabilities, so it can't be so easily expressed.