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 4-step random walk terminates at square C?

(In reply to

One way to solution by Jer)

A very nice solution!

Of course, there are not really 8^4 four move sequences on a chessboard without moving off the board, but we can rationalize that away. Once we get to the end of the board, we are not getting back in time. If we assume that at each move the King chooses equally among all of his possible moves (which is implied by the phrase "random walk"), then your solution is correct.

If, on the other hand, we assume that all possible valid walks on an 8x8 board are equally likely, then a higher probability results. The number of walks that fall off the board are 3^4 = 81. So this makes the revised probability 216/(4096-81) = 5.38% (approx.). But, of course, this is not what mathematicians mean by a random walk.

Either assumption, of course, yields your answer if we start at the center of a 9x9 board.