[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*}[/step]

[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: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]