How many steps are required to get home from a random walk?

In Frank Morgan’s “Math Chat” column of December 2, 1999, on the Mathematical Association of America (MAA) website, he posed the following challenge:

How fast do you get home with a random walk on the line? in the plane? in three-space? in n-space? The following was my response. . . .

Subj: Random walk challenge
Date: Sunday, December 5, 1999 3:03:05 PM
From:
To: Frank.Morgan@williams.edu

Thanks for posting this challenge. With your indulgence, I'll resubmit some results I sent in previously....

First, defining some terms and structures:
Each walk begins at the origin (0 on the line, (0,0) in the plane, etc.). Each step changes the coordinate in exactly one dimension (with the choice of dimension equally likely for each) by either +1 or -1, and these alternatives (i.e., +1 vs. -1) are also equally likely. To return home in k steps means that you are back home at the conclusion of the kth step AND NOT BEFORE (unless specified otherwise in a particular context in the forthcoming discussion).

On the line, you should, in the long run (or walk), return home in 2 steps half the time (50%). The walk should require 4 steps in another 1/8 (12.5%) of cases; 6 steps in another 1/16 (6.25%) of cases; 8 steps in another 5/128 (about 3.91%) of cases; 10 steps in an additional 7/256 (about 2.73%) of cases; and so on. Expressed cumulatively, you should require:
2 steps 50% of the time
4 or fewer steps 62.5% of the time
6 or fewer steps 68.75% of the time
8 or fewer steps 72.66% of the time
10 or fewer steps 75.39% of the time
12 or MORE steps 24.61% of the time.
The median of the set of all 1-D walk lengths (number of steps required to return home) is 3. (N.B. I use “set,” in this entire discussion, not in its strictest set-theory definition, which ignores repeated elements, but rather in a statistical sense, where separate elements may have the same value but each is treated as a “full-fledged” datum.)

In the plane, you should, in the long run, return home in 2 steps 1/4 of the time (25%). The walk should require 4 steps in another 5/64 (about 7.81%) of cases; 6 steps in another 11/256 (4.30%) of cases; and so on. Expressed cumulatively, you should require:
2 steps 25% of the time
4 or fewer steps 32.81% of the time
6 or fewer steps 37.11% of the time
8 or MORE steps 62.89% of the time.
The median of the set of all 2-D walk lengths (number of steps required to return home), by computer simulation, appears to be around 32.

In three-space, you should, in the long run, return home in 2 steps 1/6 of the time (about 16.67%). The walk should require 4 steps in another 1/24 (about 4.17%) of cases; 6 steps in another 83/3888 (about 2.13%) of cases; and so on. Expressed cumulatively, you should require:
2 steps 16.67% of the time
4 or fewer steps 20.84% of the time
6 or fewer steps 22.97% of the time
8 or MORE steps 77.03% of the time.
According to information I found on a Web page, there is about a 66% chance you will NEVER return home from a random walk in 3-space. (The article, about which I will say more in a few moments, had nothing to say about the number of steps in a walk that does return home: THAT I had to do myself!)
Since some walks never return home (i.e., they have infinitely many steps), the mean walk-length would be infinite in 3-space. Also, since more than 50% of walks are infinite, the median walk-length would be infinite as well.

In n-space, you should, in the long run, return home in 2 steps 1/(2n) of the time (or 50/n%). The walk should require 4 steps in another (4n-3)/8n^3 (or (100n-75)/2n^3%) of cases; 6 steps in another (20n^2-39n+20)/16n^5 (or (500n^2-975n+500)/4n^5 %) of cases; and so on. Expressed cumulatively, you should require:
2 steps 50/n% of the time
4 or fewer steps (100n^2+100n-75)/2n^3% of the time
6 or fewer steps (200n^4+200n^3+350n^2-975n+500)/4n^5% of the time
8 or MORE steps (400n^5-200n^4-200n^3-350n^2+975n-500)/4n^5% of the time.
The Web page mentioned in the previous paragraph gives probabilities of never returning home from random walks as approximately 80%, 86%, 89%, 91%, and 93% in 4-, 5-, 6-, 7-, and 8-space, respectively.

