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

  • 2
    $\begingroup$ 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) $\endgroup$ Oct 10 '12 at 14:28
  • 2
    $\begingroup$ (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. $\endgroup$ Oct 10 '12 at 14:29

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 Terence R. Shore and Douglas B. Tyler The American Mathematical Monthly Vol. 100, No. 2 (Feb., 1993), pp. 144-149

  • 1
    $\begingroup$ 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. $\endgroup$ Oct 22 '12 at 16:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.