# Random walk with positive drift

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?

• The random walk starts at 1 as stated. Am I missing something obvious here? Commented May 10, 2022 at 18:19

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.

• Where did you use the support set of $S$? From the question I assume that $S$ changes at every step with some unknown probability distribution over the given support set. Commented May 12, 2022 at 21:26
• @C.Koca I proved the case of Bernoulli distributed $S$, i.e., the support set of $S$ is $\{-1,1\}$, as I mentioned in the beginning of my post. Commented May 12, 2022 at 21:31
• One can trivially generalize this to distributions S where $P(S_i=-1) =p < 1/2$ and I suspect that a little more cleverness should give the general case OP is looking for but I don't see how to do it. Commented May 13, 2022 at 15:39

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 such that $$$$\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.$$$$

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.

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

• Many apologies on my end---$S$ is distributed over the nonnegative integers as well as -1. I made a mistake when typing up my question, please see my edit. Thank you. Commented May 10, 2022 at 22:11
• Seems to me that there is zero chance of $S= -1 \$ Commented May 12, 2022 at 18:05
• @Daniel we don't know the distribution, just that expectation is positive. Commented May 12, 2022 at 18:07