Suppose a random walk on $\mathbb{Z}^2$ takes a step left or right with probability $\frac{1}{4}$, but up with probability $\frac{1}{2} p$ and down with probability $\frac{1}{2} (1-p)$, where $p \in [0,1]$ indicates a constant bias against north when $p < \frac{1}{2}$. (So we have $\frac{1}{4}+\frac{1}{4}+ p \frac{1}{2}+ (1-p)\frac{1}{2}=1$.)

For example, here are two $10^5$-step random walks with $p=0.49$:

          The red dot marks the starting origin.

What is the probability of returning to the origin for $p < \frac{1}{2}$?

It is not $0$, and I don't think Polya's recurrence theorem holds unless $p = \frac{1}{2}$.

Added. Here is a distribution of path endpoints, again using $p=0.49$, and paths of $10^5$ steps:

          $500$ random walk endpoints, with $p=0.49$ bias against north.

  • 2
    $\begingroup$ Also, the subscript suggests that each step $n$ comes with its own $p_n$, but the text suggests that $p_n$ is a constant; which is it? $\endgroup$ Sep 12, 2015 at 3:30
  • 2
    $\begingroup$ It looks as though there is a massive body on the left in the figure rather than the bottom. $\endgroup$ Sep 12, 2015 at 5:02
  • $\begingroup$ What Anthony said + I'd expect the last point to be at around -500 rather then -200 as it is now. $\endgroup$ Sep 12, 2015 at 5:39
  • 1
    $\begingroup$ Sorry for the lack of clarity. I meant for the subscript $n$ to mean "north"; poor notation choice, now just $p$. Yes, $p$ is a constant. The bias against north in my simulations is tiny, so runs look almost as random as unbiased random walks: left, right, up, down, with just a slight bias against up. E.g., $p=0.25$ converts the walks into downward trails. $\endgroup$ Sep 12, 2015 at 12:14
  • 1
    $\begingroup$ @JosephO'Rourke For your information, you're right, Polya's result only hold when the random walk is centered (centered means that the expectation of the first movement is zero). This is very general and you do not need to have a nearest neighbor random walk. For every random walk on $\mathbb{Z}$ or on $\mathbb{Z}^2$ with exponential moments, the random walk is transient if and only if it is non centered. $\endgroup$
    – M. Dus
    Oct 18, 2018 at 4:44

1 Answer 1


Let $E_n$ denote the probability of the first return after $n$ steps, and let $P_n$ denote the probability of return after $n$ steps (but not necessarily the first return). Note that $E_n=P_n=0$ if $n$ is odd.
We are interested in $E= E(p)= \sum_{n=1}^{\infty} E_n$. Now note that for $n\ge 1$ $$ P_n = E_n + \sum_{k=1}^{n-1} E_k P_{n-k}, $$ from which it follows that $$ P = \sum_{n=1}^{\infty} P_n = \sum_{n=1}^{\infty} E_n + \sum_{k=1}^{\infty} E_k \sum_{j=1}^{\infty} P_j, $$ or in other words $P= E(1+P)$, or $$ E= \frac{P}{1+P}. $$ All this is due to Polya, of course.

Now $P_n$ is quite easy to calculate: for odd $n$ it is zero, and for even $n$ it is simply (counting $a$ steps to the right and left, and $b$ steps up and down) $$ P_n = \sum_{a+b=n/2} \frac{n!}{a!^2 b!^2} \Big(\frac 14\Big)^a \Big(\frac 14\Big)^a \Big(\frac 12p \Big)^b \Big(\frac 12 (1-p)\Big)^b. $$ We can also express $P_n$ as a double integral: $$ \frac{1}{(2\pi )^2} \int_{-\pi}^{\pi} \int_{-\pi}^{\pi} \Big( \frac 14 e^{i\alpha} + \frac 14 e^{-i\alpha} + \frac 12p e^{i\beta} + \frac 12 (1-p) e^{-i\beta} \Big)^n d\alpha d\beta. $$ From this we can see that $$ 1+P= \frac{1}{(2\pi)^2} \int_{-\pi}^{\pi} \int_{-\pi}^{\pi} \frac{2}{2-(\cos \alpha + \cos \beta + i(2p-1)\sin \beta)} d\alpha d\beta. $$

Note that when $p=\tfrac 12$ this integral diverges, and we recover Polya's theorem that $E=1$. For any given $p<\tfrac 12$ we may clearly calculate the integral. Moreover, it is not hard to get asymptotics from the above, and show that $P$ behaves like $\log (1-2p)^{-1}$ for $p$ near $\tfrac 12$ (forgetting constants here).

  • $\begingroup$ Very nice! I wonder if there is a typo in your final integral. For $p=\frac{3}{8}$, it evaluates to approx $78.7$, which leads to $P \approx 0.99$, which doesn't seem right... $\endgroup$ Sep 12, 2015 at 16:14
  • $\begingroup$ How are you evaluating the integral? Since it is singular, some care would be needed, and maybe the numerics are off? (The formula looks fine to me, but I'll see if I can put in asymptotics easily. And I imagine you didn't forget to divide by $4\pi^2$?) $\endgroup$
    – Lucia
    Sep 12, 2015 at 16:21
  • 1
    $\begingroup$ Oh I see your confusion. Your numerics are fine. You get $P=0.99$ and then $E$ which is the probability you want is $P/(1+P)$ which is about $1/2$. Sorry for calling the final answer $E$ (for exact return) rather than $P$. $\endgroup$
    – Lucia
    Sep 12, 2015 at 16:34
  • 4
    $\begingroup$ Here is one data point. For $p=\frac{1}{4}$, Mathematica evaluates the integral to $32 \sqrt{\frac{1}{33} \left(9+4 \sqrt{3}\right)} \pi K\left(-\frac{8}{11} \left(4+3 \sqrt{3}\right)\right)$ (where $K()$ is the complete elliptic integral of the 1st kind), which evals to about $61.8$, which leads to $P \approx 0.57$ and $E \approx 0.36$. $\endgroup$ Sep 12, 2015 at 17:30
  • $\begingroup$ How do you obtain the integral representation? Is that some trivial complex analysis? Or is it just a known formula? $\endgroup$ Apr 3, 2020 at 13:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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