Probability of returning to starting point before hitting adjacent point for RW on Z^2

Question

Consider (simple) random walk on $\mathbb{Z}^2$ started at the origin. The probability that the walk returns to the origin before hitting $(0,1)$ is $1/2$.

To see this, let $a(x)$ be the potential kernel for random walk on $\mathbb{Z}^2$. Then $2a(x)$ counts the expected number of visits to the origin by a random walk started at the origin before the first time it hits $x$. Let $p$ denote the probability that the walk returns to the origin before hitting $x$.

Hence,

\begin{equation*} 2a(x) = (1-p)+p(1-p)+p^2(1-p)+\cdots = \frac{1}{1-p}, \end{equation*}

and consequently,

\begin{equation*} p = 1-\frac{1}{2a(x)}. \end{equation*}

On the other hand, one can also obtain that

\begin{equation*} a(x) = \frac{1}{(2\pi)^2}\int_{[-\pi,\pi]^2}\frac{1-\exp(-ix\cdot\theta)}{1-\phi(\theta)}d\theta, \end{equation*}

where $\phi(\theta)$ is the characteristic function of the random walk. In particular, one can work out that $a(0,1) = 1$, and hence that the probability we are looking for is $1/2$. With some more work, one can also work out what the answer would be for, say, $(3,2)$ in place of $(0,1)$ (it turns out to be $(16\pi+3)/(16\pi+6)$).

But the expression for $(0,1)$ suggests that there is some sort of underlying symmetry. Is there a simple argument for why this is the case?

I'm aware that this problem can be rephrased in terms of electrical networks, and that there appears to be a simple solution involving symmetry in that setting, but I'd prefer a simple solution involving symmetry without these techniques, if possible.

Answer 1

See the solutions of Problems 2.3 and 3.4(B) in the following course:

link text

Sorry that these solutions do use electrical networks. But in this course a complete axiomatic theory of electrical networks is presented. So you may avoid their use simply replacing 'network', 'voltage', and 'current' throughout by 'table', 'chair', and 'tankard' :-)

Edit Yet another proof which perhaps you will like more. This proof still uses the language of electric networks. The required assertion is equivalent to the assertion that the conductance R between adjacent nodes of a square lattice equals 2. Let us compute R. Remove the resistor between the adjacent nodes. We get a network of conductance R-1. Now draw the conjugate network; see the dashed lines in the figure.

alt text http://www.freeimagehosting.net/t/5ff18.jpg

The conjugate network is the same as the initial one (is obtained just by 90 degree rotation). Thus their conductances are the same. On the other hand,

(1) conjugate networks have reciprocal conductances.

Thus R-1=1/(R-1) and hence R=2. QED

The nontrivial assertion (1) used in the proof follows from similar assertion for finite networks [Duffin] and the results on approximation of infinite networks by finite ones [Flanders].

[Duffin] R.J. Duffin, Distributed and lumped networks, J. Math. Mech. 8:5 (1959), 793--826.

[Flanders] H. Flanders, Infinite Networks: I - Resistive Networks, IEEE TRANS. CIRCUIT THEORY, CT-18:3 (1971), 323--331.

Answer 2

There is a symmetry argument based on uniform spanning trees. If you ask for the effective resistance across an edge $e$ in the discrete torus torus $G_n=[-n,n]^2$ with periodic boundary conditions, it reduces to the chance that a uniform random spanning tree $T_n$ in $G_n$ contains $e$. Since $T_n$ has $4n^2-1$ edges and $G_n$ has $8n^2$ edges, symmetry implies the probability an edge $e$ of $G_n$ is in $T_n$ equals $(4n^2-1)/(8n^2)$ which tends to $1/2$ as $n \to \infty$.