Let $X \sim \chi^2_n$ random variable. I am looking for a large deviation upper bound for $X$. The answer here, says that

Since you said that you're looking for an upper bound, it should also be noted that an examination of the proof of Cramer's theorem shows that you can actually get uniform exponential upper bounds (and not just asymptotics as stated above). In fact, $$ P(X_n < cn) \leq e^{-n I(c)}, \quad \forall n\geq 1, \text{ and } 0 < c < 1. $$

This bound will be quite useful to me, but I don't quite see how the proof follow's from Cramer's theorem. I am looking at the proof of Cramer's Theorem here, and I don't see how I can get rid of the asymptotics.


See B. Laurent and P.Massart, Adaptive estimation of a quadratic functional by model selection, Ann. Stat., 28 (2000) 1302--1338.

Equations (4.3) and (4.4) say that for any $x\gt 0$:

$$P(X_n \ge n + 2\sqrt{nx}+2x) \le e^{-x}.$$ $$P(X_n \le n - 2\sqrt{nx}) \le e^{-x}.$$

  • $\begingroup$ Huh, are you saying if I use $x = nI(c)$ in the second equation, the result follows? $\endgroup$ – Greenparker Jul 27 '18 at 12:13
  • $\begingroup$ I don't know. Try it and see how it compares. $\endgroup$ – Brendan McKay Jul 27 '18 at 16:06
  • $\begingroup$ It depends on the value of $c$. Sometimes the L+M bounds are cruder and sometimes they are tighter. And sometimes for small values of $c$, $n - 2\sqrt{n I(c)}$ is negative, so providing no information. Thanks for the inequalities; this is a good comment, but I can't accept it as an answer. $\endgroup$ – Greenparker Jul 27 '18 at 16:20

You can just use a standard technique for deriving Chernoff-Hoefding type bounds. The MGF of $X \sim \chi^2_n$ is

$$ {\mathbb E} e^{tX} = (1-2t)^{-n/2}. $$

For $t<0$ we have

$$ \begin{array}{rcl} {\mathbb P}( X < c n ) & \overset{t<0}= & {\mathbb P}( e^{tX} > e^{tcn} ) \\ & \overset{\text{Markov}}\leq & \left({\mathbb E} e^{tX} \right) / e^{tcn} \\ & = & \exp\left[ - (n/2) \cdot \ln( 1 - 2t ) - tcn \right] \\ & = & \exp\left[ - n \cdot \left( tc + \frac12 \ln(1-2t) \right) \right]. \end{array} $$

Now we choose $t$ so that $tc + \frac12 \ln(1-2t)$ is maximized. (Note the maximizer is $<0$ if $0<c<1$.) With this value of $t$ the last expression in the display becomes the desired bound $e^{-n I(c)}$.

The same technique works for deriving the upper bound ${\mathbb P}( X > cn ) \leq e^{-n I(c)}$ when $c>1$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.