Probability of returning to the origin

Question

I have been trying to solve the following problem: What is the probability of the particle returning back to the origin $o$ on a triangular lattice in $k$ steps?

The approach used for the regular integer grid is not working for this problem, namely the particle should make the same number of steps in horizontal direction and the same number of steps in vertical direction. So I am stuck a bit. I also tried to find the lower and upper bounds, but my tries were not really successful. Any hints how to tackle this problem are appreciated.

Answer 1

I doubt that there is a nice closed form, but there's a nice heuristic argument that (correctly) gives you an asymptotic for the answer. I'll assume implicitly that we're talking about a grid of equilateral triangles with unit side length. The geometry doesn't matter to the answer, but this is a convenient coordinate system in which to perform the calculation.

You can, essentially, apply the central limit theorem to this problem: as the number of steps grows large, your position will start to look like a normal distribution. More precisely, one could say that if you took $n$ copies of a variable taking uniform randoms values on the same unit hexagon, the distribution of their sum divided by $\sqrt{n}$ would tend towards a multivariate normal distribution with mean at the origin and a covariance matrix related to the original distribution. The choice of the regular grid helps us since the symmetry lets us know that the covariance matrix is just going to be some multiple of the identity.

In particular, the variance of the $x$ coordinates in the original distribution is just $\frac{1}3\cdot 1^2 + \frac{2}3\cdot \left(\frac{1}2\right)^2 = 1/2$ - so the covariance matrix is just going to be $\frac{1}2I$.

You can then imagine that the probability or returning exactly to the origin after $n$ steps is similar to the probability of choosing some vector from the multivariate normal distribution $N(0,1/2)$ and having it so that, when multiplied by $\sqrt{n}$, the closest lattice point is $0$ - equivalently, asking that the original vector is within the hexagon of in-radius $\frac{1}{2\sqrt{n}}$ centered at the origin. This probability is roughly the PDF of $N(0,1/2)$ evaluated at $(0,0)$ (which is $\frac{1}{\pi}$) by the area of the given hexagon (which is $\frac{\sqrt{3}}{2n}$). This gives the answer to be roughly: $$\frac{\sqrt{3}}{2\pi n}.$$ You can formally justify this argument by use of any of the various versions of the local central limit theorem - though you have to do a fair amount of digging into literature to figure out exactly how good this bound is. You can also check that this agrees very well with experimental data - here's a plot of the actual probabilities divided by this estimate for $n=1$ to $50$:

Answer 2

(NOT FULL ANSWER)

Here is just an idea, so correct me if I am wrong:

---

Firstly I assume the grid to be of equilateral triangles.

Now if the particle has to return to the origin, if we represent each movement as a vector:

$$\vec{a}_1+\vec{a}_2+\vec{a}_3+\cdots+\vec{a}_k =\vec{0}$$

For a regular cartesian system, $\vec{a}_i$ can be :

$$\vec{a}_i \in \left\{ \pm \hat{i} , \pm \frac{1}{2} \hat{i} \pm \frac{\sqrt3}{2} \hat{j} \right\}$$

Now if we apply a respective linear transformation such that:

$$\hat{i} \to 2\hat{i} \ \ \& \ \ \hat{j} \to \frac{2}{\sqrt3} \hat{j}$$

$$\therefore \vec{a}_i \in \left\{ \pm 2 \hat{i} \ , \ \pm\hat{i}\pm\hat{j} \right\} $$

Now if we break it into respective components :

$$\vec{a}_i = x_i \hat{i} \ + \ y_i\hat{j}$$

We can put the foolowing constraints:

$$x_1+x_2+x_3+\cdots+x_k = 0 \tag1$$

$$\text{where } x_i \in \{ -2,-1,1,2 \} $$

and

$$y_1+y_2+y_3+\cdots+y_k =0 \tag2$$

$$\text{where } y_i \in \{ -1,0,1 \}.$$

This becomes a well known question in combinatorics of finding the integral solutions (I read its called 'fictious partitions' but I think the name may vary regionally) .

Eg. for $(1),$

No. of solutions : = coefficient of $t^0$ in $\left( t^{-2} +t^{-1} +t +t^2 \right)^k$ = $A$ (Let's say)

Similarly for $(2)$ you get $B$.

Now find the total arrangements in the various combinations for $\vec{a}_i$.

This will be the total no. of cases where it will return back to origin.

---

You can try to find the total cases in a similar method.

---

EDIT:

I just realised there must be another constraint that whenever $y_i = \pm \hat{j}$, $x_i \neq \pm \hat{i}$

But I can't figure out how to apply that constraint......But I suppose the rest of the answer is a decent framework for any other ideas.

Answer 3

In the plane $\mathbb{Z}^2$, the probability of returning back to the origin after $2n$ steps equals

$$u_{2n}^{(2)}=\frac{1}{4^{2n}}\binom{2n}{n}\sum_{k=0}^n \binom{n}{k}^2. $$

It happens that there is a nice closed form for this expression, namely

$$u_{2n}^{(2)}=\frac{1}{4^{2n}}\binom{2n}{n}^2. $$

In $\mathbb{Z}^3$, on the other hand, one can use combinatorial arguments to show that

$$u_{2n}^{(3)} = \frac{1}{6^{2n}}\sum_{i+j+k=n} \binom{2n}{2i,2j,2k}\binom{2i}{i}\binom{2j}{j}\binom{2k}{k},$$

where i'm using multinomial coefficients. This can be rewritten as

$$u_{2n}^{(3)} = \frac{1}{6^{2n}}\binom{2n}{n}\sum_{i+j+k=n} \binom{n}{i,j,k}^2,$$

but I do not know a nice closed form for this sum. You now see where this is going : by counting steps in the $6$ directions of the triangular lattice, the probability of returning to $0$ after $n$ steps is

$$u_n = \frac{1}{6^{2n}}\sum_{a+b+c+d+e+f=n\\a+b=e+d\\b+c=e+f} \binom{n}{a,b,c,d,e,f}.$$

I do not know if this answer will satisfy you, but there might not be a nice closed form for this expression.