# Random Walk Threshold Problem with a Time-Dependent Threshold

For any constant threshold in a random walk, the probability we cross the threshold at some time goes to 1 as time goes to infinity. But how can we approach the problem if the threshold is time dependent, say as a linear function? To formalize:

Let $S_t = X_1 + X_2 ... + X_t$ represent a random walk, with each iid $X_i$ being either -1 or 1 with equal probability. Let $0 \le \theta \le 1$. What's the probability that at some time $t > 0$ during the random walk, $S_t \ge \theta t$?

## 1 Answer

It can be shown that for $$\theta>0$$, $$\mathsf{P}(S_n\ge\theta n \text{ for some } n>0)<1$$.

Let $$Z_n=S_n/n$$ where $$S_n$$ is a simple symmetric random walk. $$Z_n$$ is an $$(\mathcal{F}_n^X)$$ backward martingale ($$\mathsf{E}[X_1|\mathcal{F}_n^X]=Z_n$$). Fix $$\hat Z_n=Z_{N-n}$$ and $$\hat {\mathcal{F}}_n=\mathcal{F}_{N-n}^X$$ ($$0\le n) so that $$\hat Z_n$$ is a zero-mean martingale. Then

$$\mathsf{P}\!\left(\max_{1\le n\le N}Z_n\ge\theta\right)=\mathsf{P}\!\left(\max_{0\le n< N}\hat Z_n\ge\theta\right)\le \frac{\mathsf{E}\hat Z_{N-1}^2}{\mathsf{E}\hat Z_{N-1}^2+\theta^2}=\frac{\mathsf{E}X_1^2}{\mathsf{E}X_1^2+\theta^2}=\frac{1}{1+\theta^2}<1$$ where the first inequality is of the Cantelli type or from more directly this and this propositions proved with Cantelli's method in combination with Doob's martingale inequality . We then let $$N\rightarrow \infty$$.

On the other hand, for $$\theta\le 1$$, $$\mathsf{P}(S_n\ge\theta n \text{ for some } n>0)\ge\frac{1}{2}$$. So, for $$\theta=1$$ this probability is exactly $$\frac{1}{2}$$.

• How did you get $P\{\max_{0\le n< N}\hat Z_n\ge\theta \}\le \frac{\mathbb{E}\hat Z_{N-1}^2}{\mathbb{E}\hat Z_{N-1}^2+\theta^2}$?
– Hans
Commented Jul 15, 2018 at 20:11
• @Hans It was long time ago... However, I'm sure that this follows from a version of the Kolmogorov maximal inequality adapted to martingales.
– user140541
Commented Jul 15, 2018 at 21:39
• Kolmogorov maximal inequality is of the Chebyshev type, which will readily give you $\theta^2$ on the denominator. My concern is with that extra $\mathsf{E}\hat Z_{N-1}^2$ on the denominator. Where does it come from?
– Hans
Commented Jul 15, 2018 at 23:29
• @Hans Look at this question or its older version.
– user140541
Commented Jul 16, 2018 at 1:39
• Yes. I was about to write about Cantelli's inequality en.wikipedia.org/wiki/Cantelli%27s_inequality which is what your links are about. Thank you.
– Hans
Commented Jul 16, 2018 at 5:44