Knight on infinite chessboard riddle

Problem

From the Riddler book.

Suppose that a knight makes a random walk on an infinite chessboard. Specifically, every turn the knight follows standard chess rules and moves to one of its eight accessible squares, each with probability 1/8.

What is the probability that after the twentieth move the knight is back on its starting square?

Simulation solution

Use Julia

library(JuliaCall)

The knight moves two tiles in any direction, and one tile in a direction perpendicular to that.

Here are the 8 moves:

moves = [[1, 2], [1, -2], [-1, 2], [-1, -2],
         [2, 1], [2, -1], [-2, 1], [-2, -1]];

Code

using Plots

scatter([c[1] for c in moves], [c[2] for c in moves], 
        legend=false, markersize=10, color=:blue, tickfontcolor=:white);
scatter!([0], [0], legend=false, markersize=10, color=:red, tickfontcolor=:white);

xlims!(-4, 3);
ylims!(-4, 3)

The function take_twenty_random_moves moves the knight 20 times at random, and returns the position the knight end up at.

We do this a number of times, and record how many of those times it ended up back at the starting point.

using Random
Random.seed!(0);
nsims = 10^6;

take_twenty_random_moves() = Tuple(sum(hcat(rand(moves, 20)...), dims = 2));
sum(take_twenty_random_moves() == (0, 0) for _ in 1:nsims) / nsims

0.006266

Exact solution

This is solved via recursion. After each move, the first number in the vector counts the number of possible ways to return to the starting position from there, while the second number in the vector counts the total number of possible moves from there.

The solution is then found by dividing the first number by the second.

(The coordinates of the position i and j are used instead of the position as a tuple, in order for the memoize function to be able to efficiently remember all the positions it has already seen.)

using Memoize
@memoize function knight_returns(moves_left, i, j)
    moves_left == 0 && return [i == j == 0, 1]
    n_return = [0, 0]
    for move in moves
        n_return += knight_returns(moves_left - 1, i + move[1], j + move[2])
    end
    n_return
end;

v = knight_returns(20,0,0);
v[1] / v[2]

0.006208754649023429