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

Question

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.

Any advice is appreciated.

Answer 1

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.add_edge((x,y), (x+1, y))
            if (x+y)%2==0: g.add_edge((x,y), (x,y-1))
    g.delete_vertex((0,0))
    vs = list(g.vertices())
    origNbs = [vs.index(v) for v in [(-1,0), (1,0), (0,-1)]]
    A = g.adjacency_matrix()
    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.