Mean and median walk-lengths would be infinite in n-space for each n>2.

The mode of the set of walk-lengths is 2 in each dimension.

******

The 1-D case is a good place to start. It immediately becomes evident that any walk that returns home must have an even number of steps: equally many positive as negative ones. With a little thought, I realized the following: the total number of possible walks of length k is 2^k; and, for each positive, even k, the total number of k-step walks that end up at home (the origin) INCLUDING THOSE THAT ALSO ENCOUNTERED THE ORIGIN BEFORE THE kTH STEP is C(k,k/2). To illustrate, consider k=6. Denote each step in the positive direction as + and each step in the negative direction as -. A walk that is back at the origin after 6 steps must be some sequence of 3 +s and 3 -s. If we view the positions of the 3 +s among the 6 overall steps as a choice of choosing 3 elements out of 6, we get C(6,3), or 20. However, among these 20 are some that should not be counted in the present context. Consider, for example, +-+-+-. This represents a walk that is at the origin after 6 steps, BUT it is also home after 2 steps, as well as after 4 steps. We count for the length of the walk, in this problem, how many steps are taken to reach home FOR THE FIRST TIME (after departing). Thus +-+-+- is not really a 6-step walk at all: it “reduces” to just +-, and is thus a 2-step walk. It turns out that 16 out of the 20 sequences consisting of 3 +s and 3 -s must be thrown out for just such a reason, leaving only 4 “true” 6-step walks that return to the origin (walks that REQUIRE 6 steps to get back home). Since there are 2^6, or 64, total possible 6-step walks, the probability is 4/64, or 1/16, that you need 6 steps to get home, and hence the words in the answer above:

“On the line, ...6 steps in another 1/16 (6.25%) of cases;...”

Using such reasoning, we get 2/4, or 1/2, for the probability of a walk requiring 2 steps, and 2/16, or 1/8, for getting home in 4 steps. Such reasoning is valid as k increases, but the calculations get messy pretty fast. I did it with 8 (and got what eventually proved [I hope] to be the right answer), but I did find a bit of a short-cut that I used to check the case for k=8 and then work the case for k=10 steps. It uses a bit of probability theory, for which I had to break out a textbook for some formulae. It involves unions and intersections. On the keyboard on which I am presently typing, the usual symbols for union and intersection are available (in certain fonts), but I have reason to believe they won’t go through on the e-mail, so with your indulgence, I will use “u” and “n” for union and intersection, respectively, and hope the meanings will be evident from context.

