# Take a random walk on a Christmas tree, starting at the top. What is the probability of returning to the top?

Consider a "Christmas tree lattice" composed of equilateral triangles, as shown. The lattice extends down infinitely.

Start at the top vertex and take a random walk. At each step, move to a randomly chosen neighboring vertex, each with equal probability. Re-visiting vertices is allowed.

What is the probability of returning to the top?

## Context

I was reading about Polya's random walk constants, and with all the Christmas trees appearing these days, this question naturally arose.

## My thoughts

Let $$p(k)$$ be the probability of returning to the top for the first time on the $$k$$th step, and let $$P(n)=\sum\limits_{k=2}^n p(k)$$. We are looking for $$P(\infty)$$.

According to my calculations, based on counting paths:
$$p(2)=\frac14$$
$$p(3)=\frac{1}{4^2}=\frac{1}{16}$$
$$p(4)=\frac{2}{4^3}+\frac{1}{4^2\cdot3}=\frac{5}{96}$$
$$p(5)=\frac{3}{4^4}+\frac{4}{4^3\cdot 3}=\frac{25}{768}$$
$$p(6)=\frac{6}{4^5}+\frac{21}{4^4 6}+\frac{12}{4^3 6^2}+\frac{4}{4^2 6^3}=\frac{179}{6912}$$
Calculating gets progressively harder.

$$P(6)=\frac14+\frac{1}{16}+\frac{5}{96}+\frac{25}{768}+\frac{179}{6912}=\approx 0.423032$$.

I guess $$P(\infty)<1$$, because whenever the path touches the boundary of the tree, the probability of going down is double the probability of going up.

If we have a triangular lattice (instead of a Christmas tree), the probability of returning to the origin is presumably $$1$$.

## Edit

In the comments, @user has provided values of $$P(n)$$ for $$n=5,6,50,100, 150, 200, 250,300$$. (I got the same results for $$n=5,6$$.)

Here is a graph of $$P(n)$$ against $$n$$, for $$n=2,6,50,100,150,200,250,300$$.

• I can't answer the question, but I'd think $p(2)=\frac14$ Commented Dec 20, 2023 at 12:24
• @Toffomat You're right. I have corrected it.
– Dan
Commented Dec 20, 2023 at 12:28
• $50: 0.627516, 100: 0.668383, 150: 0.688919, 200: 0.702192, 250: 0.711817, 300: 0.719279$.
– user
Commented Dec 21, 2023 at 22:37
• $P(5)=0.397135$, $P(6)=0.423032$.
– user
Commented Dec 21, 2023 at 23:12
• @user I have editted to clarify the first point on the graph.
– Dan
Commented Dec 22, 2023 at 12:10

The probability to come back to the top is one. Just take 5 more copies of the tree and tile the plane with them, getting a tiling of the plane by triangles. With a good definition of what happens on the boundaries of the tree, we have a random walk in the plane with expectation zero which will be null recurrent. Rigorous details can be painful, but I am pretty sure of the result.

Edit. What follows is not a complete proof, since some argument (martingale? coupling? harmonic functions?) is missing. Denote $$w=e^{i\pi/3}$$ and consider the lattice $$E=\mathbb{Z}+w\mathbb{Z}+w^2\mathbb{Z}.$$

We consider $$(U_n)$$ iid such that $$\Pr(U_n=u)=1/6$$ for $$u=\pm 1,\pm w,\pm w^2.$$ We consider $$(X_n)$$ iid such that $$\Pr(X_n=x)=1/4$$ if $$x=\pm 1$$ and $$\Pr(X_n=x)=1/8$$ if $$x=\pm w,\ \pm w^2.$$ We consider $$(Y_n)$$ iid such that $$\Pr(Y_n=y)=1/4$$ if $$y=\pm w$$ and $$\Pr(Y_n=y)=1/8$$ if $$y=\pm 1,\ \pm w^2.$$ We consider $$(Z_n)$$ iid such that $$\Pr(Z_n=z)=1/4$$ if $$z=\pm w^2$$ and $$\Pr(Z_n=z)=1/8$$ if $$z=\pm 1,\ \pm w.$$

