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.
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
Here's the Sage code I used:
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.