My theory, which seems after some calculation and analysis to be valid, can be illustrated as follows:
Consider 8-step walks.
Let A be the event that a 2-step walk will be home at the end of those 2 steps. Thus P(A)= C(2,1)/2^2.
Let B be the event that a 4-step walk will be home at the end of those 4 steps, INCLUDING CASES WHERE THE ORIGIN IS REACHED IN 2 STEPS. P(B)= C(4,2)/2^4.
Let C be the event that a 6-step walk will be home at the end of those 6 steps, INCLUDING CASES WHERE THE ORIGIN IS REACHED IN 2 OR 4 STEPS. P(C)= C(6,3)/2^6.
Let D be the event that an 8-step walk will be home at the end of those 8 steps, INCLUDING CASES WHERE THE ORIGIN IS REACHED IN 2, 4, OR 6 STEPS. P(D)=C(8,4)/2^8.
Then to find the probability that an 8-step walk got home in those 8 steps BUT NOT BEFORE, we take
P(D)-P((AuBuC)nD).
In words, this is the probability that we were home in 8 steps, minus the probability that we were home in 8 steps and also in 2, 4, or 6 steps.
Evaluating P(D)-P((AuBuC)nD) is where those textbook formulae came in handy.
We already have P(D), but P((AuBuC)nD) is another matter.
In general, for events X and Y, we have the familiar theorem:
P(XuY)=P(X)+P(Y)-P(XnY). This transforms into the slightly less familiar form:
P(XnY)=P(X)+P(Y)-P(XuY).
Returning to the present example, let AuBuC play the role of X, and let D be Y. Then
P((AuBuC)nD)=P(AuBuC)+P(D)-P(AuBuCuD).
Now we need to know how to calculate P(AuBuCuD). It turns out that this probability is the sum of the individual probabilities (i.e., P(A), P(B), P(C), and P(D)), MINUS all probabilities of intersections of pairs of (combinations of 2) events (i.e., P(AnB), P(AnC), P(AnD), P(BnC), P(BnD), and P(CnD)), PLUS probabilities of intersections of triplets (combinations of 3) events (i.e., P(AnBnC), P(AnBnD), P(AnCnD), and P(BnCnD)), MINUS the probability of the intersection of all 4 events (P(AnBnCnD)). (This general principle would work for any length string of events P(X1uX2uX3u...uXj): the first step [probabilities of individual events] always has positive terms, the next step [pairs of events] has negative terms, and so on, alternating signs with each successive step.)
The next difficulty is encountered in evaluating some of the individual terms of the sum. Consider for example, P(AnD). To evaluate this easily, it helps to understand just what it means: you got home in 2 steps and then continued your walk; after 8 total steps you were home again. However, you can realize that since you were back at the origin after the first 2 steps, then you can treat the REMAINING 6 steps as a 6-step walk in its own right, and one that came home as well. In other words, P(AnD) is just the probability that a 2-step walk will return home AND that a 6-step walk will end up at home (the 6-step case here INCLUDING cases where home is also reached after the first 2 or 4 of the 6 steps). The 2-step component and the (subsequent) 6-step component of the 8-step walk are independent events, so P(AnD)=P(A)*P(C). After much plugging and crunching of numbers, we eventually get
P(D)-P((AuBuC)nD)=10/256, which, in lowest terms, is 5/128, leading to the words of the original answer:
“On the line, you should require ... 8 steps in another 5/128 (about 3.91%) of cases;...”

I used much the same reasoning to get 28/1024 (or 7/256) for the 10-step case; after that it got to be just too many terms to deal with!

The reasoning behind my assertion that the (theoretical) median is 3 for the set of lengths of all 1-D walks, where length is defined as the number of steps required to get back to the origin (having started there), is just this:
Suppose you take q random walks, recording after each the number of steps required to return home. q is either even or odd. First consider the case of q even. If the theoretical probabilities are followed, exactly q/2 of the walks will be of length 2. Thus if the lengths are arranged in ascending numerical order, the first q/2 in the list will be 2. The next q/8 (it doesn’t really matter here whether this is an integer) will be 4, so certainly the (q/2)+1st will be a 4. Thus the two middle data in this ascending arrangement are 2 and 4. The mean of 2 and 4, and thus by definition the median of the data set, is (2+4)/2, or 3. Now consider q odd. If the q elements are arranged in order, there is a 50% probability that the (single) middle datum (which would by definition be the median) will be a 2 and a 50% probability it will be a 4. It seems reasonable to take the mean of 2 and 4, and that is 3.
I ran a computer simulation, employing my computer’s random-number generator, for random walks on the line. Having learned from earlier attempts that some walks seemed to “go on and on forever,” I had the program stop if a walk reached 1000 steps, report “>1000,” and go on to the next walk. Out of 500 walks, I got the following numbers for walk lengths, as indicated:
2: 266 = 53.2% (theoretical: 50.0%)
4: 68 = 13.6% (theoretical: 12.5%)
6: 23 = 4.6% (theoretical: 6.3%)
8: 17 = 3.4% (theoretical: 3.9%)
10: 11 = 2.2% (theoretical: 2.7%)
12 or more: 115 = 23.0% (theoretical: 24.6%).
The simulation data seem to be reasonably in line with theoretical values.

Another note: since some walks (15 out of the 500 in the simulation I ran) did “go on and on forever,” and I didn’t get exact values for their lengths, I was unable to calculate a MEAN value for the data set. (This would be sort of the “grail” for this whole problem, as posed: an “expected value,” in the language of probability & statistics.) I also tried the theoretical approach of computing 2*P(2-step walk)+4*P(4-step walk)+6*P(6-step walk)+..., but this seemed to converge too slowly (if in fact it is convergent) to be of practical use to me. If it’s even possible to determine a mean, I don’t know how it would be done.

