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