Polya's famous theorem states that a simple random walk on $\mathbb{Z}^d$ is transient if $d>2$ and recurrent if $d=1,2$. This theorem is included in almost every textbook on probability theory.

As far as I know there are four proofs:

  1. By a pure combinatorial enumeration of the walks that return to the starting point via stirling' formula.

  2. A Fourier transformation computation of the Green function $G(x,y)=\sum_nP_x(S_n=y)$.

  3. Foster-Lyapunov criterion for recurrent and transient.

  4. By Lyons's theorem, construct an unit flow of finite energy from origin to infinity .

My question is , are there more proofs?

  • 2
    $\begingroup$ You have 'recurrent' and 'transient' switched backwards in your first sentence and should fix this. You might be interested in arxiv.org/pdf/1301.3916v2.pdf . $\endgroup$ – Robert Bryant May 3 '14 at 10:28
  • $\begingroup$ @RobertBryant:thank you, corrected. $\endgroup$ – zemora May 3 '14 at 11:20

Shrirang Mare (2013) gives a proof of Polya's theorem by formulating it as an electric circuit problem and using Rayleigh’s short-cut method from the classical theory of electricity. A similar proof was given earlier by Tetali (1991) and by Doyle (1998).

Jonathan Novak gives the "potpourri proof" mentioned by Robert Bryant, a proof "which cobbles together basic methods from combinatorics (decompositions and generating functions), special functions (Bessel function identities), quantum field theory (Borel transform), and asymptotic analysis (Laplace’s method)."

A drunk man will find his way home, but a drunk bird may get lost forever. — Shizuo Kakutani

  • 3
    $\begingroup$ The proof by Shrirang Mare is an exposition of the proof by Peter Doyle. I only bother to mention this because it's Doyle's PhD dissertation after all .... $\endgroup$ – Chan-Ho Suh Jun 9 '15 at 2:02

In principle one could also mention the theorem of Kanai (1986) on stability of parabolicity ($\equiv$ recurrence) with respect to rough isometries, which, in particular, implies that recurrence/transience of $\mathbb Z^d$ is equivalent to that of $\mathbb R^d$. However, it ultimately boils down to the same Dirichlet form considerations which go back to Royden (if not to Kelvin).

As for Carlo Beenakker's reply I don't think it's a good idea to advertize these half baked arguments. The "electric" ones just obfuscate very clear exposition of Terry Lyons (1983) without even mentioning his paper, whereas the "potpourri proof" is just a fancy way to deal with generating functions.


It is amusing that a unit flow of finite energy in the $d$-dimensional lattice for $d \ge 3$ can be easily constructed from Polya's urn; see ``Polya's theorem on random walks via Polya's urn'', Amer. Math. Monthly 117 (2010), no. 3, 220–231.

  • $\begingroup$ For those who have access, this paper can be accessed online on the journal's website here: jstor.org/stable/10.4169/000298910X480072 For those who don't, it can also be accessed freely on the author's website here: pages.uoregon.edu/dlevin/polya.pdf $\endgroup$ – Tom Church May 12 '14 at 2:27
  • $\begingroup$ So for any urn process (two colors) with the number of balls increases to infinity, one can get a flow on $\mathbb{Z}^2$? $\endgroup$ – zemora May 14 '14 at 6:37

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.