Skip to main content
edited tags
Link
Iosif Pinelis
  • 127.7k
  • 8
  • 107
  • 229
Source Link
gradstudent
  • 2.2k
  • 16
  • 28

Bounded difference functions and sub-Gaussian random variables

We have the following standard theorem : Let $X$ be some set and $g : X^n \rightarrow \mathbb{R}$ be a measurable function such that it satisfies the ``bounded difference property" i.e $\exists$ $\{c_i \geq 0\}_{i=1,..,n}$ s.t for each $i$ we have , $\sup _{x_1,..,x_n, x'_i \in X} \vert g(x_1,.,x_n) - g(x_1,..,x_i',..x_n)\vert \leq c_i $. Then the following is true, $\mathbb{P}[\vert Z - \mathbb{E}[Z] \vert >t] \leq 2e^{-\frac{t^2}{4\sum_{i=1}^nc_i^2}}$ i.e $\vert Z - \mathbb{E}[Z] \vert$ is sub-Gaussian.

  • Now how does the above standard theorem imply how the following inequality

$$\mathbb{E}[e^{\lambda (Z - \mathbb{E}[Z])}] \leq e^{\frac{\lambda^2 \sum_{i=1}^nc_i^2 }{2}}$$ $$?$$