Probability that a random walker crosses a moving point A random walker starts at $x_0=0$ and walks left or right with probability 1/2; let $x_n$ be the walker's position at time $n$.
Meanwhile, a point starts at $y_0=0$ and moves constantly to the right, such that $y_n=\sqrt{2 n\ln n}$.
What is the probability that there exists some $n\geq 100$ for which the walker is to the right of the point ($x_n>y_n$)?
Here is what I know:


*

*For any specific $n\geq 100$, the probability that $x_n>y_n$ is at most $1/n \leq 1/100$; this is an outcome of Azuma's inequality. However, the probability that there exists some $n$ for which $x_n>y_n$ is probably larger than 1/100.

*By the union bound, the probability is at most $\sum_{i=100}^N (1/i) \approx \ln(N)-\ln(100)$. But, since $\ln(N)>1$, this bound is useless.
Is there a better upper bound on the probability that $\exists n\geq 100: x_n>y_n$?

Approximate $x_t$ with Brownian motion $W_t$ and consider continuous time instead. The result D30 on page 99 in Probability Approximations via the Poisson Clumping Heuristic by Aldous states that if $P(W_t>y_t)$ is small for $t>t_0$ (usually taken as at least 3 standard deviations from the mean) and $y(s)$ grows roughly as $s^{\frac 1 2}$, then for $$\lambda(s)=s^{-3/2}(y(s)-sy'(s))\phi(s^{-{\frac 1 2}}y(s))\tag 1$$
$$P(W_t\le y_t: t\ge t_0)\approx \exp(-\int_{t_0}^\infty\lambda(s)\,ds)$$
where $\phi$ is density of standard normal. Plugging in $y(s)$, for $t_0\ge 90$ we get:
$$P(\exists t\ge t_0: W_t>y_t)\approx 1-\exp(-\frac {\sqrt{\log t_0}} {2\sqrt \pi t_0}(1-\frac 1{\log t_0}))\approx \frac {\sqrt{\log t_0}} {\sqrt 2\sqrt {2\pi} t_0}(1-\frac 1{\log t_0})\approx 0.005$$
for $t_0=100$. Compare this with $P(W_{t_0}>y_{t_0})\sim \frac {\phi(\sqrt{2\log t_0})}{\sqrt{2\log t_0}}=\frac 1{\sqrt{2\pi}}\frac 1{t_0\sqrt{2\log t_0}}$ which is a factor of $\log t_0$ less.
