asymmetric random walk

do asymmetric random walks also return to the origin infinitely?

-
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

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.

-

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.

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

-
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