<p>this ref covers it. </p>

<blockquote>
  <p>In sections 5 &amp; 6 we use the elliptic integral to express the probability, less than one, that certain biased random walks return to the origin. The probability of a return to the origin for these walks can then be computed accurately and easily using Gauss' arithmetic-geometric mean (AGM) method to evaluate the elliptic integral.</p>
</blockquote>

<p>[1] <a href="http://www.jstor.org/stable/2323770" rel="nofollow">Recurrence of Simple Random Walk in the Plane</a>
Terence R. Shore and Douglas B. Tyler
The American Mathematical Monthly
Vol. 100, No. 2 (Feb., 1993), pp. 144-149</p>

CC BY-SA 3.0
2012-10-22T16:58:13.410Z
Note that this paper only considers those walks for which the product of up/down probabilities is the same as the product of left/right probabilities.  There is then a closed form expression, and decidability presumably follows in at least some reasonable machine models.  The OP doesn't seem to specify this restriction, though.
András Salamon
CC BY-SA 3.0
2012-10-10T15:13:14.777Z
2012-10-10T15:13:14.777Z
vzn
<p>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. </p>

<p>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$?</p>

CC BY-SA 3.0
2012-10-10T14:28:43.250Z
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)
Tsuyoshi Ito
CC BY-SA 3.0
2012-10-10T14:29:22.657Z
(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.
Tsuyoshi Ito
<computability><pr.probability><random-walks><decidability>
Random walk returning probability
user29271
# Random walk returning probability

(Asked by: username_0 on 2012-10-08)

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

**Tags:** computability, pr.probability, random-walks, decidability

> **Comments:**
> **username_1**: 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)  
> **username_1**: (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.  

---

## 1 answers

### Answer by username_2 on 2012-10-10. Score: 4

this ref covers it.

> In sections 5 & 6 we use the elliptic integral to express the probability, less than one, that certain biased random walks return to the origin. The probability of a return to the origin for these walks can then be computed accurately and easily using Gauss' arithmetic-geometric mean (AGM) method to evaluate the elliptic integral.

[1] [Recurrence of Simple Random Walk in the Plane](http://www.jstor.org/stable/2323770)
Terence R. Shore and Douglas B. Tyler
The American Mathematical Monthly
Vol. 100, No. 2 (Feb., 1993), pp. 144-149

> **Comments:**
> **username_3**: Note that this paper only considers those walks for which the product of up/down probabilities is the same as the product of left/right probabilities.  There is then a closed form expression, and decidability presumably follows in at least some reasonable machine models.  The OP doesn't seem to specify this restriction, though.  

---

