Positive recurrent random walk on Z

Question

Let $S_n = \sum_{k=1}^n X_n$, $n \geq 1$, be a random walk defined on $\mathbb{Z}$, where $X_i$, $ i \geq 1$, are i.i.d. bounded integers random variables. It is possible $S_n$ to be positive recurrent?

Answer 1

Suppose it was possible for the chain given by a sum of iid $X_k$ to be positive recurrent. This is true in the trivial case of $X_k$ being constant (and zero) with probability 1, so assume $X_k$ takes on at least 2 values with positive probability each.

1.) It is should be immediate that $E[X_k]=0$ -- e.g. if instead the walk had negative drift, then for small $t\gt 0$

$P\big(S_n \gt 0\big) = P\big(t\cdot S_n \gt 0\big)=P\big(e^{t\cdot S_n} \gt 1\big)\leq E[e^{t\cdot S_n}] = E[e^{t\cdot X_1}]^k = M(t)^k= p^k$
for some $p\in(0,1)$, noting e.g. that by differentiating $M'(0) = \mu \lt 0$ and $M(0)= 1$, so for $t$ small enough $0\lt M(t)\lt 1$.

hence the expected number of visits to the positive integers is finite (geometric series). And thus the steady state probability of visiting positive integers is zero which implies $X_k$ takes on strictly non-positive values and the chain is transient. (For the case of positive drift, rerun the argument on $S_n^* := -S_n$)

Alternative justifications: You can also do this with SLLN or adapt the below CLT argument to the case of non-zero drift.

2.) Since the chain is positive recurrent, we have, for any $m\gt 0$
$P\big(S_n \gt m\big) \rightarrow c$ for some $c\in \big(0,1\big)$ and as $m\to \infty$, $c\to 0$
this implies
$P\big(\frac{S_n}{\sqrt{n}} \gt m\big) \rightarrow 0$

but by Central Limit Theorem
$\frac{S_n}{\sqrt{n}} \to N\big(0,\sigma^2\big)$ hence
$P\big(\frac{S_n}{\sqrt{n}} \gt m\big) \rightarrow c'$ for $c'\in \big(0,1\big)$
which is a contradiction.

addendum
for a slightly different finish with a few more details spelled out, consider that since the chain starts at state 0 and by assumption it is positive recurrent, it suffices to tease out a contradiction with $P\big(S_n =0\big)$.

By positive recurrence assumption $P\big(S_n = 0\big)\to \pi_0 \in (0,1)$, or $\big \vert P\big(S_n = 0\big) - \pi_0\big \vert \lt \epsilon$ for any $\epsilon \gt 0$ for $n\geq n^*$.

And we also have
$0\leq P\big(S_n = 0\big) = P\big(\frac{S_n}{\sqrt{n}} = 0\big) \lt \epsilon'$
for $n\geq n'$ by CLT (and e.g. using Stein's Method or Berry-Essen for explicit error bounds).

Now select $\epsilon: =\epsilon' := \frac{\pi_0}{3} $ and $m:=\max\big(n',n^*\big)$ and we get

$\frac{2}{3}\pi_0 \lt \Big \vert \big \vert\pi_0\big \vert- \big \vert P\big(\frac{S_{m}}{\sqrt{m}} = 0\big)\big \vert \Big \vert \leq \Big \vert \pi_0- P\big(\frac{S_{m}}{\sqrt{m}} = 0\big) \Big \vert=\big \vert P\big(S_{m} = 0\big) - \pi_0\big \vert \lt \epsilon = \frac{1}{3}\pi_0$
which is a contradiction