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.
Best Answer
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}.$$