In an infinite two-dimensional square-shaped grid, we define four directions, north, south, east, west. We thus have $4^n$ random walks of length $n$. If we end where we started, for every north step we have a south one, and similarly for east and west. Supposing $k$ north-south and $n/2 -k$ east-west steps, we find that the number of possible walks is $$\sum_{k=0}^{n/2}\frac{n!}{k!^2(n/2-k!)!^2}={n\choose n/2}\sum_{k=0}^{n/2}{n/2\choose k}^2={n\choose n/2}^2$$ a beautiful result that hints a cleaner interpretation. How can we see this directly from the grid?
Combinatorics – Number of Random Walks Starting and Ending at the Origin
combinatoricsrandom walk
Related Solutions
An exact computation to answer question 1. is simple in principle, difficult to do exactly with no computer, and the result is frankly not very interesting. Question 2. is more interesting since, after 3600 steps on a graph of 25 vertices with diameter 10, the random walk is close to its stationary distribution.
The random walk is equivalent to the simple reversible random walk on the augmented graph where one adds 3 supplementary loops to each corner, 2 to each side vertex not a corner, and 1 to each other vertex. Every vertex in the augmented graph has degree 5 hence the stationary distribution is uniform. The Markov chain is aperiodic hence, at any large time, the probability to be at any of the vertices of this graph with 25 vertices is approximately 1/25.
The probability to be in any set S of vertices is approximately the size of S divided by 25. There are 4 corners hence the probability to be at one corner is approximately 4/25. There are 16 side squares hence the probability to be on one side is approximately 16/25.
Thanks for the interesting and creative problem.
It made me curious as to how large the path could get for Energy = 20, so I mapped it:
The origin is the green cell and the possible end cells are yellow. The cells that your question asks for percentages on are the orange squares.
With problems like these with a gajillion possibilities, I lean heavily toward using a simulator.
I ran 4 simulations, each for 100 million trials, and since all 4 of them gave similar results, I concluded that the number of trials for each run was large enough. Here are the results:
------------------------ Original answer end ------------------------
Edit: This may be overkill, but I was curious how many distinct stopping points there were, and I wanted to see how the probabilities decreased as the endpoint got further from the origin.
So, I altered the sim again and re-ran it for 2,147,483,646 runs, and here are those results. The percentages are out of all possible paths, not just for the white slice shown. I am showing only the slice because it considers all 161 distinct points (and makes it small enough to read, but you'll probably need to save it to your machine to view it). All other possible ending points are a reflection of these points.
Quite a few possible ending points far from the origin were never hit once, and some were hit only once (15,10; 16,7; and 17,0)
Best Answer
Since $n$ must be even in order for the walk to be closed, I’ll write $n=2m$. Let $n_N,n_S,n_E$, and $n_W$ be the number of steps north, south, east, and west, respectively. Then $n_N=n_S$ and $n_E=n_W$, so $n_N+n_E=n_S+n_W=m$ and $n_N+n_W=n_S+n_E=m$.
Note also that if we choose $n_N,n_S,n_E$, and $n_W$ so that $n_N+n_E=n_S+n_W=m$ and $n_N+n_W=n_S+n_E=m$, then automatically $n_N=n_S$ and $n_E=n_W$.
Now imagine charting an $n$-step walk by starting with a strip of $n$ squares and labelling each square N, S, E, or W for steps north, south, easy, and west, respectively. However, we’ll do it in a slightly odd way. First choose any $m$ squares and mark them $\nearrow$. These will be the $m$ steps that go either north or east. Then choose any $m$ squares and mark them $\nwarrow$; these will be the $m$ steps that go either north or west. Clearly this procedure can be carried out in $\binom{2m}m^2$ ways. Now go through the strip and change the markings according the following rules:
It follows from the remark in the second paragraph that we’ve laid out a chart for a path that returns to the origin, and it’s not hard to see that every $n$-step path that returns to the origin has a chart that can be produced in this way. There are $\binom{2m}m^2$ charts produced in this way, so there are $\binom{2m}m^2$ $n$-step paths that return to the origin.