What is the probability that a random walk on $\mathbb{Z}^2$ will hit $(1,0)$ before $(2,0)$?

Suppose we have a 2-dimensional simple random walk: we start at $$(0,0)$$, and at every step, we add a random unit vector in one of the four cardinal directions selected independently and uniformly.

It is well-known that this procedure will with probability $$1$$ hit every element of $$\mathbb{Z}^2$$ infinitely often. Thus, it makes sense to ask about the probability that such a walk will hit $$(1,0)$$ before $$(2,0)$$.

Running some Monte Carlo simulations, it looks like the walk first lands on $$(1,0)$$ something like $$70\%$$ of the time, but I don't have much confidence about the accuracy of these simulations since I cannot actually run them all to completion and have to either throw out the unfinished trials or make a guess as to how they will conclude. Some more precise simulations show that the walk first lands on $$(1,0)$$ with probability at least $$0.607$$ and on $$(2,0)$$ with probability at least $$0.153$$.

Is there a known exact value for this probability, and how can it be computed in general for any two points on the square lattice? I'm also interested in a general formula for the probability of encountering $$n$$ points in a given order.

• What we are looking for is a discrete harmonic function on the square lattice, with boundary conditions $f(1,0)=1$, $f(2,0)=0$, and then evaluate $f(0,0)$. Feb 6 '21 at 21:59
• @WillM.: I don't follow your symmetry argument. Why should the probability of reaching $(2,0)$ versus $(1,1)$ first be identical? This is certainly not the case two moves out. Feb 6 '21 at 23:32
• @HagenvonEitzen In addition, it's safe to assume that $f(n,m) \approx 0.5$ when $n$ and $m$ are large. I've done some inefficient numerical calculations to compute $f(0,0)$ recursively, and it appears that the value is larger than $1 / \sqrt{2}$. I would guess that the value lies around $0.723$. Feb 7 '21 at 10:19
• There is a good chance that it is $2-4/\pi$ (it agrees with Jeroen's calculation), which is the effective resistance between the origin and (2,0). I calculated what the equivalent 3-node circuit should be for the effective resistances $(1/2,1/2, 2-4/\pi)$, and the desired probability came out to be exactly that. You can read the effective resistance values here: mathpages.com/home/kmath668/kmath668.htm.
– E-A
May 24 '21 at 3:51
• For your more general question, you wanted to calculate the probability of hitting a sequence of points in a given chain. In the resistor analogy, to hit point $a$ before $b,c,d$, you’d want the voltage at $a$ to be 1 and the voltage at $b,c,d$ to be 0. The probability of hitting $a$ before $b,c,d$ starting at $x$ is then the voltage at $x$. If you put a point source at each of $a,b,c,d$ you could calculate the implied voltage differences using E-A’s link. By taking linear combinations of them, you can get the $1,0,0,0$ voltages at those points and the voltage at any point $x$.
– Eric
May 27 '21 at 1:34

Update: I originally got the probability is $$1-2/\pi$$, but there seemed to be mistake taking the wrong order of limits. Taking the right order I got $$2-4/\pi$$.

Denote $$f_n(\mathbf{x})$$ the number of ways to end at $$\mathbf{x} = (x,y)$$ after $$n$$ steps. Denote $$g_n(\mathbf{x})$$ the number of ways to end at $$\mathbf{x}$$ after $$n$$ steps for the first time. Denote $$h_n(\mathbf{x},\mathbf{y})$$ the number of ways to end at $$\mathbf{x}$$ after $$n$$ steps for the first time having not passed through $$\mathbf{y}$$.

Note

$$h_n(\mathbf{x},\mathbf{y}) = g_n(\mathbf{x}) - \sum_{k=0}^{n-1} h_k(\mathbf{y},\mathbf{x}) g_{n-k}(\mathbf{x}-\mathbf{y}) \tag{1}$$ The desired probability is $$\lim_{n \rightarrow \infty} \frac{1}{4^n} \sum_{k=0}^n h_k((1,0),(2,0))4^{n-k}$$. Similarly

$$g_n (\mathbf{x}) = f_n(\mathbf{x}) - \sum_{k=0}^{n-1} g_k(\mathbf{x}) f_{n-k}(\mathbf{0}) \tag{2} \\$$

Thus in principle we can successively solve for $$f_n$$, $$g_n$$, $$h_n$$, sum, and take the limit.

To compute $$f_n$$:

For $$n$$ odd, $$f_n((2l,0)) = 0, \forall l \in \mathbb{N}$$. For $$n = 2m$$

$$f_{2m} ((2l,0)) = \sum_{i=0}^{m} {2m \choose 2i} {2i \choose i+l} {2m-2i \choose m-i}. \\$$ The terms are $$0$$ for $$i < l$$. $${2i \choose i+l}$$ is the number of ways of stepping horizontally $$2i$$ times and ending at $$l$$. $${2m-2i \choose m-i}$$ is similar, but for vertical steps. $${2m \choose 2i}$$ is the number of ways of alternating between $$2i$$ horizontal steps and $$2m-2i$$ vertical steps.

Expanding the terms and simplifying

\begin{align} f_{2m} ((2l,0)) &= {2m \choose m+l} \sum_{i=0}^{m} {m-l \choose i-l} {m+l \choose m-i} \\ &= {2m \choose m+l}^2 \end{align}

by Vandermonde's Convolution. Similarly, for $$n$$ even, $$f_n((1,0)) = 0$$, and

\begin{align} f_{2m+1}((1,0)) &= \sum_{i=0}^m {2m+1 \choose 2i+1} {2i+1 \choose i+1} {2m-2i \choose m-i} \\ &= {2m+1 \choose m} \sum_{i=0}^m {m+1 \choose i+1} {m \choose i} \\ &= {2m+1 \choose m}^2 \end{align}

To compute $$g_n$$:

For even $$n, g_n((1,0)) = 0$$. For $$n = 2m+1, \mathbf{x} = (1,0), (2)$$ becomes

$$\sum_{i=0}^m g_{2i+1}((1,0)) {2m - 2i \choose m-i }^2 = {2m+1 \choose m}^2 \tag{3}$$

Recursively computing a few cases $$g_1((1,0)) = 1, g_3((1,0)) = 5, g_5((1,0)) = 44, g_7((1,0)) = 469$$. This doesn't appear in OEIS and I don't recognize a pattern.

For odd $$n$$, $$g_n((2,0)) = 0$$. For $$n=2m$$, $$(2)$$ gives $$\sum_{i=0}^m g_{2i}((2,0)) {2m - 2i \choose m-i }^2 = {2m \choose m+1}^2 \tag{4}$$

$$(3)$$ and $$(4)$$ are convolutions and can be solved using generating functions. Let

\begin{align} A(z) &= \sum_{k \geq 0} {2k \choose k}^2 z^{2k} \\ B(z) &= \sum_{k \geq 0} {2k+1 \choose k}^2 z^{2k+1} \\ C(z) &= \sum_{k \geq 0} {2k \choose k+1}^2 z^{2k} \\ G_{(1,0)}(z) &= \sum_{k \geq 0} g_{2k+1}((1,0))z^{2k+1} \\ G_{(2,0)}(z) &= \sum_{k \geq 0} g_{2k}((2,0))z^{2k} \\ H_{(\mathbf{x},\mathbf{y})}(z) &= \sum_{k \geq 0} h_k(\mathbf{x},\mathbf{y}) z^k \end{align}

The following have the same coefficients by $$(3)$$ therefore are equal

$$G_{(1,0)}(z)A(z) = B(z) \tag{5}$$

Similarly by $$(4)$$ $$G_{(2,0)}(z)A(z) = C(z) \tag{6}$$

Comment: It would be nice to find $$h_k$$ in its closed form, but it seems not easy. The complete elliptical integral of the first kind has series $$K(t) = \frac{\pi}{2} \sum_{k=0}^\infty \left(\frac{(2k)!}{2^{2k}(k!)^2}\right)^2 t^{2k}$$ hence $$A(z) = \frac{2}{\pi} K(4 z)$$.

For $$B(z)$$, substituting $${2k+1 \choose k} = \frac{1}{2} {2(k+1) \choose k+1}$$ gives $$1 + 4zB(z) = A(z)$$. By $$(5)$$

$$4zG_{(1,0)}(z) = -\frac{1}{A(z)} + 1$$

By explicitly differentiating the RHS and setting $$z=0$$ I verified $$g_1((1,0)) = 1, g_3((1,0)) = 5, g_5((1,0)) = 44$$. So to find $$g_k$$ it seems we need the power series for $$1/K(t)$$.

Probability:

We're almost done!

Multiplying $$(1)$$ by $$z^n$$ and summing over $$n$$ $$H_{((1,0),(2,0))}(z) = G_{(1,0)}(z) - H_{((2,0),(1,0))}(z) G_{(1,0)}(z).$$ since $$g_k(\mathbf{x}-\mathbf{y}) = g_k(\mathbf{y}-\mathbf{x})$$ by symmetry (for even $$n$$ the equation says $$0 = 0$$). Similarly $$H_{((2,0),(1,0))} = G_{(2,0)}(z) - H_{((1,0),(2,0))}(z) G_{(1,0)}(z)$$

Combining $$H_{((1,0),(2,0))}(z) = G_{(1,0)}(z) - \left(G_{(2,0)}(z) - H_{((1,0),(2,0))}(z) G_{(1,0)}(z)\right) G_{(1,0)}(z)$$ So \begin{align} H_{(1,0),(2,0)}(z) &= G_{(1,0)}(z) \frac{1 - G_{(2,0)}(z)}{1 - G_{(1,0)}(z)^2} \\ &= B(z) \frac{A(z) - C(z)}{A(z)^2 - B(z)^2} \\ &= \frac{A(z) - C(z)}{2(A(z) - B(z))} - \frac{A(z) - C(z)}{2(A(z)+B(z))} \\ \end{align}

Update: Differentiating the RHS a few times gives $$H_{((1,0),(2,0))} = z+5z^3 + \cdots$$ so this seems correct. The probability is

$$\lim_{n \rightarrow \infty} \frac{1}{4^n} \sum_{k=0}^n h_k((1,0),(2,0)) 4^{n-k} = H_{((1,0),(2,0))}(1/4)$$

Originally I took the wrong order of limits and got $$1-\pi/2$$. We have to be a bit careful since $$A(1/4) = \frac{2}{\pi} K(1) = + \infty$$. To compute this we need to use

\begin{align} H_{((1,0),(2,0))}(1/4) &= \lim_{z \rightarrow 1/4^{+}} H_{((1,0),(2,0))}(z) \\ &= \lim_{z \rightarrow 1/4^{+}} \left(\frac{A(z) - C(z)}{2(A(z) - B(z))} - \frac{A(z) - C(z)}{2(A(z)+B(z))}\right) \end{align} since $$A(z), B(z), C(z)$$ are convergent and continuous for $$0\leq z<1/4$$.

Inputing these into mathematica with Limit[(1 - 1/(4 x)) (2 EllipticK[16 x^2])/[Pi] + 1/(4 x) , x -> 1/4] and Limit[(2 EllipticK[16 x^2])/[Pi] - x^2 HypergeometricPFQ[{3/2, 3/2, 2, 2}, {1, 3, 3}, 16 x^2], x -> 1/4] gives $$\lim_{z \rightarrow 1/4^+} (A(z) - B(z)) = 1, \lim_{z \rightarrow 1/4^+} (A(z) - C(z)) = 4 - 8/\pi$$ respectively.

I don't know how Mathematica put the second in a closed form (the first I think I could do since its in terms of $$K$$), but since $$\lim_{z \rightarrow 1/4^+} (A(z) + B(z)) = +\infty$$ we get

$$H_{((1,0),(2,0))}(1/4) = 2 - \frac{4}{\pi}$$

• The first series evaluates to $2-4/\pi$; splitting into even-odd indices and using generating functions, the other two evaluate to $\frac{2}{\sqrt{3}}\mp \frac{2}{3} \left(2 \sqrt{3}-3\right)$, which means the last term that is the difference of their reciprocals is $1/2$. So, unless I've made an arithmetic error, your answer doesn't agree with the comments by a factor of $4$, unless the leading $1/2$ is meant to be a $2$, or there's some other error (or, plausibly, the original comment is off). Tl;dr : computations are mostly right, I think. May 28 '21 at 22:27
• I did more calculation. A way to know for sure is to calculate $\lim_{z \rightarrow 1/4} \lim_{n \rightarrow \infty} A(z) - C(z)$, where they have been truncated to $n$ terms, instead of $\lim_{n \rightarrow \infty} \lim_{z \rightarrow 1/4} A(z) - C(z)$. This ensures convergence. May 29 '21 at 14:48
• This looks really good but numerical simulations suggest the answer is closer to $.7$ than $.3$. I'm not sure where, but I strongly suspect a factor of $2$ was dropped somewhere in your work. May 29 '21 at 17:48
• Seconding all the comments about a missing factor of $2$ here: you can just directly add up the possible paths of length $\le5$ and see that the probability must be at least $\frac{189}{512}\approx 0.369$. May 29 '21 at 18:15
• @tinklehoy: I agree with your explicit computations of $g_k((1,0))$, so I think everything up to that point is likely correct. Can you use the final expression to obtain coefficients of $h_k((1,0),(2,0))$? I have $1,0,5,0,42,0,429,0,4866,\ldots$ via direct computation. May 30 '21 at 18:40

Not an answer but actually trying this I got a probability of $$0.73$$. The code is An explanation is as follows:

$$1)$$ Start at $$t=0$$ in the complex plain

$$2)$$ Add one of the following randomly $$(1,-1,i,-i)$$ to $$t$$

$$3)$$ Check if $$t=1$$ or $$t=2$$ (if so, stop and record this result)

$$4)$$ Check if the magnitude of the resulting number is greater than $$100$$

$$5)$$ If not, got back to step $$2)$$. If it is, then choose randomly from $$t=1$$ or $$t=2$$, record the result, and stop

I do this $$10,000$$ times and record the result each time. The key assumption I made was that for $$|t|>100$$ the probability of getting $$t=1$$ or $$t=2$$ first was about $$50\%$$ each.

Update: I re-ran my code with $$\lambda=10^6$$ and got a final probability of $$P=0.726992$$. This agrees heavily with the conjectured answer of $$2-\frac{4}{\pi}$$ as

$$\left|2-\frac{4}{\pi}-\frac{726992}{10^6}\right|<10^{-3}$$