Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Hi: this question is regarding the topological properties of random walks on a finite torus.

Consider an unbiased random walk on finite square lattice on a torus of linear dimension $L$. Place a trap at the origin, such that the random walk ends as soon as the walker lands in the trap.

If the walker begins at the origin, what is the probability that the path of the random walker will form a topologically trivial (contractible) loop on the torus after it has returned to the origin for the first time and is trapped?

More generally, I am interested in the probabilities the path having an arbitrary topological winding number at the first-return of the walker, and how this depends (or does not depend) on $L$.

thanks,

Chris

share|improve this question
    
The limit as the size of the torus goes to ∞ depends heavily on the dimension, because it is the same as the probability that the walker never returns to the start. Proof: Obviously this forms a lower bound because if the walker never returns to the start then it cannot land in the trap at the origin. However, if the size of the torus is at least N, then the probability that the walker takes more than N steps to return to the start is an upper bound. As N goes to ∞ the probability gets squeezed between these two. –  Will Sawin May 23 '12 at 19:29
    
The probability that the walker never returns to the start is well-known to be $0$ in dimensions 1 and 2 and positive in higher dimensions. –  Will Sawin May 23 '12 at 19:30
    
I realize I did not specify before: I am specifically interested 2 dimension random walk, so the walk will be recurrent. –  Chris May 24 '12 at 4:58
    
Instead of unfolding the torus in both directions, I suggest estimating the probability by unfolding the torus in one direction. That is, estimate the probability that the loop will wind around the torus in one direction (say the $x$ direction). The events that the loop winds in the $x$ or $y$ directions are not independent, but one or the other must occur for the loop to be nontrivial, so $P(x) \le P(x~\text{or}~y) \le 2 P(x)$. –  Douglas Zare May 24 '12 at 21:22
add comment

1 Answer

Say the walk starts at $0$. The lattice in the torus is the image of ${\mathbb Z}^n$ under a quotient map, and your random walk on the torus is the image of a random walk on ${\mathbb Z}^n$. The walk on the torus gives a nontrivial loop iff the walk on ${\mathbb Z}^n$ hits some member of $L{\mathbb Z}^n$ other than $0$ before returning to $0$. If $n=2$, because random walk on ${\mathbb Z}^2$ is recurrent, the probability of a nontrivial loop goes to $0$ as $L \to \infty$. If $n \ge 3$, random walk on ${\mathbb Z}^n$ is transient; if this walk never returns to $0$ its first hit on $L {\mathbb Z}^n$ must not be at $0$, so the probability of a nontrivial loop has a nonzero lower bound.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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