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

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