2022-Q1 – Exponential Markov Bounds, MGFs, and Rademacher Tails
2022 Probability Prelim Exam (PDF)
Problem 1
Let $S$ be a real-valued random variable and let $x>0$.
(a)(i)
Show that for every $t>0$, \(P(S>x)\le e^{-tx}\,\mathbb{E}[e^{tS}].\)
(a)(ii)
Show that \(P(S>x)\le \inf_{t>0}\, e^{-tx}\,\mathbb{E}[e^{tS}].\)
Now let $\varepsilon_1,\varepsilon_2,\ldots,\varepsilon_n$ be i.i.d. Rademacher random variables,
i.e. $P(\varepsilon_i = 1)=P(\varepsilon_i=-1)=\tfrac12$.
Let \(S_n = \sum_{k=1}^n \varepsilon_k.\)(b)(i)
Show that \(\mathbb{E}[e^{t S_n}] = \left(\frac{e^{t} + e^{-t}}{2}\right)^n.\)
(b)(ii)
Show that for all $t>0$, \(P(S_n > x) \le \exp\!\left( -tx + \frac{n t^2}{2}\right).\)
(c)
Deduce that for all $x>0$, \(P\!\left(\frac{S_n}{\sqrt{n}} > x\right) \le e^{-x^2/2}.\)
Solution
(a)(i) Exponential Markov Bound
Claim.
For every $t>0$, \(P(S>x) \le e^{-tx}\,\mathbb{E}[e^{tS}].\)
Proof.
Since $e^{t\cdot}$ is strictly increasing, \(\{S>x\} = \{e^{tS} > e^{tx}\}.\) Because $e^{tS} \ge 0$, Markov’s inequality applies: \(P(S>x) = P(e^{tS} > e^{tx}) \le \frac{\mathbb{E}[e^{tS}]}{e^{tx}} = e^{-tx}\,\mathbb{E}[e^{tS}].\) ∎
Conclusion.
We have derived the standard exponential Markov bound.
(a)(ii) Taking the Infimum in $t$
Claim.
\(P(S>x)\le \inf_{t>0}\, e^{-tx}\,\mathbb{E}[e^{tS}].\)
Proof.
Part (a)(i) shows that for every $t>0$, \(P(S>x)\le e^{-tx}\,\mathbb{E}[e^{tS}].\) Since the inequality holds for all $t>0$, it must also hold for the greatest lower bound of the right-hand side. Therefore, \(P(S>x)\le \inf_{t>0}\, e^{-tx}\,\mathbb{E}[e^{tS}].\) ∎
Conclusion.
No optimization is performed here; this step simply tightens the bound by taking the infimum over all $t>0$.
(b)(i) MGF of a Rademacher Sum
Claim.
\(\mathbb{E}[e^{t S_n}] = \left(\frac{e^{t}+e^{-t}}{2}\right)^n.\)
Proof.
Independence gives \(\mathbb{E}[e^{tS_n}] = \mathbb{E}\!\left[e^{t(\varepsilon_1+\cdots+\varepsilon_n)}\right] = \prod_{k=1}^n \mathbb{E}[e^{t\varepsilon_k}].\)
Now compute the one-variable MGF: \(\mathbb{E}[e^{t\varepsilon}] = e^t P(\varepsilon=1) + e^{-t} P(\varepsilon=-1) = \frac{e^{t} + e^{-t}}{2}.\)
Substitute back: \(\mathbb{E}[e^{tS_n}] = \left(\frac{e^{t}+e^{-t}}{2}\right)^n.\) ∎
Conclusion.
The Rademacher MGF is the hyperbolic cosine: $\cosh(t)$. The sum’s MGF is its nth power.
(b)(ii) Chernoff-Type Bound for $S_n$
Claim.
\(P(S_n > x) \le \exp\!\left(-tx + \frac{n t^2}{2}\right).\)
Proof.
Start with part (a)(i): \(P(S_n>x) \le e^{-tx}\,\mathbb{E}[e^{tS_n}].\) Insert the result from (b)(i): \(= e^{-tx}\left(\frac{e^{t}+e^{-t}}{2}\right)^n.\) Use the inequality \(\frac{e^t + e^{-t}}{2} \le e^{t^2/2},\) which follows from $ \cosh(t) \le e^{t^2/2} $. Thus \(P(S_n>x) \le e^{-tx}\,(e^{t^2/2})^n = e^{-tx + n t^2/2}.\) ∎
Conclusion.
This is a standard Chernoff–Hoeffding upper bound for Rademacher sums.
(c) Sub-Gaussian Tail for the Normalized Sum
Claim.
\(P\!\left(\frac{S_n}{\sqrt{n}} > x\right) \le e^{-x^2/2}.\)
Proof.
Rewrite the event: \(P\!\left(\frac{S_n}{\sqrt{n}}>x\right) = P(S_n > x\sqrt{n}).\)
Apply (b)(ii): \(P(S_n > x\sqrt{n}) \le \exp\!\left[-t x\sqrt{n} + \frac{n t^2}{2}\right].\)
Now minimize the exponent. Let \(\phi(t) = -t x\sqrt{n} + \frac{n t^2}{2}.\) Complete the square: \(\phi(t) = \frac{n}{2}\left(t - \frac{x}{\sqrt{n}}\right)^2 - \frac{x^2}{2}.\) The minimum occurs at $t^* = x/\sqrt{n}$, yielding \(\phi(t^*) = -\frac{x^2}{2}.\)
Hence: \(P\!\left(\frac{S_n}{\sqrt{n}}>x\right) \le e^{-x^2/2}.\) ∎
Conclusion.
The normalized Rademacher sum has Gaussian-type upper tails, confirming that Rademacher variables are sub-Gaussian with variance proxy $1$.
Key Ideas
-
Exponential Markov inequality:
Converts tail bounds into exponential–moment bounds via $P(X>a)\le E[e^{tX}]e^{-ta}$. -
Infimum trick:
If a bound holds for all $t>0$, it holds for the infimum—no optimization required unless the MGF is known. -
MGF of a Rademacher:
$\mathbb{E}[e^{t\varepsilon}] = \cosh(t)$. -
Hyperbolic cosine bound:
$\cosh(t)\le e^{t^2/2}$. -
Quadratic minimization / completing the square:
Essential in Chernoff bounds to extract Gaussian tails. -
Sub-Gaussian behavior:
Rademacher sums behave like Gaussian random variables in their tail decay.
Comments