Self-avoiding walks on infinite grids

Suppose we start at \((0,0)\) on the cartesian grid, and wander about randomly only in North, South, East and West directions, never visiting a vertex more than once. How far will we wander before we come to a point around which there are no unvisited vertices?

This is best answered experimentally, and indeed it’s already be done - note that this article is behind a paywall, but the result can be read. The average length, it seems is 71 steps, or more precisely \(70.6 \pm 0.2\) steps.

We can check this for ourselves, using Julia for speed. First, a simple function for a random walk:

function chrand(A)
    return(A[rand(CartesianIndices(A))])
end

dirs = [[1,0],[-1,0],[0,1],[0,-1]]

function random_path()
    P = [[0,0]]
    while true
        adj = [last(P) .+ q for q in dirs]
        available = adj[(!in).(adj,Ref(P))]
        if length(available) == 0
            return(P)
        else
            new = chrand(available)
            P = append!(P,[new])
        end
    end
end

This function simply adds points one at a time, at each stage adding any point which is adjacent to the most recent one, and is not yet in the path. The helper function `chrand` just chooses a random element from an array.

Now we can run this function as many times as we like, and look at the results:

using ProgressMeter

path_lengths = []
N = 100000
@showprogress for i in 1:N
    P = random_path()
    path_lengths = append!(path_lengths,[length(P)])
end

The handy package ProgressMeter does just that - shows a progress meter.

After it finishes (taking 42 seconds on my elderly, but trusty, laptop), we can than explore some statistics:

using StatsBase

mean(path_lengths)

which returns:

\(71.84871\)

And we can also look at the histogram:

histogram(path_lengths,legend = false)

Note that path lengths form a very skewed distribution, where long paths are very uncommon. You might try, for example, to find a path which is over 750 steps long by creating random paths and checking their lengths. This takes a very long time. When I tried this, it took 13704084 trials to find a path over 750 steps; the path found had in fact 847 steps, and looks like this:

Note how at the other end the path has got itself into a little spiral from which it can’t continue.

Higher dimensions

Well, one higher dimension. We use the same routines as above, except that we start with [0,0,0], and the list of directions is

dirs = [[1,0,0],[-1,0,0],[0,1,0],[0,-1,0],[0,0,1],[0,0,-1]]

Paths are much longer here, and running only 1000 trials (which took me about 30 minutes), I ended up with a mean length of 3757.895. The longest path was 22877 steps, and the shortest was only 48.

On another test run, I got a short path of only 28 steps (the dark dot shows the path start at \((0,0,0)\):