Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question

1 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

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.

share|improve this answer
    
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. –  mfolz Jun 28 '11 at 5:31

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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