HOWEVER, my use of the phrase “go on and on forever,” it would seem, is not quite appropriate here, at least when discussing the 1-D case. And that’s where the Web-page article comes in! This fascinating discussion can be seen at
http://www.mathsoft.com/asolve/constant/polya/polya.html .
A mathematician named Polya showed in 1921 that every random walk on the line is certain to come home. He also showed (looking ahead just a bit) that 2-D random walks are also certain to come home. However, in 3 or more dimensions, there is a positive probability that a random walk will not ever come home. The calculations for these probabilities are somewhat less than simple!!! Each probability is a multiple definite integral (the multiplicity equaling the number of dimensions). For 3 dimensions, the probability that a walk WILL return home (ever) is an expression containing a triple integral, and simplifies(?) to:
1-1/(((sqr(6))/32*pi^3)*gamma(1/24)*gamma(5/24)*gamma(7/24)*gamma(11/24)),
which evaluates to about 0.3405373296....

We are finally ready to move on to the 2-D case, where much of what we have shown so far will be useful, but a few new twists emerge....
In a 2-D random walk, there are 4 possibilities at each step: increase the x-coordinate by 1 (x+), decrease the x-coordinate by 1 (x-), increase the y-coordinate by 1 (y+), or decrease the y-coordinate by 1 (y-). Thus the number of possible k-step walks is 4^k. As in 1-D (and for essentially the same reason), in order to return home in k steps, k must be even. But a moment’s thought shows that there is an additional restriction: the number of steps IN EACH DIMENSION must be even in order to get back home (this number may be 0 for one of the dimensions), and in fact there must be equally many + and - steps within each dimension.
Let’s first examine 2-step walks. The number of possible walks is 4^2, or 16, and only 4 of these, x+x-, x-x+, y+y-, and y-y+, arrive home. Clearly a 2-step walk that gets back home must stay within a single dimension, so the “additional restriction” just mentioned does not come into play. The probability of getting home is 4/4^2, or 4/16, or 1/4, as given in the answer earlier.
With the 4-step case in 2-D, things start getting interesting. It is entirely possible that a random walk in 2-D may happen to stay within one dimension. It might stay in just the x dimension. Suppose it does. We already know how many 4-step walks in one dimension get home, from earlier: C(4,2), or 6, are home in 4 steps, and throwing out the ones among those 6 that were already back in 2 steps leaves just 2: x+x+x-x- and x-x-x+x+.
However, the walk may, with equal likelihood, stay just within the Y dimension! Similar reasoning shows there are 2 walks of 4 steps, staying within the y dimension, that get home in 4 steps but not before.
Add 2+2, and we have 4 walks in 2-D that require 4 steps to get home, with each such walk staying within one dimension.
Now we must examine 2-D walks that have some positive number of steps in EACH dimension, x and y. Fortunately, our reasoning from a moment ago shows that it’s not necessary to consider the possibility of 3 of the 4 steps being in one dimension and 1 in the other; we need only consider the case of 2 steps in each dimension. And within each dimension, we clearly need one + step and one - step. So overall, we need the walk to have an x+, an x-, a y+, and a y-. That is, it needs to be some PERMUTATION of x+x-y+y-. 4 distinct elements means 4!, or 24, permutations. But we’re not quite done. We have to throw out those that are home in 2 steps.
First, we throw out permutations starting with x+x-.., since they get home in 2. The number of such permutations is just the number of ways the remaining elements, y+ and y-, can be arranged in the 3rd and 4th positions, which is clearly just 2. Then, using the same reasoning, we throw out 2 walks starting with x-x+, and 2 starting with y+y-, and 2 starting with y-y+. That is, 2+2+2+2, or 8, of the 24 get thrown out, leaving 16 that involve both dimensions and actually require 4 steps to get home. Now we add to this the 4, each of which stays in one dimension, and we have a total of 20 walks, in 2-D, that require 4 steps to get home. Now there is a total of 4^4, or 256, possible walks of length 4 in 2-D, so the probability that it will require 4 steps to get home in 2-D is 20/256, or 5/64, as given in the answer above.
Now to the 6-step case in 2-D. As with the 4-step case, it’s possible that, for a given walk, all 6 steps will be within just one of the dimensions. Once again, this was already covered when we discussed 1-D walks: there are 4 different walks that require 6 steps to get home in one dimension. Once again, however, in 2-D such a walk might occur all within the x dimension, or all within the y dimension; thus we must add the 4 possibilities in x and the 4 in y, getting 8 walks in 2-D that require 6 steps to get home, where each walk stays within one dimension.
Consider the case now of 6-step walks in 2-D for which there is a positive number of steps in each dimension. For reasons mentioned above, we need not consider the possibility of 5 steps in one dimension and 1 in the other, nor need we look at the case of 3 steps in each dimension. Thus we need examine only the possibility that 4 steps are in one dimension and 2 in the other. We DO need to remember that this might be 4 in the x dimension and 2 in the y, and it might equally as likely be 4 in y and 2 in x. However, because of symmetry, we can do our calculations for just the case of 2 in x and 4 in y, and when we are done, double our result to account for the walks with 2 in y and 4 in x.
The 2 steps in x must be x+ and x-; the 4 in y must be 2 y+s and 2 y-s. Thus we must examine permutations of the 6 elements x+x-y+y+y-y-. The number of permutations is not 6!, but rather only 6!/2!2!, or 180, since 2 elements are doubled. Still, 180 seems to be a rather daunting number of sequences to examine. Fortunately, short-cuts continually present themselves, making the task manageable. When I actually worked this out on paper, I used the symbols D (for down), L (left), R (right), and U (up) in place of y-, x-, x+, and y+, respectively. I then began methodically listing permutations of DDLRUU in alphabetical order. However, I kept watching for any sequence that was symmetric (i.e., represented a return home) after either 2 or 4 elements, in which cases I didn’t need to look at arrangements of the remaining 4 or 2 elements but could “skip ahead.” In such a manner, I needed to account for just 32 sequences (or partial sequences) beginning with D, of which 26 required all 6 steps to return home. In a similar manner, I needed to look at only 21 sequences beginning with L, of which 16 required all 6 steps to get home. Then I reasoned that by symmetry, another 16, beginning with R, would return home in exactly 6 steps; likewise, another 26 beginning with U would do so.
Thus I had 26+16+16+26, or 84, different sequences in 2 dimensions, with 2 steps in x and 4 in y, that required 6 steps to return home. By symmetry there would be another 84 such walks with 2 steps in y and 4 in x.
84+84=168 walks in 2-D that involve both dimensions and require 6 steps to return home.
Now add the 8 walks accounted for above for which each stays within one dimension, and we have 168+8, or 176, walks in 2-D that require 6 steps to return home. The total possible number of 6-step walks in 2-D is 4^6, or 4096, so the probability that 6 steps are required to return home from a random walk in 2-D is 176/4096, or 11/256, as given above in the answer.

