Random walk returning probability

Question

Consider a two-dimensional random walk, but this time the probabilities are not $1/4$, but some values $p_1, p_2, p_3, p_4$ with $\sum p_i=1$. For example, from $(0,0)$, it goes to $(1,0)$ with $p_1$, goes to $(0,1)$ with $p_2$ etc.

I am interested in the probability of going back to $(0,0)$, starting from $(0,0)$. In general, this probability is not 1. The question is, how to compute this probability?

Another question is, how to characterise the condition on $p_1, \cdots, p_4$ under which the probability is 1 or less 1?

Thanks.

Answer 1

The probability to return to the origin is $1$ if and only if $p_N=p_S$ and $p_W=p_E$.

To see this, note that the position $X_n$ of the random walk after $n$ steps is the sum of $n$ i.i.d. displacements with known distribution hence if the mean of these is not $(0,0)$, $X_n\to\infty$ almost surely, in particular, $$ P(\mathrm{return\ to}\ (0,0))\lt1. $$ The remaining case is when $p_N=p_S=\frac12p$ and $p_W=p_E=\frac12(1-p)$, then $$ 4\pi^2P(X_n=(0,0))=\iint E(\mathrm e^{\mathrm itX_{n}})\mathrm dt, $$ where the integral is over $(-\pi,\pi)^2$, whose area is $4\pi^2$. Furthermore, $$ E(\mathrm e^{\mathrm itX_{n}})=E(\mathrm e^{\mathrm itX_1})^n,\qquad E(\mathrm e^{\mathrm itX_1})=p\cos t_1+(1-p)\cos t_2, $$ hence summing up and considering $R=1+$ the number of returns to $(0,0)$, one gets $$ 4\pi^2E(R)=\iint\frac{\mathrm dt}{1-E(\mathrm e^{\mathrm itX_1})}=\iint\frac{\mathrm dt}{p(1-\cos t_1)+(1-p)(1-\cos t_2)}. $$ The convergence of the integral on the RHS depends on the behaviour of the denominator near $(0,0)$. Since this denominator is asymptotically between two multiples of $t_1^2+t_2^2$, a change to polar coordinate show that the convergence is run by $$ \int_0\frac{r\mathrm dr}{r^2}. $$ Finally $E(R)=+\infty$ for every $p$, hence $P(\mathrm{return\ to}\ (0,0))=1$.

In the transient case $\varrho\lt1$ with $\varrho=P(\mathrm{return\ to}\ (0,0))$, $R$ is geometrically distributed with parameter $\varrho$ hence $\varrho=1-1/E(R)$ where the same reasoning as above shows that $$ 4\pi^2E(R)=\iint\frac{\mathrm dt}{1-E(\mathrm e^{\mathrm itX_1})}=\iint\frac{\mathrm dt}{1-p_N\mathrm e^{\mathrm it_1}-p_S\mathrm e^{-\mathrm it_1}-p_W\mathrm e^{\mathrm it_2}-p_E\mathrm e^{-\mathrm it_2}}. $$

Answer 2

Hint: After step one, the probability of the walk returning to $0$ is $1/4$. After step two, you need to compute the number of paths and their lengths leading from $(0,0)$ to the current position... that is the number of such paths from one corner to another of a bounding defined by $(0,0)$ and the current position...

Another hint: The computation of the number of paths from one corner of a square to another on some integer grid can be separated on the $X$ coordinates and the Y coordinates... That means that the recursive function computing this is of the form $f(x,y) = g(f(x-1), f(y-1))$...

Answer 3

Let your walk be a string in the alphabet $\{N,E,S,W\}$, with respective probabilities $\{p_N,p_E,p_S,p_W\}$ of occurring. The only way to return to the origin is if the number of Ns and Ss are equal and the number of Es and Ws are equal. So we need to count the number of such strings of length $2n$.

For given $n$, there are $4^n$ possible walks. Of these, we need to count strings with equal numbers of $(N,S)$ and $(E,W)$ pairs. There are $n$ ways to write $n$ as the sum of two nonnegative integers $k$, $n-k$; let $k$ be the number of $(N,S)$ pairs. The probability that this happens is $$p_N^k\ p_S^k\ p_E^{n-k}\ p_W^{n-k}$$ times the multinomial coefficient $$\binom{2n}{k,k,n-k,n-k}.$$ The probability that you return "home" after $2n$ steps is therefore $$\sum_{k=0}^n \binom{2n}{k,k,n-k,n-k} p_N^k\ p_S^k\ p_E^{n-k}\ p_W^{n-k}.$$