5
$\begingroup$

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

Improve this question
$\endgroup$
2
  • 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$
    – Tsuyoshi Ito
    Oct 10, 2012 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$
    – Tsuyoshi Ito
    Oct 10, 2012 at 14:29

1 Answer 1

Reset to default
4
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • 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$
    – András Salamon
    Oct 22, 2012 at 16:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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