4
$\begingroup$

Do asymmetric random walks also return to the origin infinitely?

  • 0
    I'm writing out a proof for this, and I"m getting that $\sum f_n $ doesn't converge.2011-05-03

5 Answers 5

4

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.

1

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.

  • 0
    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.2011-05-03
0

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

  • 0
    @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.2011-05-03
0

No, it doesn't.

For a random walk, consider point of view $v_k$ as:

  1. let $+1$ and $-k$ be the two "fozen points", $p_k$ is the probability hitting $+1$, $1-p_k$ hitting $-k$, or, equivalently
  2. let $-1$ and $+k$ be the two "fozen points", $q_k$ is the probability hitting $-1$, $1-q_k$ hitting $+k$.

With such two "forks", we can construct view $v_{k+1}$, such that

  1. let $+1$ and $-(k+1)$ be the two "fozen points", $p_{k+1}$ is the probability hitting $+1$, $1-p_{k+1}$ hitting $-{k+1}$, or, equivalently
  2. let $-1$ and $+{k+1}$ be the two "fozen points", $q_{k+1}$ is the probability hitting $-1$, $1-q_{k+1}$ hitting $+{k+1}$.

We have: $p_{k+1} = \frac{p_k}{1-(1-p_k)(1-q_k)}$ and $q_{k+1} = \frac{q_k}{1-(1-p_k)(1-q_k)}$.

Obviously, $p_{k+1}/q_{k+1} = p_k/q_k$, so points $(p_k, q_k)$ line up on a line from the origin $(0,0)$.

Also, $1/p_k > p_{k+1}/p_k = q_{k+1}/q_k < 1/q_k$, so points $(p_k,q_k)$ are bounded in the square $(0,0)$, $(1,0)$, $(1,1)$ and $(0,1)$.

So, starting if $p_1 = 1-q_1 < 1/2$, the probability of hitting $+1$ is $p_\infty = 1/q_1 < 1$, vice versa. $p_1 = q_1 = 1/2$ is the only situation that has probability $1$ to hit both $+1$ and $-1$.

Hence, the probability of returning to origin, is less than $1$, unless the random walk is symmetric.

0

It depends. If you consider a Random Walk in a Random Environment, it may be asymmetric and recurrent. See https://arxiv.org/pdf/0707.3160.pdf

Also, if your walk is homogeneous,

$ X_i = \begin{cases} +1 \text{ with probability } 2/3\\ -2 \text{ with probability } 1/3\end{cases}$

let $S_n = \sum_{i=1}^n X_1$ this walk is recurrent. Indeed, by Donsker Theorem $\frac{S_{[tn]}}{\sqrt{n}} \to B_t $ where $B_t$ is a Brownian motion. This implies that $P(S_n <0 \text{ infinitely often and } S_n >0 \text{ infinitely often} ) = 1$

Since to cross from the negative to the positive this walk must first reach $0$, we conclude that this asymetric random walk visit $0$ infinitely many times.