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.

I am interested in the probability $x$ of going back to (0,0), starting from (0,0). In general, this probability is not 1 (I guess that $x$ is not rational in general). The question is, given a probability threshold $r$, is it decidable that $x\geq r$?

• At the risk of stating the obvious: One of the possible approaches to proving the decidability of this problem (with a caveat stated later) is to find one computable sequence which approaches x from below and another computable sequence which approaches x from above. Here “computable” means that the i-th term of the sequence can be computed given i, p_1, p_2, p_3, and p_4. These two sequences together give you an algorithm to decide whether x≥r under the promise that x≠r (this is the caveat I mentioned above). (more) Oct 10 '12 at 14:28
• (cond’d) A computable sequence which approaches x from below is easy, but I do not know how to define a computable sequence which approaches x from above. Such a sequence might be found by looking at a proof of x≠1 closely. Oct 10 '12 at 14:29