I played around a bit with the word-counting approach, which seems to have given me some promising results.
Each walk of length
dimensions that starts at the origin corresponds to a word of length
from the alphabet
For instance, if you're interested in walks from
steps, consider the word
characters correspond to steps in the positive and negative directions in dimension
, respectively. The
:es are characters (directions) yet to be selected from
. If we walk in the order prescribed from left to right in
, by the time we reach the
:es, we will have reached
in our walk.
If we consider the first two
:es from the left, we can replace them with any pair of
) and still be in
after these two additional steps. Repeating this for each consecutive pair of
:es, assuming that we have an even number of
:es, the resulting string describes a walk from the origin to
In this particular example, it is realized that we can represent a selection of three pairs of
as the sum 3+0+0 (three pairs from the first dimension, none from the remaining two). Similarly, 0+2+1 represents a selection of no pairs of
, two pairs of
, and one pair of
(thus 0+2+1 gives rise to the string
Each such sum with three summands (where the summands are nonnegative integers that sum to half the number of
:es) gives us a walk to
represented by distinct letters.
By counting the number of permutations of all words that arise from all such sums (3+0+0, 0+3+0, 0+0+3, 2+0+1, 2+1+0, 0+2+1, 1+2+0, 0+1+2, 1+0+2, 1+1+1), we get the total number of walks we seek (since no other walks of this type exist).
For this example, we get that the number of walks that we seek, N, is
(Number of walks arising from 3+0+0) + (Number of walks arising from 0+3+0) + ... + (Number of walks arising from 1+1+1) =
Dividing N by the total number of walks in 20 steps (
) yields the probability that we end up in
after 20 steps.
This example is easily extended to the general case. For instance, using the notation
we get that the probability that we end up in
steps is given by
where the sum is taken over all nonnegative integers