Imagine a chess King placed in the central square C(5,5) of a 9x9 “checkerboard”. King’s step consists of his displacement to the neighboring square in one of the 8 directions.
What is the probability that his 4step random walk terminates at square C?
First consider everywhere the King can get in 2 moves and the number of ways to get there.
1 2 3 2 1
2 2 4 2 2
3 4 8 4 3
2 2 4 2 2
1 2 3 2 1
Note: the 8 is on the starting square.
Now from any of these squares there are the same number of ways to get back to the center in 2 moves, so we can just square all these numbers and add them up.
The sum is 216. There are 8^4 = 4096 fourmove sequences so
216/4096 = 27/512 = .052734375
Incidentally you could use an ordinary chessboard for this problem. The starting board really only needs to be 7x7, since if the first three moves bring you that far out, the fourth can't bring you back.

Posted by Jer
on 20150521 09:40:07 