11
$\begingroup$

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


          RandWalk11
          RandWalk3
          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:


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


$\endgroup$
  • 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$ – Noam D. Elkies Sep 12 '15 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$ – Anthony Quas Sep 12 '15 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$ – Ori Gurel-Gurevich Sep 12 '15 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$ – Joseph O'Rourke Sep 12 '15 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 '18 at 4:44
18
$\begingroup$

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

$\endgroup$
  • $\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$ – Joseph O'Rourke Sep 12 '15 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 '15 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 '15 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$ – Joseph O'Rourke Sep 12 '15 at 17:30

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.