## Formalized Name Hoeffding's Lemma ## Proof We prove the bound with parameter $\sigma = b - a$. Let $W'$ be an independent copy of $W$ (same distribution, independent of $W$). Since $\mathbb{E}[W'] = \mathbb{E}[W]$, we can write: \begin{align*} \mathbb{E}[e^{\alpha(W - \mathbb{E}[W])}] = \mathbb{E}[e^{\alpha(W - \mathbb{E}[W'])}] = \mathbb{E}[e^{\mathbb{E}[\alpha(W - W') \mid W]}]. \end{align*} The last equality uses $\mathbb{E}[W' \mid W] = \mathbb{E}[W']$ (by independence) and the fact that $W$ is known given $W$. Applying Jensen's inequality to the convex function $x \mapsto e^x$ conditionally on $W$ (and then the tower property): \begin{align*} \mathbb{E}[e^{\alpha(W - \mathbb{E}[W])}] \leq \mathbb{E}[e^{\alpha(W - W')}]. \end{align*} Now introduce a Rademacher random variable $\varepsilon$ independent of $(W, W')$. The key observation is that $W - W' \stackrel{d}{=} \varepsilon(W - W')$: the signed difference $W - W'$ is symmetric around zero (since $W$ and $W'$ have the same distribution), so multiplying by an independent $\pm 1$ does not change its distribution. Therefore: \begin{align*} \mathbb{E}[e^{\alpha(W - \mathbb{E}[W])}] \leq \mathbb{E}[e^{\alpha \varepsilon(W - W')}] = \mathbb{E}\bigl[\mathbb{E}[e^{\alpha \varepsilon(W - W')} \mid W, W']\bigr]. \end{align*} Conditioning on $(W, W')$, the quantity $\alpha(W - W')$ is a fixed constant $c$, and $\varepsilon$ is Rademacher. By the Rademacher example above, $\mathbb{E}[e^{c\varepsilon}] \leq e^{c^2/2}$. Applying this conditionally: \begin{align*} \mathbb{E}[e^{\alpha(W - \mathbb{E}[W])}] \leq \mathbb{E}[e^{\alpha^2(W - W')^2/2}]. \end{align*} Since $W \in [a, b]$ and $W' \in [a, b]$ almost surely, we have $|W - W'| \leq b - a$, so $(W - W')^2 \leq (b-a)^2$. Therefore: \begin{align*} \mathbb{E}[e^{\alpha(W - \mathbb{E}[W])}] \leq e^{\alpha^2(b-a)^2/2}. \end{align*} This is the sub-Gaussian condition with parameter $\sigma = b - a$.