Author |
Topic: Knight Circuit Time (Read 4596 times) |
|
william wu
wu::riddles Administrator
Gender: 
Posts: 1291
|
 |
Knight Circuit Time
« on: Nov 22nd, 2002, 3:43pm » |
 Quote  Modify
|
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?
|
|
 IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Knight Circuit Time
« Reply #1 on: Nov 24th, 2002, 1:10pm » |
Quote Modify
|
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)
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Knight Circuit Time
« Reply #2 on: Nov 25th, 2002, 12:47am » |
Quote Modify
|
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)
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
SWF
Uberpuzzler
Posts: 879
|
|
Re: Knight Circuit Time
« Reply #3 on: Dec 1st, 2002, 1:57pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Knight Circuit Time
« Reply #4 on: Dec 1st, 2002, 2:50pm » |
Quote Modify
|
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..
|
| « Last Edit: Dec 1st, 2002, 3:07pm by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
william wu
wu::riddles Administrator
Gender:
Posts: 1291
|
|
Re: Knight Circuit Time
« Reply #5 on: Dec 7th, 2002, 6:06am » |
Quote Modify
|
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.
|
| « Last Edit: Dec 7th, 2002, 6:07am by william wu » |
IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
SWF
Uberpuzzler
Posts: 879
|
|
Re: Knight Circuit Time
« Reply #6 on: Dec 7th, 2002, 6:10pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
Nigel_Parsons
Junior Member
Gender:
Posts: 63
|
|
Re: Knight Circuit Time
« Reply #7 on: Apr 10th, 2004, 3:05pm » |
Quote Modify
|
Ever the optimist, I'll take the 1/6 chance of the knight landing back on his second move!
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Knight Circuit Time
« Reply #8 on: May 2nd, 2004, 8:20am » |
Quote Modify
|
on Nov 25th, 2002, 12:47am, 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.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Knight Circuit Time
« Reply #9 on: May 2nd, 2004, 9:11am » |
Quote Modify
|
on May 2nd, 2004, 8:20am, 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.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Knight Circuit Time
« Reply #10 on: May 3rd, 2004, 7:10am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Knight Circuit Time
« Reply #11 on: Jan 22nd, 2007, 7:32am » |
Quote Modify
|
on Dec 7th, 2002, 6:06am, 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 ei is the expected time to get to state n from state i (and let en>0 be the expected time to return to state n). Then
ei = 1 + [sum]j<n Aji ej = 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 - en v (*)
since eA = eA' + en v, where v is the last row of A.
Now let p be the column vector with pi the stationary probability of being in state i, so that
pi = [sum]j Aij pj,
i.e., p = Ap. In particular, vp = pn, and, since the entries of p add to 1, we also have wp = 1. So right-multiplying (*) by p gives
ep = wp + eAp - envp
= 1 + ep - enpn,
so enpn = 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, Ak 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 Bk is strictly less than 1. Then it's easy to see that powers of Bk converge to 0 (the largest entry decays exponentially), so Bk, 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 en 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 Akv -> p for any v requires some more work though.)
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Knight Circuit Time
« Reply #12 on: Aug 16th, 2008, 9:41am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Knight Circuit Time
« Reply #13 on: Aug 16th, 2008, 1:34pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print