[proofplan]
We center the bounded observations by writing $Y_i=f(X_i)-Pf$, so that the upper-tail event becomes a deviation event for the sum $\sum_{i=1}^n Y_i$. For a positive exponential parameter $\lambda$, Markov's inequality applied to the nonnegative [random variable](/page/Random%20Variable) $\exp(\lambda\sum_i Y_i)$ converts the tail probability into a [moment generating function](/page/Moment%20Generating%20Function) estimate. Independence factors this moment [generating function](/page/Generating%20Function), and [Hoeffding's lemma](/theorems/1956) bounds each centered bounded factor by a quadratic exponential. Optimizing the resulting bound in $\lambda$ gives the upper-tail estimate; the lower-tail estimate follows by applying the same argument to $-f$.
[/proofplan]
[step:Center the empirical average and record the bounded interval]
For each $1\le i\le n$, define the real-valued random variable
\begin{align*}
Y_i:\Omega\to\mathbb R
\end{align*}
by
\begin{align*}
Y_i(\omega):=f(X_i(\omega))-Pf.
\end{align*}
Since $a\le f\le b$ on $S$, the function $f$ is bounded and hence $P$-integrable. Moreover,
\begin{align*}
a\le Pf\le b,
\end{align*}
because $P$ is a probability measure and
\begin{align*}
a=\int_S a\,dP(x)\le \int_S f(x)\,dP(x)\le \int_S b\,dP(x)=b.
\end{align*}
Thus each $Y_i$ is bounded by
\begin{align*}
a-Pf\le Y_i\le b-Pf.
\end{align*}
The interval length is
\begin{align*}
(b-Pf)-(a-Pf)=b-a.
\end{align*}
Also, since $X_i$ has distribution $P$,
\begin{align*}
\mathbb E[Y_i]=\int_\Omega f(X_i(\omega))\,d\mathbb P(\omega)-Pf=\int_S f(x)\,dP(x)-Pf=0.
\end{align*}
Finally,
\begin{align*}
P_nf-Pf=\frac{1}{n}\sum_{i=1}^{n}Y_i.
\end{align*}
[guided]
The point of this step is to isolate the random fluctuation from its deterministic mean. For each $1\le i\le n$, define
\begin{align*}
Y_i:\Omega\to\mathbb R
\end{align*}
by
\begin{align*}
Y_i(\omega):=f(X_i(\omega))-Pf.
\end{align*}
The function $f$ is bounded because $a\le f(x)\le b$ for every $x\in S$, so the integral defining $Pf$ is finite. Since $P$ is a probability measure, integrating the pointwise inequality $a\le f\le b$ gives
\begin{align*}
a=\int_S a\,dP(x)\le \int_S f(x)\,dP(x)\le \int_S b\,dP(x)=b.
\end{align*}
Therefore
\begin{align*}
a-Pf\le f(X_i)-Pf\le b-Pf,
\end{align*}
so each $Y_i$ is supported in the interval $[a-Pf,b-Pf]$. This interval has length
\begin{align*}
(b-Pf)-(a-Pf)=b-a.
\end{align*}
The variables are centered. Indeed, because $X_i$ has distribution $P$,
\begin{align*}
\mathbb E[Y_i]=\int_\Omega f(X_i(\omega))\,d\mathbb P(\omega)-Pf=\int_S f(x)\,dP(x)-Pf=0.
\end{align*}
The empirical deviation is exactly the average of these centered variables:
\begin{align*}
P_nf-Pf=\frac{1}{n}\sum_{i=1}^{n}Y_i.
\end{align*}
This reformulation puts the problem into the standard bounded-sum form needed for the exponential moment argument.
[/guided]
[/step]
[step:Bound the exponential moment of the centered sum]
We use the following form of Hoeffding's lemma: if $Z:\Omega\to\mathbb R$ is a centered random variable with $\alpha\le Z\le \beta$ almost surely, then for every $\lambda\in\mathbb R$,
\begin{align*}
\mathbb E[\exp(\lambda Z)]\le \exp\left(\frac{\lambda^2(\beta-\alpha)^2}{8}\right).
\end{align*}
This is a standard external ingredient not yet resolved to a wiki theorem: Hoeffding's Lemma.
For each $i$, apply this lemma to $Z=Y_i$, $\alpha=a-Pf$, and $\beta=b-Pf$. Since $\mathbb E[Y_i]=0$ and $\beta-\alpha=b-a$, for every $\lambda>0$,
\begin{align*}
\mathbb E[\exp(\lambda Y_i)]\le \exp\left(\frac{\lambda^2(b-a)^2}{8}\right).
\end{align*}
Because $X_1,\dots,X_n$ are independent and the maps $f:S\to\mathbb R$ are measurable, the random variables $Y_1,\dots,Y_n$ are independent. Hence
\begin{align*}
\mathbb E\left[\exp\left(\lambda\sum_{i=1}^{n}Y_i\right)\right]
=\prod_{i=1}^{n}\mathbb E[\exp(\lambda Y_i)]
\le \exp\left(\frac{n\lambda^2(b-a)^2}{8}\right).
\end{align*}
[/step]
[step:Apply exponential Markov inequality and optimize the parameter]
Fix $t>0$ and $\lambda>0$. The event $\{P_nf-Pf\ge t\}$ is the same as
\begin{align*}
\left\{\sum_{i=1}^{n}Y_i\ge nt\right\}.
\end{align*}
Since the exponential map is increasing,
\begin{align*}
\left\{\sum_{i=1}^{n}Y_i\ge nt\right\}
=
\left\{\exp\left(\lambda\sum_{i=1}^{n}Y_i\right)\ge \exp(\lambda nt)\right\}.
\end{align*}
Applying Markov's inequality to the nonnegative random variable
\begin{align*}
\omega\mapsto \exp\left(\lambda\sum_{i=1}^{n}Y_i(\omega)\right)
\end{align*}
gives
\begin{align*}
\mathbb P(P_nf-Pf\ge t)
\le \exp(-\lambda nt)\mathbb E\left[\exp\left(\lambda\sum_{i=1}^{n}Y_i\right)\right].
\end{align*}
Using the exponential moment bound from the previous step,
\begin{align*}
\mathbb P(P_nf-Pf\ge t)
\le \exp\left(-\lambda nt+\frac{n\lambda^2(b-a)^2}{8}\right).
\end{align*}
Choose
\begin{align*}
\lambda_*:=\frac{4t}{(b-a)^2}.
\end{align*}
Then $\lambda_*>0$, and substituting $\lambda=\lambda_*$ yields
\begin{align*}
-\lambda_*nt+\frac{n\lambda_*^2(b-a)^2}{8}
=
-\frac{4nt^2}{(b-a)^2}+\frac{2nt^2}{(b-a)^2}
=
-\frac{2nt^2}{(b-a)^2}.
\end{align*}
Therefore
\begin{align*}
\mathbb P(P_nf-Pf\ge t)\le \exp\left(-\frac{2nt^2}{(b-a)^2}\right).
\end{align*}
[/step]
[step:Apply the upper-tail result to $-f$ for the lower tail]
Define the [measurable function](/page/Measurable%20Function)
\begin{align*}
g:S\to\mathbb R
\end{align*}
by
\begin{align*}
g(x):=-f(x).
\end{align*}
Since $a\le f(x)\le b$ for every $x\in S$, we have
\begin{align*}
-b\le g(x)\le -a
\end{align*}
for every $x\in S$, and the interval length is
\begin{align*}
(-a)-(-b)=b-a.
\end{align*}
Also
\begin{align*}
P_ng=-P_nf
\end{align*}
and
\begin{align*}
Pg=-Pf.
\end{align*}
Applying the upper-tail estimate already proved to $g$ gives, for every $t>0$,
\begin{align*}
\mathbb P(P_ng-Pg\ge t)\le \exp\left(-\frac{2nt^2}{(b-a)^2}\right).
\end{align*}
But
\begin{align*}
P_ng-Pg=(-P_nf)-(-Pf)=Pf-P_nf.
\end{align*}
Hence
\begin{align*}
\mathbb P(Pf-P_nf\ge t)\le \exp\left(-\frac{2nt^2}{(b-a)^2}\right).
\end{align*}
Together with the upper-tail estimate, this proves both claimed inequalities.
[/step]
