Is this Jensen's Inequality? (Symmetrization Lemma)

Question

This question concerns most proofs I've seen on the so called Symmetrization Lemma.

Let $\mathcal{F}$ be a class of measurable functions and $X_1,\ldots,X_n$ be independent and identically distributed random elements of a measurable space $(\mathcal{X},\mathcal{A})$, distributed according to some distribution $P$ and define $$P_n=\frac{1}{n}\sum_{i=1}^n\delta_{X_i}$$ The proof starts off by introducing a ghost sample $Y_1,\ldots,Y_n$ of $n$ random variables distributed identically to the $X_i$'s and drawn independently and then they write $$\sup_{f\in\mathcal{F}}\left|(P_n-P)f\right|=\sup_{f\in\mathcal{F}}\frac{1}{n}\left|\sum_{i=1}^nf(X_i)-Ef(Y_i)\right|\leq E_Y \sup_{f\in\mathcal{F}}\frac{1}{n}\left|\sum_{i=1}^nf(X_i)-f(Y_i)\right|,$$ with the last inequality being what I do not understand (the $E$ stands for expected value and $E_Y$ the same with respect to $Y$).

How do we justify it? It kinda looks like Jensen's inequality but the dependence of the supremum on the random variables seems way too complicated to write it in that way. I guess I'm missing something obvious here and would be very grateful if anyone could point it out.

It is also Lemma $4$ on these notes (page $196$), where the writers claim that it is Jensen's inequality because "the supremum is a convex function", but I still have a hard time understanding how to even write the supremum as a function on the random variables, let alone a convex one.

Thank you for your time.

Answer 1

There are two steps required to prove your inequality. The first step involves Jensens's inequality, while the second step does not (the way I see it).

First, you show that, for all $f\in \mathcal F$, $$ \frac{1}{n}\left|\sum_{i=1}^nf(X_i)-Ef(Y_i)\right| \le E_Y\, \frac1n \sum_{i=1}^n |f(X_i)-f(Y_i)|\tag1 $$ using Jensen's inequality. Since this holds for all $f\in F$, you conclude $$ \sup_{f\in \mathcal F}\frac{1}{n}\left|\sum_{i=1}^nf(X_i)-Ef(Y_i)\right| \le \sup_{f\in \mathcal F}E_Y\, \frac1n \sum_{i=1}^n |f(X_i)-f(Y_i)|\tag2 $$ Second, for all $f\in \mathcal F$, start with the obvious equality $$ \frac1n \sum_{i=1}^n |f(X_i)-f(Y_i)|\le \sup_{f\in \mathcal F}\, \frac1n \sum_{i=1}^n |f(X_i)-f(Y_i)|\tag3 $$ Applying $E_Y$ to both sides of $(3)$, we get $$\tag4 E_Y\;\frac1n \sum_{i=1}^n |f(X_i)-f(Y_i)| \le E_Y\;\sup_{f\in \mathcal F}\, \frac1n \sum_{i=1}^n |f(X_i)-f(Y_i)| $$ The LHS of $(4)$ depends on $f$, while the RHS does not. Therefore, inequality $(4)$ still holds when you take the $\sup$ over all $f\in \mathcal F$ on the LHS. That is, $$ \sup_{f\in \mathcal F} E_Y\;\frac1n \sum_{i=1}^n |f(X_i)-f(Y_i)| \le E_Y\;\sup_{f\in \mathcal F}\, \frac1n \sum_{i=1}^n |f(X_i)-f(Y_i)|\tag5 $$ Combine $(2)$ and $(5)$ to get what you ultimately want.

There might be a way to express the reasoning in equations $(3)$ through $(5)$ in terms of Jensen's inequality, but I cannot see how.