Let $X_n$ be a one-dimensional random walk with $p \neq 0.5$. Show that $P(\lim_{n \rightarrow \infty} \frac{1}{n} X_n = 0)$ equals $0$.

Question

Let $X_n$ be a one-dimensional random walk on the integers that starts at $0$ (as normally) but has $p \neq \frac{1}{2}$, i.e. so that it moves to its right neighbor with probability $p$ and left neighbor with probability $1-p$ at each step. In other words, the walk is biased to left or right and should therefore be "located" infinitely far to the left or right respectively when an infinite amount of time has passed, informally speaking. So how do I prove that $P(\lim_{n \rightarrow \infty} \frac{1}{n} X_n = 0)$ equals $0$, i.e. that the there is zero probability that $\lim_{n \rightarrow \infty} \frac{1}{n} X_n = 0$?

Answer 1

Consider $n$ random variables $Y_i$ for $i = [1,n]$ where, WLOG, $Y_i = 1$ if we go to the right and $Y_i = -1$ otherwise. These $n$ variables are independent Bernoulli trials with (WLOG) $Pr(Y_i = 1) = p > 0.5$.

Then we have that $X_n = \sum_{i=1}^{n} Y_i$. This can be interpreted as the final co-ordinate after completion of the random walk.

The expected value of the final co-ordinate is given by $$E[X_n] = \mu = \sum_{i=1}^{n} E[Y_i] = \sum_{i=1}^{n} (1\times p -1\times (1-p)) = (2p-1)n$$

Via Chernoff Bounds we have that

$$Pr(X_n > (1 + \delta)\mu) \le e^{\frac{-\mu \delta^2}{3}}, 0 < \delta \le 1 $$ $$ = e^{-n\frac{(2p - 1)\delta^2}{3}}$$

Now observe that $p > 0.5 \implies E[X_n] > 0$, i.e. we expect to finish the random walk on a non-zero co-ordinate.

Now observe that the probability of the random variable $X_n$ deviating from the expected value by some small factor of $\delta$ is bounded above by an exponentially decreasing function in $n$. Thus, as $n \to \infty$ we have that $e^{-n\frac{(2p - 1)\delta^2}{3}} \to 0$

This can be interpreted as the probability of the finishing point $X_n$ deviating away from its expected value is zero as the size of the walk gets larger. Therefore $\lim_{n\to\infty}X_n = n(2p-1)$ Thus $$\lim_{n\to\infty}\frac{1}{n}X_n = \lim_{n\to\infty}\frac{1}{n}(2p-1)n = 2p-1 \not= 0$$ $$\implies Pr(\lim_{n\to\infty}\frac{1}{n}X_n = 0) = 0$$

Q.E.D.

Alternatively

We saw that $E[X_n] = (2p-1)n > 0$.

By the law of large numbers, we have that as $\lim_{n\to\infty}X_n =E[X_n]$.

Thus $$\lim_{n\to\infty}\frac{1}{n}X_n = \lim_{n\to\infty}\frac{1}{n}(2p-1)n = 2p-1 \not= 0$$ $$\implies Pr(\lim_{n\to\infty}\frac{1}{n}X_n = 0) = 0$$

Q.E.D.