Now we consider the Markov chain $$(S_n)$$ on $$E$$ such that $$S_{n+1}=s+U_{n+1}$$ if $$s=S_n=a+wb+cw^2$$ is such that either $$a=b=c=0$$ or $$a,b,c$$ are such that at least either $$a,b\neq 0,$$ or $$b,c\neq 0$$, or $$c,a\neq 0.$$

In other cases $$S_{n+1}=s+X_{n+1}$$ if $$s\in \mathbb{Z}\setminus \{0\}$$, $$S_{n+1}=s+Y_{n+1}$$ if $$s\in w\mathbb{Z}\setminus \{0\}$$,$$S_{n+1}=s+Z_{n+1}$$ if $$s\in w^2\mathbb{Z}\setminus \{0\}.$$

This chain is so close to the null recurrent random walk $$S'_n=u+U_1+\cdots+U_n$$ that one guess that it should also be null recurrent.

Finally coming back to the initial chain $$C_n$$ on the Chrismas tree it is clear that $$C_n$$ is obtained by folding $$E$$ on the tree in an obvious way.

Final edit. I found the solution in the theorem page 133 of the book'Random walks and electric networks' by Peter Doyle and Laurie Snell, Carus Mathematical Monographs 1984, which shows that $$S_n$$ is recurrent. Indeed $$S'_n$$ is recurrent and the transition probabilities $$p_{ij}$$ and $$p'(ij)$$ of these two Markov chains on $$E$$ are such that there exist $$u>0$$ and $$v$$ satisfiying $$up_{ij} The proof of the fact that the random walk on the Christmas tree will hit the top an infinite number of times is complete.

• My instant answer also was $1$. But trying to prove I replaced this tree by a bamboo with probabilities $1/3$ of going up and $2/3$ of going down. I found that the probability of never coming home is $4/9$ for such bamboo, not $0$. However it doesn't mean anything about this tree, where probabilities of going up and going down become more and more equal. But your argumentation is also rather weak Commented Dec 20, 2023 at 15:02
• To me it seems very reasonable that the probability is 1, as we move further down the tree the movement go more and more to be like a fair random walk so there is a probability one that we will go up(a lot) the tree infinitly many times and surely at the and we will go back to the base of the tree
– RT1
Commented Dec 20, 2023 at 19:24
• @RT1 But, for me, the problem is that, as the walker approaches the top of the tree, the walk becomes less like a fair random walk, so it is not clear if the walker will move up to the top a an infinite number of times.
– Dan
Commented Dec 21, 2023 at 22:24

This is not a proof, but just some evidence that the probability is $$1$$.

In the comments, @user provided the following values:

$$P(50)=0.627516$$
$$P(100)=0.668383$$
$$P(150)=0.688919$$
$$P(200)=0.702192$$
$$P(250)=0.711817$$
$$P(300)=0.719279$$

(@user also provided values of $$P(5)$$ and $$P(6)$$, which matched my calculated values.)

Taking a clue from here, I conjectured that $$P(n)$$ approaches something like $$f(n)=1-\dfrac{a}{\log n+b}$$ for some $$a$$ and $$b$$. I found that with $$a=2$$ and $$b=1.37$$, we have:

$$P(50)=1.009912\times f(50)$$
$$P(100)=1.004662\times f(100)$$
$$P(150)=1.003448\times f(150)$$
$$P(200)=1.003025\times f(200)$$
$$P(250)=1.002862\times f(250)$$
$$P(300)=1.002807\times f(300)$$

Since $$\lim\limits_{n\to\infty}f(n)=1$$, this suggests that $$\lim\limits_{n\to\infty}P(n)=1$$.

• Why can't multiplication coefficient drop below 1? Commented Jan 8 at 15:50
• @Smylic Sorry, I don't know.
– Dan
Commented Jan 8 at 15:51