How to prove the proposition?

Question

Proposition: Let $X \sim \chi^2_m$. Then, $$P (X \geq t) \leq \left(\frac{t}{m}\right)^{\frac{m}{2}} \exp{\left(- \frac{t-m}{2}\right)}$$

How I can prove it?

Answer 1

First, let $X= \sum_{i=1}^m y_i^2 \sim \chi^2_m$.

Pick any parameter $\lambda \in [0, \frac{1}{2})$.

By using Chernoff bounds, we write $$Pr [X \geq t] = Pr [e^{\lambda x} \geq e^{\lambda t}] \leq e^{-\lambda t} E[e^{\lambda x}].$$

Then we can write $$ E[e^{\lambda x}]=E[\exp (\lambda \sum_{i=1}^m y_i^2)]=\prod_{i=1}^m E[\exp (\lambda y_i^2)]. $$

Expanding the expectation, we get $$E[\exp (\lambda y_i^2)]=\frac{1}{\sqrt{2 \pi}} \int_{-\infty}^{\infty} \exp (\lambda x^2) \exp (-x^2/2) dx=\frac{1}{\sqrt{2 \pi}} \int_{-\infty}^{\infty} \exp(-x^2 (\frac{1}{2}-\lambda))dx.$$

If that $\frac{1}{2}-\lambda$ factor were simply $\frac{1}{2}$, then, we could evaluate that integral using the fact that $e^{-z^2}/\sqrt{2 \pi}$ is the pdf of a standard normal random variable, so it integrates to 1.

We can accomplish that with change of variables. Using $Z=x\sqrt{1-2\lambda}$, $\lambda \in [0,1/2)$, we get $$E[\exp (\lambda y_i^2)]=\frac{1}{\sqrt{2 \pi}} \int_{-\infty}^{\infty} \exp (-(x\sqrt{1-2\lambda})^2/2)dx =\frac{1}{\sqrt{2 \pi}\sqrt{1-2\lambda}}\int_{-\infty}^{\infty} \exp (-z^2/2)dz= \frac{1}{\sqrt{1-2\lambda}}.$$

We get $Pr[X \geq t] \leq e^{-\lambda t}(1-2\lambda)^{-m/2}$. Set $\lambda=(1-\frac{m}{t})/2$. Then, $$Pr[X \geq t] \leq e^{\frac{m-t}{2}} (\frac{m}{t})^{-\frac{m}{2}}=(\frac{t}{m})^{\frac{m}{2}} \exp (-\frac{t-m}{2}).$$