Prove that the probability of a knight to get in a specific square is 1.

Question

So this is the question I'm stuck at:

Assume that we have a knight on the chess board on the square B1 and there is no other piece on the board. Each time the knight moves randomly on the board. Prove that the probability of the knight reaching the square B8 is 1.(The number of moves are infinite)

I know that it is possible to reach any square of the chess table by knights tour problem. And I know that starting and the ending point doesn't matters in the problem. I just don't know how to show that the probability of getting to a specific square is 1.

Answer 1

The pigeonhole principle guarantees that there is a square (let us call it X) on which the knight is infinite many times.

There is a fixed sequence of moves taking him from X to B8 , and we have infinite many trials , so this fixed sequence must eventually occur.

Answer 2

This is just a more detailed version of Peter's excellent answer.

With infinitely many moves, and only 64 squares, there must be some square that the knight lands on infinitely many times. That's because any sum of 64 finite numbers is still finite. (It's the infinite pigeonhole principle: If an infinite number of pigeons fly into a finite number of boxes, then at least one of those boxes has infinitely many pigeons in it.)

Once the knight lands on one square infinitely often, consider the $2$, $3$ or $4$ squares within reach of it. Let's take $4$ as our example; a similar argument applies to $2$ and $3$. The probability of landing on any one of those squares is $1$, because the probability of avoiding it is $\frac34$, each time you leave that first infinite square, and $\left(\frac34\right)^n$ goes to $0$ as n grows. Now you have more squares (total of $5$ now, in the case we're looking at) that are hit with probability $1$, and the same argument shows that they are each, with probability $1$, hit infinitely often. (If one is only hit finitely often, then it falls into the same $\left(\frac34\right)^n$ trap.)

Now you can repeat this process for the subsequent move. Each square within reach of our $5$ certainly-infinite squares will also be visited infinitely many times, with probability $1$.

With each repetition, we collect more squares that are visited infinitely often, with probability $1$. Since every square will eventually be reached (all being a finite number of moves from our original infinite square), we can draw the same conclusion about every one.

Answer 3

From any square, it takes at most $5$ moves to get to B8:

3 0 3 2 3 2 3 4
2 3 2 1 2 3 4 3
1 2 1 4 3 2 3 4
2 3 2 3 2 3 4 3
3 2 3 2 3 4 3 4
4 3 4 3 4 3 4 5
3 4 3 4 3 4 5 4
4 5 4 5 4 5 4 5

So divide up the knight's infinitely long random walk into blocks of $5$ moves. In each block of $5$ moves, there is at least a $(\frac18)^5$ chance of ending up at B8: there is

• at least one sequence of moves the knight can follow to get there in that block, no matter where it started, and
• at most $8^5$ possibilities total, since a knight has at most $8$ options for each move.

This repeats every block, so after $k$ blocks ($5k$ moves total) there is at most a $(1 - (\frac18)^5)^k$ chance that the knight has not been to B8. As $k \to \infty$, this probability goes to $0$, so with probability tending to $1$, eventually the knight will visit B8.