I ran a series of 2000 computer-simulated 2-D random walks and obtained the following numbers of walks requiring the specified number of steps to return home:
2: 453 = 22.7% (theoretical: 25.0%)
4: 177 = 8.9% (theoretical: 7.8%)
6: 72 = 3.6% (theoretical: 4.3%)
8 or more: 1298 = 64.9% (theoretical: 62.9%).
Again, the simulation data seem fairly close to predictions from theory.
The simulation dataset had a median of 32. Since the data seemed slightly high overall compared to theoretical values, it’s possible the true (theoretical) median should be slightly less.

Now, on to 3-D. A 2-step walk that returns home must stay within one dimension: the second step must simply be the “negative” of the first. We already know how many 2-step walks that return home there are in one dimension: 2. However, in 3-space, the single dimension in which both steps occur may be any one of 3 (i.e., both steps in x, both in y, or both in z). This gives 2*3, or 6, possibilities for walks in 3-space that return home in 2 steps. Now there are 6 possible directions (x+, x-, y+, y-, z+, z-) that any step in 3-space might go, so there are 6^2, or 36 total possible 2-step walks. Thus the probability that a 2-step walk in 3-space will return home is 6/36, or 1/6, as given in the answer above.

Next we consider 4-step walks. A 4-step walk in 3-D may involve only one dimension. Suppose a 4-step walk stays within the x dimension. We know from the 1-D case how many such walks require 4 steps to return home: 2. But the single dimension in which the walk takes place may be any one of 3. Since there are 2 possible walks in each of 3 dimensions, we have 2*3, or 6 possible walks in 3-D, each staying in one dimension, that require 4 steps to return home.
However, a 4-step walk in 3-D may involve 2 dimensions. Once again, our earlier work helps: we already know, from the 2-D case, how many walks that include steps in exactly 2 dimensions and require 4 steps to get home there are: 16. But now we must take into account that the two dimensions involved may be x & y, or they may be x & z, or y & z. Since there are 3 ways to choose which pair of dimensions a given walk occurs in, there are 16*3, or 48, walks in 3-D, with each involving two dimensions, that require 4 steps to return home.
We might then ask about 4-step walks involving all three dimensions, but we quickly realize this is not possible, since with a minimum of 2 steps in each dimension, a walk involving 3 dimensions would have a minimum of 2*3, or 6, steps.
We then need only add the number of walks staying within one dimension, 6, to the number each of which involves two dimensions, 48. We have 6+48=54 for the total number of possible walks in 3-D that require 4 steps to return home. The total possible 4-step walks in 3-D is 6^4, or 1296. Thus the probability that a random walk in 3-D will require 4 steps to return home is 54/1296, or 1/24, as stated in the answer above.

