# Probability that random walk returns to starting vertex in at most 20 moves

While trying to solve a somewhat unrelated problem, I came across this problem.

If I start at the origin of this lattice (which is the same as a hexagonal/honeycomb lattice), I want to figure out the probability that the walk is $$k\leq 20$$ moves and only returns to the origin for the first time on the $$k$$th move.

Perhaps more clearly, the problem is to find a random walk (starting at the origin) on this lattice which is at most 20 moves, but the origin is an absorbing state.

Now, the source gives a similar problem with solution, without this additional condition of the origin being an absorbing state. In essence, we find that the probability that a random walk on this lattice returns to the origin in $$2n$$ moves (perhaps returning multiple times in between) is $$\sum_{k=0}^n \binom{2k}{k}\binom{n}{k}^2.$$

However, I'm not sure how relevant this is, since we don't know exactly how many times the random walk would return to the origin in between.

• But your problem statement is identical to your cited work. If the walk returns on step 11, 14, and 19, then it indeed returns "for the first time in at most 20 steps." Such a case is precisely what is computed by your cited literature (save for a factor of 2).... no? Jul 9, 2022 at 1:29
• If that expression divided by $3^{2n}$ is the probability of returning to the start after exactly $2n$ steps not necessarily for the first time - let's call that probability $g(n)$ - then the probability of returning to the start for the first time after exactly $2n$ steps would be $f(n)=g(n)-\sum\limits_{k=1}^{n-1} f(k)g(n-k)$ and the probability of returning to the start for the first time after at most $2n$ steps would be $\sum\limits_{k=1}^{n-1} f(k)$. Jul 9, 2022 at 1:50
• @DavidG.Stork No. What the cited work is saying is that if a walk returns in, for example, 12 steps, it is counting, for example, moving back and forth between the origin and a point adjacent to it 6 times. However, my question is about the path only returning once to the origin i.e. it cannot return to the origin before the 12th step. Jul 9, 2022 at 1:55
• @DavidG.Stork Perhaps more clearly, the problem would be something like "the walk is stopped after the origin is reached. what is the probability that the walk is stopped within 20 moves". Jul 9, 2022 at 2:03
• @MandelBroccoli: Sorry, no. Read your words carefully: "returns to the origin for the first time in at most 20 moves". Thus if a route returns on steps 11, 17, and 19, IT RETURNS TO THE ORIGIN FOR THE FIRST TIME IN AT MOST 20 MOVES. Jul 9, 2022 at 2:25

The values $$k\leq 20$$ aren't too big to brute force. Because you need to come back, you only have to consider the graph up to $$\frac{k}{2}$$ distance to the origin. Then remove the origin and for each pair of neighbors of the origin count $$k-2$$-walks on that graph starting from first and ending in second. Sum those up and that's your answer. We get

2 :  3
4 :  6
6 :  30
8 :  180
10 :  1188
12 :  8322
14 :  60714
16 :  456174
18 :  3504630
20 :  27398106


Here's the Sage code I used:

def f(k):
if k<2: return 0
g = Graph()
lim = k//2
for y in range(-lim, lim+1):
for x in range(-lim, lim+1):
g.delete_vertex((0,0))
vs = list(g.vertices())
origNbs = [vs.index(v) for v in [(-1,0), (1,0), (0,-1)]]
A = A^(k-2)
return sum(A[vI][vJ] for vI in origNbs for vJ in origNbs)

for k in range(2, 21, 2):
print (k, ": ", f(k))


I'm probably exaggerating on the $$y$$-range because you need two steps to move a level, but it's not too slow even like that.

• Oh, and after return, the walk can move freely, so multiply those values by $3^{n-k}$ if you want the walks of length $n$. Jul 9, 2022 at 6:16
• Hm... so for the $n=6$ case I count $30,$ not $24.$ Jul 9, 2022 at 6:56
• Ah, I see the problem: "for each neighbor of the origin count $k-2$-walks on that graph starting and returning to it." There are walks that exist that don't start and end at the same neighbor vertex e.g. simply going around a rectangle/6-cycle, which is $6$ steps. Jul 9, 2022 at 7:16
• Oh, right! You need to sum all pairs. I'll edit. Jul 9, 2022 at 7:23
• Not only does this sequence not appear in OEIS, but none of $456174$ and $3504630$ and $27398106$ appear in any other sequences. Similarly for the following terms $217209474$, $1741917492$, $14104103076$, $115132444686$ Jul 13, 2022 at 0:38