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

        riddles >> hard >> Chess Markov Chain
        
(Message started by: Earendil on Apr 16th, 2005, 2:05pm)
Title: Chess Markov Chain
Post by Earendil on Apr 16th, 2005, 2:05pm
You have a 8x8 chess board and a King on A1 at turn 1. Every turn the King moves to one of his normal movement squares with equal probability. What is the probability that after an infinite number of turns the king is on one the central squares? (D4, D5, E4, E5 )
Title: Re: Chess Markov Chain
Post by Grimbal on Apr 16th, 2005, 3:11pm
I find [hide]32/420 = 7.6%[/hide]
Why?
[hideb]
Consider the probability not of the cells but of the moves between neighbouring cells.  The fact that each cell has as many moves in as out, and that the probability of the moves in are redistributed evenly among the moves out, makes the probabilities converge to be all the same.
There are 420 possible moves, 32 of them end in the 4 central cells.
[/hideb]
Title: Re: Chess Markov Chain
Post by Deedlit on Apr 17th, 2005, 9:11am
While this is clearly the answer, I think a complete solution requires a proof that the process converges to this distribution. (which is what I assume Earendil meant by the somewhat nonsensical "infinite number of turns")  There's probably some basic result that says that this Markov chain has to converge to a stable distribution - I don't know much about Markov chains.  So we (probably) need to show that this is the only stable distribution.

We know that for each square, the probability of each outgoing move is equal.  Also, we know the outgoing moves and ingoing moves have to cancel out.  So if we let P(x) be the probability of a single outgoing move from x, we have that each P(x) is a weighted average of P(y) over all neighboring squares y.  If any two adjacent squares x0 and x1 have different values for P, then x1 must have a have a neighbor x2 with a larger value of P, and x2 must have a larger neighbor x3, and so on to infinity.  But this is absurd, since we only have 64 squares. So Grimbal's is the only stable distribution.
Title: Re: Chess Markov Chain
Post by towr on Apr 17th, 2005, 11:49am
Another approach is to show that nth power of the transition matrix converges (to a non-zero matrix) as n goes to infinity.
(I'll have to dig up my numerical math book before I can work that out further though)
Title: Re: Chess Markov Chain
Post by kris on Apr 18th, 2005, 7:21am
As the number of states (64) is finite, and as each state is accessible from every other state, the markov chain is irreducible. A finite irreducible markov chain is positive recurrent and has an unique stationary distribution. So in the current problem the probability tends to a finite limit. Thus what remains is solving 64 simultaneous eqn in 64 variables, if one goes by brute force method. atleast one can reduce it to 16 eqns using symmetry.

~kris
Title: Re: Chess Markov Chain
Post by Deedlit on Apr 18th, 2005, 12:09pm

on 04/18/05 at 07:21:51, kris wrote:
As the number of states (64) is finite, and as each state is accessible from every other state, the markov chain is irreducible. A finite irreducible markov chain is positive recurrent and has an unique stationary distribution.


Neat stuff!  In fact, any positive recurrent Markov chain has a unique stationary distribution of the form u(j) = k / W(j,j), where W(j,j) is the mean return time for j.  More generally, any invariant signed measure is of the above form. (I did some digging.  :P) So, for a Markov chain like this one, where the possible transitions are symmetric and the probabilities are uniformly distributed between the possible transitions, the mean return time for a state is inversely proportional to the number of possible transitions from that state!  Very cool indeed.  8)


Quote:
So in the current problem the probability tends to a finite limit. Thus


Well, that doesn't follow from what you said before.  For instance, a finite irreducible Markov chain could just be moving around a ring.  But a finite, irreducible, aperiodic Markov chain does converge to a unique limiting distribution (regardless of initial distribution) by the Perron-Frobenius theorem.
Title: Re: Chess Markov Chain
Post by kris on Apr 18th, 2005, 12:37pm
yeah...should have included that case too...missed that one. however, in this current problem, we have a aperiodic chain, so that wont cause any problem.

another point i missed was, using further symmetry, one can actually reduce to 10 equations in 10 variables. havent actually written or solved the equations though.

~kris
Title: Re: Chess Markov Chain
Post by SWF on Apr 18th, 2005, 9:52pm
This problem is very similar to a problem that was posted in this forum a couple of years ago, Knight Circuit Time (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_medium;action=display;num=1038008593), except that one was for a knight moving at random instead of king.  It was solved in a similar way with a 10 by 10 matrix.
Title: Re: Chess Markov Chain
Post by Deedlit on Apr 19th, 2005, 3:09am

on 04/18/05 at 12:37:06, kris wrote:
yeah...should have included that case too...missed that one. however, in this current problem, we have a aperiodic chain, so that wont cause any problem.


Yeah, but it would be nice to have an elementary proof of convergence.  It seems like there ought to be one.

I noticed the previous thread also talked about the relationship between the stationary probability and the mean return time.  The proof is nowhere near as hard as William's GSI suggested, though.  If the Markov chain approaches a limiting distribution, then the density of times that the process is at state i converges to the limiting probability pi.  It follows that the nth appearance of state i is asymptotic with n/pi, and thus the mean return time is 1/pi.  So I guess it wasn't as cool as I first thought.    :(
Title: Re: Chess Markov Chain
Post by Deedlit on Apr 19th, 2005, 3:27pm
Here's a proof of convergence that doesn't invoke Perron-Frobenius:

First, we use the fact that if the Markov chain is acyclic, then Pn has all positive entries for sufficiently large powers n.  We have the basic fact that if gcd(a1, ..., ai) = 1, then there is a k such that for all n > k, n is representable as a sum of ai. (This isn't hard to prove)  So for any state i there is a number f(i) such that for all n >= f(i) there are paths from i to i of length n.  Letting p(i,j) be the length of a path from i to j, we have that there are paths from i to j for all lengths of f(i) + p(i,j) or more.  Letting n be the maximum of f(i) + p(i,j) for all (i,j), we have that Q = Pn has all positive entries.

Next, we claim that for Q an m x m stochastic matrix with positive entries and any vector v with a sum of 0, we have [lim]i Qiv = 0.  Let m(v) be the maximum absolute value of an entry in v, and let a be the smallest entry in Q.  We claim that m(Qv) <= (1-a) m(v).  Suppose WLOG that m(Qv) is the absolute value of a postive entry (Qv)i.  At least one of the entries of v is negative, say vj. Then  

(Qv)i = [sum]k Pi,k vk < [sum]k != j Pi,k vk <= [sum]k != jPi,k m(v) <= (1-a) m(v)

and so Qi v goes to 0.  With Q = Pn, we have [lim]i Pin + j v = Qi (Pjv) = 0 for all i, since Pjv can be regarded as just another distribution. So [lim]i Pi v = 0.

Since we have a stationary distribution s, we can write any distribution v as a sum s + z, where z will be a vector with sum 0, and then

 [lim]i Pi v  = [lim]i Pi s + Pi z = s.


Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board