Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

do asymmetric random walks also return to the origin infinitely?

share|improve this question
    
No they do not. –  Did May 3 '11 at 19:57
    
Why not? Presumably because rand({0,1}) doesn't converge? –  Joseph Weissman May 3 '11 at 20:28
    
I'm writing out a proof for this, and I"m getting that $\sum f_n $ doesn't converge. –  gentisse May 3 '11 at 20:38

3 Answers 3

This is a consequence of the law of large numbers. The position $S_n$ at time $n$ is the sum of $S_0$ and of $n$ i.i.d. displacements, each with expectation $m\ne0$, hence $S_n/n\to m$ almost surely. In particular, $|S_n|\ge |m|n/2$ for every $n\ge N$ where $N$ is random and almost surely finite, which implies $S_n\ne0$. Since $(S_n)$ does not visit zero after time $N$, the number of visits of zero is almost surely finite. The starting point $S_0$ is irrelevant.

share|improve this answer

No. Heuristic: If the walk goes right with probability $1/2+\alpha/2>1/2$ then the expected position after $n$ steps is $\alpha n,$ while the expected variation is only $O(\sqrt n).$ Thus the walk crosses the origin only finitely often.

share|improve this answer
    
Oh, clarification. When I say asymmetric, I meant say that the random walk goes right three steps for every one step to the left, each with probability 1/2. –  gentisse May 3 '11 at 21:04

Proof sketch: let $P(x,y)$ be the generating function of all walks which end up at the origin for the first time, with $x$ meaning left and $y$ meaning right. You can write a recurrence relation for the walks and deduce an expression for $P$ by solving a quadratic. Now substitute $pt$ for $x$ and $1-p$ for $y$.

share|improve this answer
    
does it make a difference if the random walk does not start at the origin? –  gentisse May 3 '11 at 21:00
    
@gentisse: It makes no difference to the finiteness of the the visits to the origin - if it starts to the right of the origin it will on average visit the origin fewer times (perhaps never) than in the original question, and if it starts to the left of the origin it will almost certainly reach (or jump over) the origin once, after which you will be close to the original question. –  Henry May 3 '11 at 21:48

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.