Vtyjkyuk

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

It can be shown that for $theta>0$, $mathsfP(S_ngetheta 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 $(mathcalF_n^X)$ backward martingale ($mathsfE[X_1|mathcalF_n^X]=Z_n$). Fix $hat Z_n=Z_N-n$ and $hat mathcalF_n=mathcalF_N-n^X$ ($0le n<N$) so that $hat Z_n$ is a zero-mean martingale. Then

$$mathsfPleft(max_1le nle NZ_ngethetaright)=mathsfPleft(max_0le n< Nhat Z_ngethetaright)le fracmathsfEhat Z_N-1^2mathsfEhat Z_N-1^2+theta^2=fracmathsfEX_1^2mathsfEX_1^2+theta^2=frac11+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 $Nrightarrow infty$.

On the other hand, for $thetale 1$, $mathsfP(S_ngetheta n text for some n>0)gefrac12$. So, for $theta=1$ this probability is exactly $frac12$.