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 1


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

  • $\begingroup$ 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}$? $\endgroup$
    – Hans
    Commented Jul 15, 2018 at 20:11
  • $\begingroup$ @Hans It was long time ago... However, I'm sure that this follows from a version of the Kolmogorov maximal inequality adapted to martingales. $\endgroup$
    – user140541
    Commented Jul 15, 2018 at 21:39
  • $\begingroup$ 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? $\endgroup$
    – Hans
    Commented Jul 15, 2018 at 23:29
  • $\begingroup$ @Hans Look at this question or its older version. $\endgroup$
    – user140541
    Commented Jul 16, 2018 at 1:39
  • 1
    $\begingroup$ 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. $\endgroup$
    – Hans
    Commented Jul 16, 2018 at 5:44

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .