# Probability a random walk eventually crosses a square root boundary

Let $\lbrace X_n, n \geq 1 \rbrace$ be i.i.d random variables taking values in $\lbrace -1, 1 \rbrace$, and \begin{align*} S_n = \sum_{i = 1}^{n} X_i \end{align*} be a random walk. Let $f$ be a function $\mathbb{N} \to \mathbb{R}^+$. Define a stopping time $J$ as \begin{align*} J=\inf\{n \geq 0\mid S_n \geq f(n) \} \end{align*} Do there exist $a, b$ so that when $f(n) = a\sqrt{n} + b$, we have \begin{align*} \lim_{n \to \infty} Pr[J \leq n] < 1\ ?\end{align*}

This can be proved if $f(n) = 2\sqrt{n\log{n} + b}$, a sketch is as follows

Let $C_i$s be some unimportant constants. We can bound by Hoeffding/Chernoff that $Pr[S_n \geq f(n)] \leq C_1n^{-2}e^{-C_2b}$. Then by union bound it can be shown that $Pr[\lbrace \exists n, S_n \geq f(n) \rbrace] \leq C_3e^{-C_4b}$, then we just need to choose a sufficiently large value for b

This proof do not generalize to the tighter case where $f(n) = O(\sqrt{n})$ though

• Wht are your thoughts on this?
– Did
Commented Jan 9, 2016 at 8:08
• I think I can prove this if $f(n) = a\sqrt{n}\log{n} + b$. But to tighten it to $\sqrt{n}$ seems quite hard Commented Jan 9, 2016 at 8:14
• OK. Then show what you can do.
– Did
Commented Jan 9, 2016 at 8:15
• Added a proof of the simpler case Commented Jan 9, 2016 at 8:24

No, there do not exist such $a,b$.
The law of the iterated logarithm for simple random walk states that, almost surely, $$\limsup_{n \to \infty} \frac{S_n}{\sqrt{2 n \log \log n}} = 1.$$ In particular, almost surely, there exist infinitely many $n$ such that $S_n \ge \sqrt{n \log \log n} \ge a\sqrt{n}+b$, since the second inequality holds for all sufficiently large $n$.