1

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.

MandelBroccoli
  • 655
  • 1
    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? – David G. Stork Jul 09 '22 at 01: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)$. – Henry Jul 09 '22 at 01: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. – MandelBroccoli Jul 09 '22 at 01: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". – MandelBroccoli Jul 09 '22 at 02:03
  • 1
    @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*. – David G. Stork Jul 09 '22 at 02:25
  • @DavidG.Stork I may have worded it ambiguously. I was trying to convey that the origin is an absorbing state. – MandelBroccoli Jul 09 '22 at 02:34
  • Hah! Absorbing state?? How would we ever guess that?? – David G. Stork Jul 09 '22 at 03:05
  • @Henry I'm unable to fully understand ... you formulation seems nice ... I think it'd brilliant if you could provide a proof , maybe as an answer ? – C.C. Jul 09 '22 at 09:02
  • You ask for a probability. The sum you reference is not a probability and the answer you have accepted does not provide a probability. – Daniel Mathias Jul 09 '22 at 11:49
  • @DanielMathias Indeed. However, it shows the number of walks that are $2k$ moves for $k$ from $1$ to $10.$ To find the probability is simple computation from here - divide the number of walks that are $2k$ (for some $k$) by $3^{2k}$ and sum them. Also note that there can be no walks that are an odd length so this solves the problem. – MandelBroccoli Jul 09 '22 at 16:21

1 Answers1

2

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.

ploosu2
  • 8,707
  • 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$. – ploosu2 Jul 09 '22 at 06:16
  • Hm... so for the $n=6$ case I count $30,$ not $24.$ – MandelBroccoli Jul 09 '22 at 06: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. – MandelBroccoli Jul 09 '22 at 07:16
  • Oh, right! You need to sum all pairs. I'll edit. – ploosu2 Jul 09 '22 at 07: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$ – Henry Jul 13 '22 at 00:38