random walk returning probability 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_{i=1}^4 p_i=1$. For example, from (0,0), it goes to (1,0) with p_1, goes to (0,1) with p_2 etc.
The question is how to compute the probability x of going back to (0,0), starting from (0,0). In general, this probability is not 1.  
Thanks.
 A: Since the number of visits has geometric distribution, it's enough to find its expected value. 
Here is one approach: since you can solve the one-dimensional case, treat the two-dimensional case as two "interleaved" one-dimensional walks, one north-south, the other east-west. Let's say $p_1$ is the probability of north, $p_2$ is the probability of south. Then at each step, we do a step from the north-south walk with probability $p_1+p_2$ and a step from the east-west walk with probability $p_3+p_4$; each step of the north-south walk is north with probability $p_1/(p_1+p_2)$ and south with probability $p_2/(p_1+p_2)$.
So then the probability of being back at the origin at time $N$ is the sum over $m$ of 
$P(X=m)
P(\text{north-south walk at 0 after $m$ steps})P(\text{east-west walk at 0 after $N-m$ steps})$
where $X$ is Binomial$(N, p_1+p_2)$. 
Sum over $N$ to get the total expected number of visits. 
I don't see that this will give you a closed-form answer, but it may at least make it easier to compute and/or obtain bounds. 
A: A special case where we can avoid one of the two sums in James Martin's answer is when the "determinant" $p_1p_3-p_2p_4$ of the four probabilities is zero. Then we can treat the random walk as a "sum" of two independent one-dimensional random walks, one taking steps $(+1/2, +1/2)$ or $(-1/2,-1/2)$, the other taking steps $(+1/2,-1/2)$ or $(-1/2,+1/2)$. The original walk is back at the origin precisely when both these 1D-walks are.
If the transition probabilities of the two component walks are $p, (1-p)$ and $q, (1-q)$ respectively, then the expected number of visits to the origin (including the start) is $$\sum_{n=0}^\infty \binom{2n}{n}^2 p^nq^n(1-p)^n(1-q)^n.$$
In terms of the original probabilities, $$pq(1-p)(1-q) = (p_1+p_2)(p_2+p_3)(p_3+p_4)(p_4+p_1).$$
I'm no expert on this type of sum, but according to Maple, $$\sum_{n=0}^\infty \binom{2n}{n}^2 x^n = \frac2{\pi} EllipticK(4\sqrt{x}).$$
The probability of never returning is the reciprocal of this (with $x=pq(1-p)(1-q)$), in other words 
$$\frac{\pi}{2EllipticK(4\sqrt{(p_1+p_2)(p_2+p_3)(p_3+p_4)(p_4+p_1)})}.$$
An obvious question is whether this holds also when $p_1p_3 \neq p_2p_4$. Off the top of my head I don't see why it couldn't.
