aez-notes

Three-Dimensional Random Walk

What is the chance the simple random walk on \(\mathbb{Z}^{3}\) returns to its initial position?

Polya's Random Walk Theorem tells us that the probability of return in \(\mathbb{Z}^{2}\) is 1, however in higher dimensions it is not certain. In three dimensions it is approximately \(0.34\).

We can do a very rough calculation to get the return probabilities for 3 and 4 dimensions with the following script. It runs too slow to get more than the first digit correct though, even when compiled and with memoization.

restart();
kill(all);

foldl(f, x0, xs) :=
if emptyp(xs)
then x0
else foldl(f, f(x0, first(xs)), rest(xs));

prod(xs) :=
if emptyp(xs)
then 0
else foldl("*", first(xs), rest(xs));

arraymap(a, xs) := map(lambda([x], a[x]), xs);

l_1[n] := if evenp(n) then binomial(n, n/2) else 0;

l_coeff(n, d) :=
if is(equal(n, 0))
then 1
else lsum(i, i,
  map(
    lambda([p], apply(multinomial_coeff, p) * prod(arraymap(l_1, p))),
    listify(flatten(map(permutations, integer_partitions(n, d))))));

L(z, d, N) := sum(l_coeff(2 * n, d) * z^(2 * n), n, 0, N);
prob_return(d, N) := float(1 - 1 / L(1 / (2 * d), d, N));

compile(l_coeff);

print(prob_return(3, 50));
/*
0.3107687252064985
*/
print(prob_return(4, 10));
/*
0.1807480265784589
*/