Random Walks

Let's consider the following situation. We start at the origin (0,0) and want to get to the point (4,4). However, we can only move one step at a time, either horizontally or vertically. We are constrained to move within the grid of points shown. Given this constraint, horizontal movement can be to the left or right and vertical movement can be up or down. However, we have no control over this step by step movement. It is completely random. On average, how many steps should be required to reach our destination?

FIGURE 1

I set up a program in SageMathCell to simulate this random walk over 1,000 trials. The result returned a median walk of 60 steps. What happens as the grid grows larger? I was interested in looking at the relationship between the size of the grid and the average number of steps required to reach the goal. Here are the results for grids with of size 1 to 21 and a graphical representation in FIGURE 2:

1	2	3	4	5	6	7	8	9	10	11
2	14	34	60	108	156	224	289	388	534	587

12	13	14	15	16	17	18	19	20	21
762	884	1104	1270	1420	1657	1785	2114	2442	2693

FIGURE 2

Not surprisingly the graph seems to be that of a parabola and my best fit formula, based on the above data, gives its equation as \(y=5.2 \, x^2\). 

This type of walk can be extended to 3 dimensions so that from (0, 0, 0) we need to get to (2, 2, 2) for example:

FIGURE 3

Running a thousand trials again on SageMathCell again, we get a median of 40 steps with a minimum of 6 (the least possible) and a maximum of 344. What's surprising is the vastly different lengths of these random walks. For example, with a cube of side 10, a median of 3075 steps is returned from the thousand trials but the maximum is 46826 and the minimum is 114. Here are the results (the simulation was too slow for sides greater than 10):

1	2	3	4	5	6	7	8	9	10
7	40	117	254	473	793	1129	1786	2390	3075

FIGURE 4

Although it looks parabolic, it's probably cubic and, if this is the case, then an equation of \(y=0.27 \, x^3 \) seems the best fit. In any case, this post is not meant to be definitive. It's just meant to clarify my thinking. I'll need to pursue this further and improve on the accuracy of these possible equations.