[proofplan]
Center the [random variable](/page/Random%20Variable) and apply Markov's inequality to its exponential transform. The assumed [Laplace transform](/page/Laplace%20Transform) bound converts this into a one-parameter family of exponential tail estimates. Optimizing the resulting quadratic in the parameter gives the upper-tail bound. If the Laplace bound is available for negative parameters as well, the same argument applies to the lower tail, and the two-sided estimate follows from finite subadditivity of probability.
[/proofplan]
[step:Apply Markov's inequality to the exponential transform]
Define the centered random variable $X:\Omega\to\mathbb R$ by
\begin{align*}
X(\omega)=F(\omega)-\mathbb E[F].
\end{align*}
Fix $t\geq 0$ and $\beta>0$. Define the non-negative random variable $Y_\beta:\Omega\to[0,\infty)$ by
\begin{align*}
Y_\beta(\omega)=e^{\beta X(\omega)}.
\end{align*}
Since the assumed Laplace bound implies $\mathbb E[Y_\beta]<\infty$, Markov's inequality applies to $Y_\beta$ at the level $e^{\beta t}>0$. Because
\begin{align*}
\{X\geq t\}=\{e^{\beta X}\geq e^{\beta t}\},
\end{align*}
we obtain
\begin{align*}
\mathbb P(X\geq t)\leq e^{-\beta t}\mathbb E[e^{\beta X}].
\end{align*}
Using the Laplace transform hypothesis gives
\begin{align*}
\mathbb E[e^{\beta X}]\leq \exp\left(\frac{\sigma^2\beta^2}{2}\right).
\end{align*}
Therefore, for every $\beta>0$,
\begin{align*}
\mathbb P(X\geq t)\leq \exp\left(-\beta t+\frac{\sigma^2\beta^2}{2}\right).
\end{align*}
[guided]
We want to estimate the probability of the event $\{X\geq t\}$, where $X:\Omega\to\mathbb R$ is the centered random variable defined by
\begin{align*}
X(\omega)=F(\omega)-\mathbb E[F].
\end{align*}
The hypothesis controls exponential moments of $X$, so we convert the event $\{X\geq t\}$ into an event involving an exponential. Fix $\beta>0$. Define $Y_\beta:\Omega\to[0,\infty)$ by
\begin{align*}
Y_\beta(\omega)=e^{\beta X(\omega)}.
\end{align*}
The map $s\mapsto e^{\beta s}$ is increasing on $\mathbb R$, so
\begin{align*}
\{X\geq t\}=\{e^{\beta X}\geq e^{\beta t}\}.
\end{align*}
The random variable $Y_\beta$ is non-negative, and the Laplace hypothesis gives
\begin{align*}
\mathbb E[Y_\beta]=\mathbb E[e^{\beta X}]\leq \exp\left(\frac{\sigma^2\beta^2}{2}\right)<\infty.
\end{align*}
Thus Markov's inequality applies to $Y_\beta$ at the positive threshold $e^{\beta t}$ and gives
\begin{align*}
\mathbb P(X\geq t)=\mathbb P(Y_\beta\geq e^{\beta t})\leq e^{-\beta t}\mathbb E[Y_\beta].
\end{align*}
Substituting the Laplace transform estimate yields
\begin{align*}
\mathbb P(X\geq t)\leq \exp\left(-\beta t+\frac{\sigma^2\beta^2}{2}\right).
\end{align*}
This is the Chernoff estimate before optimization: every positive choice of $\beta$ gives a valid upper bound, and the next step chooses the best one.
[/guided]
[/step]
[step:Optimize the Chernoff parameter to obtain the upper tail]
For fixed $t\geq 0$, define the quadratic function $q_t:[0,\infty)\to\mathbb R$ by
\begin{align*}
q_t(\beta)=-\beta t+\frac{\sigma^2\beta^2}{2}.
\end{align*}
If $t=0$, then $\mathbb P(X\geq 0)\leq 1=\exp(0)$, which is the desired estimate. Suppose now that $t>0$. The derivative of $q_t$ is
\begin{align*}
q_t'(\beta)=-t+\sigma^2\beta.
\end{align*}
Thus $q_t$ is minimized over $[0,\infty)$ at
\begin{align*}
\beta_t=\frac{t}{\sigma^2}.
\end{align*}
Substituting this value into the preceding bound gives
\begin{align*}
\mathbb P(X\geq t)\leq \exp\left(-\frac{t^2}{\sigma^2}+\frac{t^2}{2\sigma^2}\right).
\end{align*}
Hence
\begin{align*}
\mathbb P(X\geq t)\leq \exp\left(-\frac{t^2}{2\sigma^2}\right).
\end{align*}
Since $X=F-\mathbb E[F]$, this proves the asserted upper-tail estimate.
[/step]
[step:Apply the upper-tail estimate to the negative centered variable]
Assume now that the Laplace transform bound holds for every $\beta\in\mathbb R$. Define $Z:\Omega\to\mathbb R$ by
\begin{align*}
Z(\omega)=-X(\omega)=\mathbb E[F]-F(\omega).
\end{align*}
For every $\gamma\geq 0$, using the hypothesis with $\beta=-\gamma$ gives
\begin{align*}
\log\mathbb E[e^{\gamma Z}]=\log\mathbb E[e^{-\gamma X}]\leq \frac{\sigma^2\gamma^2}{2}.
\end{align*}
Also $\mathbb E[Z]=-\mathbb E[X]=0$, because $X=F-\mathbb E[F]$ and hence $\mathbb E[X]=0$. Therefore $Z$ satisfies the same one-sided Laplace transform hypothesis as a centered random variable. Applying the already proved upper-tail estimate to $Z$ gives, for every $t\geq 0$,
\begin{align*}
\mathbb P(Z\geq t)\leq \exp\left(-\frac{t^2}{2\sigma^2}\right).
\end{align*}
Equivalently,
\begin{align*}
\mathbb P(X\leq -t)\leq \exp\left(-\frac{t^2}{2\sigma^2}\right).
\end{align*}
[/step]
[step:Combine the two one-sided estimates by finite subadditivity]
For every $t\geq 0$, the event $\{|X|\geq t\}$ is contained in the union of the upper-tail and lower-tail events:
\begin{align*}
\{|X|\geq t\}\subset \{X\geq t\}\cup\{X\leq -t\}.
\end{align*}
By finite subadditivity of the probability measure $\mathbb P$,
\begin{align*}
\mathbb P(|X|\geq t)\leq \mathbb P(X\geq t)+\mathbb P(X\leq -t).
\end{align*}
Using the two one-sided bounds gives
\begin{align*}
\mathbb P(|X|\geq t)\leq 2\exp\left(-\frac{t^2}{2\sigma^2}\right).
\end{align*}
Since $X=F-\mathbb E[F]$, this is exactly
\begin{align*}
\mathbb P(|F-\mathbb E[F]|\geq t)\leq 2\exp\left(-\frac{t^2}{2\sigma^2}\right).
\end{align*}
This completes the proof.
[/step]
