5
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks for the link. I have nothing 'against' electrical networks (anyone working in random walks needs to be familiar with them!); I was just hoping for an especially simple solution involving some sort of symmetry argument. But it seems unlikely that there is one. $\endgroup$ – mfolz Jun 28 '11 at 5:31
1
$\begingroup$

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$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ This is quite a nice argument, but based on what OP wrote I have a feeling that they were asking for a “symmetry argument” that would directly show that the event in question has the same probability as its complement by somehow mapping them to each other. The symmetry you used is of a different sort, involving the fact that all edges of $G_n$ are equally likely to be in $T_n$. $\endgroup$ – Dan Romik Jun 6 '19 at 23:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.