Random walk with positive drift

Question

I'm working on something where the following claim, if true, would be quite helpful:

Let $S$ be a random variable distributed over $\{-1,0\}\cup\mathbb N$ with $\mathbb E[S]>0$.

Consider a one dimensional random walk with step size $S$, starting at $1$. Is it true that, with nonzero probability, the random walk never reaches 0?

Intuitively this claim seems true (as the random walk has positive drift) but I'm not sure how to show it. If the claim does not hold in general, are there other conditions we can impose on the distribution of $S$ that would make the claim true?

Answer 1

Here is a partial answer, which proves the claim for Bernoulli random walks.

Let $S_i\in\{-1,1\}$ be independent step variables with $P(S_i=-1) =p$ and $P(S_i=1) = 1-p$, where $p<\frac12$ and denote $X_n = 1+\sum_{i=1}^nS_i$ as the random walk. Furter, we introduce $T_0 = \inf\{n:X_n=0\}$ as the random variable that denotes the time the random walk first hits $0$. Then, by the Hitting Time Theorem,

$$ P(T_0=n) = \frac{P(X_n=0)}n $$

and consequently, the probability that the random walk hits $0$ at some point is given by

$$ P(T_0 < \infty) =\sum_{n=1}^\infty P(T_0=n)= \sum_{n=1}^\infty \frac{P(X_n=0)}n. $$

Since for even time instants, $P(X_{2k}=0)=0$ and odd time instants, $P(X_{2k+1}=0) = p^{k+1}(1-p)^k\binom{2k+1}{k+1}$, we get

$$ P(T_0 < \infty) = \sum_{k=0}^\infty \frac{p^{k+1}(1-p)^k\binom{2k+1}{k+1}}{2k+1} = \frac{p}{1-p},$$

where the last equality has been found by WolframAlpha. This means that the probability that the random walk never hits $0$ is given by $P(T_0 = \infty) = \frac{1-2p}{1-p}>0$.

This approach directly generalizes to the more general case, where $P(S = -1)+P(S=0)<\frac12$, which is always "dominated" by some Bernoulli random walk.

Answer 2

To verify the general case, you can use a simple argument based on the Markov property of the random walk:

Let $(S_n)_{n\in\mathbb{N}}$ be an i.i.d. sequence with marginal distribution $\mathcal{L}(S)$. By the law of large numbers (and $\mathbb{E}(S)>0$) there exists $N\in\mathbb{N}$ such that $\mathbb{P}(\sum_{k=1}^n S_k \geq 1\ \forall n\geq N)>0$, since almost surely $\lim_{n\to\infty}\frac1n \sum_{k=1}^n S_k=\mathbb{E}(S)>0$

Since $N$ is finite, there must be some $0\leq n_0<N$ such that \begin{equation}\mathbb{P}\Bigg(\sum_{k=1}^{n_0} S_k =\min\Big\{\sum_{k=1}^n S_k, n\in\mathbb{N}_0\Big\}\Bigg)>0.\end{equation}

But that forces the event $\{\sum_{k=n_0+1}^n S_k\geq 0$ for all $n>n_0\}$ to have strictly positive probability. Due to the fact that $(S_n)_{n>n_0}$ has the same distribution as $(S_n)_{n\in\mathbb{N}}$, this proves your claim.

In fact you can show that given your step-size distribution (bounded from below by -1) the probability you ask for is the unique root of $x^2=g(x)$ in $(0,1)$, where $g(x)=\mathbb{E}(x^S)$ is the corresponding probability generating function.

Answer 3

The increments of your random walk (i.e. draws from $S$) are always non-negative. If your random walk starts at $1$, then your random walk is bounded below by $1$, so that it never hits zero. That is, if $X_n$ is the state of your random walk at time $n$, then $$P(X_n = 0 \text{ for some } n ) = 0$$