# Symmetrization and Contraction Principle of Random Variables

I was reading a paper and came across the terms symmetrization and contraction principle of random variables. I tried to extract the statements as follows:

Symmetrization: Let $$X_1,\dots,X_n$$ be independent zero-mean random variables and $$p\geq 2$$, then $$\left\|\sum_{i=1}^n a_i X_i\right\|_p \leq 2 \left\|\sum_{i=1}^n a_i \varepsilon_i X_i\right\|_p$$ where $$a_i$$ are real numbers and $$\varepsilon_i$$ denote a sequence of symmetric independent Rademacher random variables (also independent of the $$X_i$$'s).

Contraction Principle: Let $$X_1,\dots,X_n$$ be independent non-negative random variables and $$p\geq 2$$. Further, suppose for each $$i$$, we have $$\mathbb{P}(Y_i\geq t)\geq \mathbb{P}(X_i\geq t)$$ for all $$t>0$$, where $$Y_1,\dots, Y_n$$ are also non-negative random variables. Then we have $$\left\|\sum_{i=1}^n a_i \varepsilon_i X_i\right\|_p \leq \left\|\sum_{i=1}^n a_i \varepsilon_i Y_i\right\|_p$$ where $$a_i$$ are real numbers and $$\varepsilon_i$$ denote a sequence of Rademacher random variables.

There might be more general statements of these results that exist but the paper does not really cite them, and I am having trouble finding references to exact statements and proofs. If anybody can provide a reference (preferably a textbook) or a hint, that would be greatly appreciated!

For reference, the paper and argument cited is here, on page 12.

Edit: I am looking for a reference to read, not a direct solution or anything like that.

• Both statements are false. Perhaps you want some independence assumptions somewhere. Commented Apr 4, 2021 at 1:46
• @Michael thanks for your comment, I edited to add in independence. Can you point me to a reference? Not looking for a solution, just a reference to read. Commented Apr 4, 2021 at 1:49
• You also likely want $\epsilon_i$ to be independent of $X_i$, else you can have a counter-example $X_i = (-1)^i \epsilon_i$ for $i \in \{1, ..., n\}$ where $\{\epsilon_i\}$ are i.i.d. Rademacher, so that $\{X_i\}$ are also i.i.d. Rademacher. Commented Apr 4, 2021 at 1:59
• @Michael thanks, I edited that too Commented Apr 4, 2021 at 2:00
• Kind of weird that you have a reference already and yet you are looking for a reference to read and not a solution. Anyway I came up with a cool proof of the first property that uses symmetry, the idea is that if the distribution of $V_i$ and $-V_i$ are the same and the independence assumptions hold then $\sum_i a_i V_i$ has the same distribution as $\sum_i a_i\epsilon_i V_i$. It also uses iterated expectations $E[X]=E[E[X|Y]]$. You seem not to want a proof, though. Commented Apr 4, 2021 at 4:22

The symmetrization is called Khintchine's inequality, see here: https://en.wikipedia.org/wiki/Khintchine_inequality

For the contraction principle, I don't know any reference, but I can prove it. First note that if $$Z\geq 0$$ and $$p > 0$$, then \begin{align} \mathbb{E}[Z^p] = \mathbb{E}\Big[\int_0^{Z} p t^{p-1} dt\Big] = \mathbb{E}\Big[\int_0^{\infty} p t^{p-1} \mathrm{1}_{\{Z\geq t\}} dt\Big] \stackrel{\text{Fubini}}{=} \int_0^{\infty} p t^{p-1} \mathbb{P}(Z\geq t) dt. \end{align} Therefore, if $$X,Y\geq 0$$ and $$\mathbb{P}(X\geq t) \leq \mathbb{P}(Y \geq t)$$ for all $$t > 0$$, then \begin{align*} \mathbb{E}[X^p] = \int_0^{\infty} p t^{p-1} \mathbb{P}(X\geq t) dt \leq \int_0^{\infty} p t^{p-1} \mathbb{P}(Y\geq t) dt = \mathbb{E}[Y^p]. \end{align*} We conclude $$(\mathbb{E}[X^p])^{1/p} \leq (\mathbb{E}[Y^p])^{1/p}$$ for all $$p > 0$$.

Thus, with $$X = \big|\sum_{i=1}^n a_i \varepsilon_i X_i\big|$$ and $$Y = \big|\sum_{i=1}^n a_i \varepsilon_i Y_i\big|$$, we get the claim.

EDIT: We get the claim assuming $$\mathbb{P}(\big|\sum_{i=1}^n a_i \varepsilon_i X_i\big| > t) \leq \mathbb{P}(\big|\sum_{i=1}^n a_i \varepsilon_i Y_i\big| > t)$$, which doesn't follow from $$\mathbb{P}(X_i > t) \leq \mathbb{P}(Y_i > t), ~1 \leq i \leq n$$. Humm, so it's not clear that the third line of the middle equation on page 12 of your reference is actually correct, maybe it was forgotten that the $$\varepsilon_i$$'s can be negative ? Maybe there is another argument at play, I'm not sure.

• There is a reference that I had : I found section 4.2 in Ledoux and Talagrand's book : "Probability in Banach spaces", a generalization of what you write. Needless to say, the proof is simple as you seem to illustrate. +1. I'd found the first one too, but you wrote it before me, so well done! Commented Apr 4, 2021 at 19:08
• How do you get the very last line? And where are you using independence? Commented Apr 4, 2021 at 19:43
• See the edit above. Commented Apr 4, 2021 at 20:55

I may as well write the proof I alluded to last night in the above comments.

Let $$X_1, …, X_n, \epsilon_1, …, \epsilon_n$$ be mutually independent random variables. Suppose that $$E[X_i]=0$$ and $$P[\epsilon_i=-1]=P[\epsilon_i=1] = 1/2$$ for all $$i \in \{1, …, n\}$$. Fix $$p\geq 1$$. For a random variable $$Y$$ define $$\|Y\|_p = E[|Y|^p]^{1/p}$$

Claim: For any real numbers $$a_1, ..., a_n$$ we have $$\left\|\sum_{i=1}^n a_iX_i \right\|_p \leq 2 \left\|\sum_{i=1}^n a_i\epsilon_i X_i\right\|_p$$

Proof: Without loss of generality we can assume $$a_i=1$$ for all $$i$$ (else, just define $$Y_i=a_iX_i$$).

Let $$Z=(Z_1, ..., Z_n)$$ be a vector that is independent of $$(X_1, ..., X_n, \epsilon_1, ..., \epsilon_n)$$ but has the same distribution as $$X=(X_1, ..., X_n)$$. Then $$X_i-Z_i$$ has the same distribution as $$-(X_i-Z_i)$$ and so it also has the same distribution as $$\epsilon_i(X_i-Z_i)$$. Then \begin{align} \left\|\sum_{i=1}^n(X_i-Z_i)\right\|_p &= \left\|\sum_{i=1}^n\epsilon_i(X_i-Z_i)\right\|_p\\ &\leq \left\|\sum_{i=1}^n\epsilon_iX_i\right\|_p + \left\|\sum_{i=1}^n\epsilon_i Z_i\right\|_p\\ &=2\left\|\sum_{i=1}^n\epsilon_iX_i\right\|_p \quad (*) \end{align}

On the other hand, by convexity of $$|x|^p$$ and Jensen's inequality we get: \begin{align} E\left[\left|\sum_{i=1}^n (X_i-Z_i)\right|^p | X\right] &\geq \left| E\left[\sum_{i=1}^n (X_i-Z_i)|X\right]\right|^p\\ &=\left|\sum_{i=1}^n X_i \right|^p \end{align} where we have use the fact that $$E[Z_i|X]=0$$ for all $$i \in \{1, ..., n\}$$. Taking expectations of both sides gives $$E\left[\left|\sum_{i=1}^n (X_i-Z_i)\right|^p \right] \geq E\left[\left|\sum_{i=1}^n X_i \right|^p\right]$$ Raising both sides to the $$1/p$$ power gives $$\left\|\sum_{i=1}^n (X_i-Z_i)\right\|_p \geq \left\|\sum_{i=1}^n X_i \right\|_p \quad (**)$$ Combining (*) and (**) proves the result.

• Small suggestion - instead of writing the law of $Z$ as that of $-X$, it's perhaps nicer to set it as the law of $X$ and write $X- Z$. This is of course identical, but there's the semantic difference of making clear that you're comparing two independent draws of a vector to one-another. Commented Apr 4, 2021 at 20:05
• @varpi it's important to realise that the heart of the argument is about controlling the size of a vector in terms of the distance between two independent copies of it. The Rademacher representation is useful (leads to notions like Rad. width/Rad. complexity) but hides something at first look. The trick itself is very natural when you consider the case where the $X_i$ may not be centred, in which case you'd introduce the $Z_i$ to manipulate an expectation - $|\sum X_i - \mathbb{E}[X_i]|^p = |\mathbb{E}[\sum X_i + Z_i|X]|^p$ (in the notation of this answer). Commented Apr 4, 2021 at 20:05
• @stochasticboy321 : Good point, I will change the law of $Z$ to the same as $X$ (rather than $-X$). It is a cosmetic change but it indeed simplifies the main ideas. Commented Apr 4, 2021 at 22:20

Extended comment.

I don't have the kind of concrete knowledge to assess the arguments being made in the paper. However, I have heard the semantic associations of 'symmetrization' and 'contraction' in context of 'Rademacher random variables' before. I am aware that both principles form the basis of arguments made in statistical learning theory in the original papers of Vapnik and Chervonenkis, and also in the study of empirical processes.

Having skimmed the references in your paper, the books that I recognise from there and which mention 'symmetrization' in the context of above is:

• A. W. van der Vaart, J.A. Wellner, Weak convergence and empirical processes. With applications to statistics. Springer Series in Statistics. Springer-Verlag, New York, 1996. https://doi.org/10.1007/978-1-4757-2545-2 - see section 2.3.

On symmetrization and contraction principles discussed in proximity of each other, there is a small section in the following book on concentration inequalities:

• Boucheron, S., Lugosi, G., & Massart, P. (2013). Concentration inequalities: A nonasymptotic theory of independence. Oxford: Oxford University Press. DOI:10.1093/acprof:oso/9780199535255.001.0001 - see section 11.3 and also bibliographical remarks in that section for further reading references.

And there is a section on symmetrization in these introductory notes for statisticians on empirical process theory here by B. Sen.

And also the following by a researcher who does research in empirical process theory:

Since Michael has answered the first one, I will write essentially the proof of the second, taken from "Probability in Banach spaces" by Ledoux (as mentioned by Teresa Lisbon in a comment).

We have that

$$E_{\epsilon}[\left\|\sum_{i=1}^n a_i \varepsilon_i \beta_i y_i \right\|_p^p] \leq E_{\epsilon}[\left\|\sum_{i=1}^n a_i \varepsilon_i y_i\right\|_p^p]$$ whenever $$|\beta_i| \leq 1$$. This follows from convexity of $$(\beta_1, ..., \beta_n) \rightarrow \left\|\sum_{i=1}^n a_i \varepsilon_i \beta_i y_i \right\|_p$$, and convex functions achieve their extrema on a boundary point (and this function takes the same value on each of those points). Now, note that since $$Y_i$$ dominates $$X_i$$ stochastically, there exists a coupling $$\pi$$ of all of them, independent of $$\epsilon$$s such that $$\beta_i := \frac{X_i}{Y_i} < 1$$ almost surely (by abuse of notation, consider $$0/0 = 0$$; note that we can construct the coupling be such that $$Y_i = 0$$ implies $$X_i = 0$$). So, in particular, for this set of $$X_i$$, and $$Y_i$$s we have,

$$E_{\epsilon}[\left\|\sum_{i=1}^n a_i \varepsilon_i X_i \right\|_p^p] \leq E_{\epsilon}[\left\|\sum_{i=1}^n a_i \varepsilon_i Y_i\right\|_p^p]$$ $$\pi$$-almost surely. Taking expectation w.r.t. $$\pi$$, and taking the $$p-th$$ root should finish the proof.