Symmetrization

05 Mar 2018

Prologue To The Symmetrization

In machine learning, statistics, probability theory, the symmetrization is commonly used to relate the random variables belonging to the same distribution.

The Symmetrization

Given a bounded random variable $Z\in\lbrack a,b\rbrack$, we perform multiple tests of it with instances of $Z$ duplicated, choose one of the clones to be $Z’$, so that $Z’\in\lbrack a,b\rbrack$ and $E\lbrack Z\rbrack$=$E\lbrack Z’\rbrack$.
There exists some properties:
[1]$E_Z\lbrack e^{Z-E\lbrack Z\rbrack}\rbrack\le E_Z\lbrack E_{Z’}\lbrack e^{Z-Z’}\rbrack\rbrack$
[2]$P(\left|Z-E\lbrack Z\rbrack\right|\ge t)$=$P(\left|Z-E\lbrack Z’\rbrack\right|\ge t)$
$\le E\lbrack e^{\lambda\cdot E\lbrack\left|Z-Z’\right|\rbrack}\rbrack\cdot e^{-\lambda\cdot t}$
[3]$E_Z\lbrack E_{Z’}\lbrack e^{\lambda\cdot (Z-Z’)}\rbrack\rbrack\le e^{\frac {(\lambda\cdot (b-a))^{2}}{2}}$

proof::mjtsai1974

➀by given, $E\lbrack Z\rbrack$=$E\lbrack Z’\rbrack$, then,
$E_Z\lbrack Z-E\lbrack Z\rbrack\rbrack$=$E_Z\lbrack Z-E\lbrack Z’\rbrack\rbrack$
And according to the Jensen's inequality, we have it that
$E_Z\lbrack e^{Z-E\lbrack Z\rbrack}\rbrack$
=$E_Z\lbrack e^{Z-E\lbrack Z’\rbrack}\rbrack$
$\le E_Z\lbrack E_{Z’}\lbrack e^{Z-Z’}\rbrack\rbrack$
➁by the Chernoff bounds, we can have
$P(\left|Z-E\lbrack Z\rbrack\right|\ge t)$
=$P(\left|Z-E\lbrack Z’\rbrack\right|\ge t)$
=$P(e^{\lambda\cdot\left|Z-E\lbrack Z’\rbrack\right|}\ge e^{\lambda\cdot t})$
$\le E\lbrack e^{\lambda\cdot\left|Z-E\lbrack Z’\rbrack\right|}\rbrack\cdot e^{-\lambda\cdot t}$
$\le E\lbrack e^{\lambda\cdot E\lbrack\left|Z-Z’\right|\rbrack}\rbrack\cdot e^{-\lambda\cdot t}$
➂given that $S\in\{+1,-1\}$, a Rademacher random variable, and $S\cdot (Z-Z')$ and $Z-Z'$ have the same distribution, it implies that
$E_Z\lbrack E_{Z’}\lbrack e^{Z-Z’}\rbrack\rbrack$
=$E_Z\lbrack E_{Z’}\lbrack e^{S\cdot (Z-Z’)}\rbrack\rbrack$
=$E_{Z,Z’}\lbrack E_{S}\lbrack e^{S\cdot (Z-Z’)}\rbrack\rbrack$
Then, below holds,
$E_Z\lbrack E_{Z’}\lbrack e^{\lambda\cdot (Z-Z’)}\rbrack\rbrack$
=$E_Z\lbrack E_{Z’}\lbrack e^{S\cdot\lambda\cdot (Z-Z’)}\rbrack\rbrack$
=$E_{Z,Z’}\lbrack E_{S}\lbrack e^{S\cdot\lambda\cdot (Z-Z’)}\rbrack\rbrack$
➃by MGF, we have below holds
$E_{S}\lbrack e^{S\cdot\lambda\cdot (Z-Z’)}\rbrack\le e^{\frac {(\lambda\cdot (Z-Z’))^{2}}{2}}$
Because $\left|Z-Z'\right|\le (b-a)$ guarantees $(Z-Z')^{2}\le (b-a)^{2}$ , then
$E_{S}\lbrack e^{S\cdot\lambda\cdot (Z-Z’)}\rbrack\le e^{\frac {(\lambda\cdot (b-a))^{2}}{2}}$
Therefore, $E_Z\lbrack E_{Z’}\lbrack e^{\lambda\cdot (Z-Z’)}\rbrack\rbrack\le e^{\frac {(\lambda\cdot (b-a))^{2}}{2}}$