And now we move on to 6-step walks in 3-D. As before, all 6 steps might be within a single dimension. And again we know, from 1-D, that there are 4 walks in one dimension that require 6 steps to get home. There are 3 choices as to which dimension a given such walk occupies. 4*3 is 12: the number of random walks in 3-D with each staying within a single dimension, that require 6 steps to return home.
The walk may occupy two dimensions. Here we can use earlier work: in examining 2-D, we learned that in two dimensions, say x and y, there are 84 walks with 2 steps in the x dimension and 4 in the y that require 6 steps to return home; and by symmetry, there are an additional 84 such walks with 4 steps in x and 2 in y, giving 168 such walks in a pair of dimensions. But now, in 3-D, there are 3 ways to choose a pair of dimensions: x & y, x & z, or y & z. So we take 168*3, or 504, as the possible number of ways a random walk in 3-D that involves two of the dimensions can require 6 steps to return home.
And now, 6-step walks in 3-D that involve steps in all three dimensions. Clearly, this can only occur if there are exactly 2 steps in each of the dimensions. The approach I used here was to represent each 6-step walk as a sequence of steps, each step labeled x, y, or z according to its dimension. I began listing permutations of xxyyzz alphabetically, knowing there was an upper bound of 6!/2!2!2!, or 90, on how many permutations I would have to list. In fact, it was much easier. Any sequence that contained two of the same letter within the first 2, or two pairs of matching letters in the first 4, steps could be rejected, and any remaining “finishes” to that sequence could be skipped. For example, I started with xx----, and immediately skipped to xy---- sequences, because no xx---- sequence would count: either the two xs would be of the same sign and you wouldn’t get home, or they would be of opposite sign and you’d be home in 2 steps (not 6). Using such (and similar) logic, I looked at only 25 sequences (or partial ones) starting with x, of which 20 “counted.” But then I simply reasoned that by symmetry, there would be 20 more “legal” sequences starting with y and 20 more with z, making 60 in all. But I wasn’t quite done. For the walk to get home, the two xs in a sequence would have to be of opposite sign; likewise with the 2 ys and with the 2 zs. For example, take the sequence xyzxyz. The x in position 1 might be positive and the one in position 4 negative, or it could be the reverse: two possible arrangements of the xs. There would likewise be 2 possible arrangements of the ys, and 2 of the zs. Thus each sequence would actually represent 2*2*2, or 8, legal walks. 60 sequences times 8 arrangements of xs, ys, and zs within each gives 480 random walks in 3-D involving all 3 dimensions and requiring 6 steps to return home.
Now we add the walks in 3-D each involving one dimension: 12, plus those each involving two dimensions: 504, and those involving all three dimensions: 480, to get 996 random walks in 3-D that require 6 steps to get home. There are 6^6, or 46656, possible 6-step walks in 3-D, giving a probability of 996/46656, or 83/3888, that a random walk in 3-D will require 6 steps to return home, as stated in the answer above.

