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

combinatoricsmarkov chainsprobabilityrandom walk

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.

The given lattice

Any advice is appreciated.

Best Answer

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.

Related Question