I encounter this when proving bounds for a randomized algorithm, which is mathematically formulated below. Many thanks for any thoughts or discussions given.
Consider simple random walk $S_n = X_1 + \cdots + X_n$, where each iid $X_i = \pm 1$ w.p. 1/2 each.
The goal is to find the smallest possible function $f(n)$: For every positive $n$, w.p. $1-\frac 1 n$ that $\forall i = 1, \cdots, n$ we have $|S_i| = O(f(n))$
With @stochasticboy321 suggestion, I apply Hoeffding inequality and find $O(\sqrt{n\log n})$ would make an upper bound with probability at least $1 - 1/n$. I wonder if this is the smallest possible function.