Finally, we can jump to n-space.
The 2-step case is straightforward. The walk must take place within one dimension to return home. Within one dimension there are 2 walks that return home in 2 steps. There are n choices for which dimension the walk will occupy. So there are 2*n, or 2n, random walks in n-space that return home in 2 steps. Now, at each step there is a choice of n dimensions, and once that is chosen, a choice of 2 directions (+ or -): 2n possibilities per step. The total number of possible 2-step walks is thus (2n)^2. Thus the probability that a random walk in n-space will return home in 2 steps is 2n/(2n)^2, or 1/(2n), as given in the answer above.

As for the 4-step case in n-space: in n-space, a walk might still take place all within one dimension. We know from before that there are 2 different walks within one dimension that require 4 steps to return home. In n-space there is a choice of n dimensions in which such a walk might occur. So there are 2*n, or 2n walks in n-space, each of which remains within a single dimension, that require 4 steps to get home.
A walk in n-space might involve 2 of the dimensions. Once again, we know that there are 16 random walks involving exactly two dimensions that require 4 steps to get home. But there is a choice as to which pair of dimensions are involved, and from combinatorics we know this is C(n,2), which evaluates to n!/(2!(n-2)!), or n(n-1)/2. Then 16 walks per pair of dimensions, times n(n-1)/2 choices for which pair of dimensions, gives 8n(n-1), or 8n^2-8n random walks in n-space involving two dimensions that require 4 steps to return home.
But as we realized in the 3-D case, a 4-step walk that returns home can never involve more than two dimensions, no matter what the value of n is. We need not concern ourselves here with walks with steps in 3 or more dimensions.
So the total number of walks in n-space that require 4 steps to get home is 2n+8n^2-8n, or 8n^2-6n. There are (2n)^4, or 16n^4 possible 4-step random walks in n-space, so the probability of a random walk in n-space requiring 4 steps to return home is (8n^2-6n)/16n^4, or (4n-3)/8n^3, as given in the answer above.

Lastly, we will treat 6-step walks in n-space. A 6-step walk may remain in a single dimension. There are 4 walks in one dimension that require 6 steps to return home, and a choice of n dimensions, giving 4*n, or 4n random walks in n-space, each remaining within a single dimension, that require 6 steps to return home.
A 6-step walk may have steps in exactly 2 dimensions. We know that in a given pair of dimensions there are 168 walks using both dimensions that require 6 steps to get home. We know from a moment ago that there are n(n-1)/2 ways to choose a pair of dimensions out of n possibilities. So there are 168*n(n-1)/2, or 84n(n-1), or 84n^2-84n walks in n-space, each having steps in exactly 2 dimensions, that require 6 steps to return home.
And a 6-step walk may involve 3 dimensions. We know from earlier that the number of walks in a “triplet” of dimensions, with steps in all 3, that require 6 steps to return home is 480. The number of ways to choose which 3 dimensions out of n possibilities is C(n,3), or n!/(3!(n-3)!), or n(n-1)(n-2)/6. Then 480 walks per triplet of dimensions, times n(n-1)(n-2)/6 ways to choose which triplet, gives 80n(n-1)(n-2), or 80n^3-240n^2+160n random walks in n-space, with steps in exactly 3 dimensions, that require 6 steps to return home.
We know from an extension of earlier reasoning that no 6-step walk that returns home can have steps in more than 3 dimensions, so we have accounted for all possibilities.
Thus the total number of random walks in n-space that require 6 steps to return home is 4n+84n^2-84n+80n^3-240n^2+160n, or 80n^3-156n^2+80n. The total possible number of 6-step walks in n-space is (2n)^6, or 64n^6. Thus the probability that a random walk in n-space will require 6 steps to return home is (80n^3-156n^2+80n)/64n^6, or (20n^2-39n+20)/16n^5, as given in the answer above.

***********

And that’s as far as I went!!

Eric Brahinsky
ebrahinsky@aol.com