Let $X_n$ be a sequence of iid random variables with $\mathbb{E}[X_1] = 0$ and
$$\mathbb{E}[e^{\alpha X_1}] < \infty \quad \text{ for each $\alpha \in [0, 1/2]$}.$$
Let $S_k = X_1 + \dots + X_k$.
What would be a minimum set of assumptions on $X$ to obtain a bound of the form
$$\mathbb{P}\left(\max_{1\leq k \leq n} S_k \geq t\sqrt{n}\right) \leq e^{-ct^{0.001}}$$
where I do not care about the power on $t$.
One way to do this is to assume that $X_1$ is sub-exponential. By Doob's maximal inequality, we have
\begin{align*}
\mathbb{P}\left(\max_{1\leq k \leq n} S_k \geq t\sqrt{n}\right)
&= \mathbb{P}\left(e^{\lambda \max_{1\leq k \leq n} S_k} \geq e^{\lambda t\sqrt{n}}\right)\\
&\leq \frac{\left(\mathbb{E}[e^{\lambda X_1}]\right)^n}{e^{{\lambda t\sqrt n}}}.
\end{align*}
Now we see that if $X_1$ is sub-exponential, i.e. $\log(\mathbb{E}[e^{\lambda X_1}]) \leq C_0\lambda^2$ for some fixed $C_0$ and $\lambda$ in a small fixed interval $[0, \lambda_0]$. Then, we get
$$\log\left(\frac{\left(\mathbb{E}[e^{\lambda X_1}]\right)^n}{e^{{\lambda t\sqrt n}}} \right) \leq nC_0\lambda^2 – \lambda t \sqrt n.$$
We see that $\lambda = \frac{t}{C_0 \sqrt n}$ would be a minimizer for $nC_0\lambda^2 – \lambda t \sqrt n$. Thus if $ \frac{t}{C_0\sqrt n} \leq \lambda_0$, then we have the maximal probability $$\mathbb{P}\left(\max_{1\leq k \leq n} S_k \geq t\sqrt{n}\right) \leq e^{-ct^2}.$$
Otherwise, this estimate becomes a large deviation, but with a maximum in front of the random walk. I expect it would decay like $e^{-ct}$ instead of $e^{-ct^2}$, and I would appreciate it if someone could find a reference for this as well.
Best Answer
The minimizer in $[0,\lambda_0]$ of the parabola $f(\lambda)=nC_0\lambda^2 - \lambda t \sqrt n$ is actually $$\lambda(t)=\min\Bigl\{\lambda_0,\frac{t}{2C_0 \sqrt n}\Bigr\}\,.$$ Since $f(\lambda(t))=-t^2/(4C_0)$ for $t \le 2C_0 \lambda_0 \sqrt{n}$ and $f(\lambda(t))=nC_0\lambda_0^2 - \lambda_0 t \sqrt n$ for for $t \ge 2C_0 \lambda_0 \sqrt{n}$. Thus, as expected, for large $t$ we get exponential decay.