If you want a rough answer, it is something of the order of $\frac{3^n}{n}$. This random paths are easier than self avoiding walks, you can think of these paths in this way: If you consider the even steps, these paths describe a random walk in a triangular lattice, which is a bit easier to describe. Each step $X_i$ is given by adding a sixth root of unity $\rho^{j}$, $j= 1,2,\dots, 6$. And we want to understand when $S_n = X_1 + X_2 + \dots X_n$ is equal to zero. After $n$ steps what you have $S_n = A_n 1 + B_n\rho + C_n \rho^2 = (A_n - C_n)1 + (B_n + C_n)\rho$ (here I'm using the fact that $\rho^2 = \rho -1$). You want to estimate the probability that $A_n - C_n = 0$ and $B_n + C_n = 0$.

I think the heuristic is that $A_n, B_n, C_n$ behave like standard random walks in the line (This is also true for $A_n - C_n$, and $B_n + C_n$) and so the probability of $A_n - C_n = 0$ or that $B_n - C_n = 0$ is of the order of $\frac{1}{\sqrt{n}}$, if these events were independent this gives you $(\frac{1}{\sqrt{n}})^2 = \frac{1}{n}$.

Observe also that this answer is the same as in the square lattice, and it seems this estimate should hold for more general tilings. See also Random walk on a Penrose tiling.

easier: you are just looking for a diagonal entry on a power of a certain infinite adjacency matrix. $\endgroup$ – LSpice May 5 at 15:05