I have a Chi distribution (not chi-squared distribution) and I don't seems to find any valid closed form tail bound (tight is also needed), (in the large deviation regime).

The MGF is not a simple function so obviously it should not be straightforward.

Any one familier with any valid bound?

  • $\begingroup$ The mgf is $(1-2t)^{-k/2}$. That's pretty simple. If you try to make a bound you'll notice the right value of $t$ falls out pretty easily. $\endgroup$ – Thomas Ahle Jan 11 '19 at 12:31

A $\chi^2$-tail bound implies a $\chi$ distribution tail bound, since if $X$ is a $\chi$-rv with m deg of freedom, $X^2$ is a $\chi^2$-rv with m deg of freedom, and $\{X \geq x \} = \{ X^2 \geq x^2\}$ since both are non-negative r.v.'s (for $x>0$).

Based on this question from cross-validated, which relies on Lemma 1 and its corollary in

Laurent, B.; Massart, P. Adaptive estimation of a quadratic functional by model selection. Ann. Statist. 28 (2000), no. 5, 1302--1338.

You have $P(X^2 -m \geq 2 \sqrt{m x} + 2 x) \leq e^{-x}$ and $P(m - X^2 \geq 2\sqrt{m x}) \leq e^{-x}$.

Rearranging the first one, you get $P(X \geq \sqrt{m + 2 \sqrt{mx} + 2x}) \leq e^{-x}$ and $P(X \leq m - 2 \sqrt{m x}) \leq e^{-x}$.

If you just use a Chernoff bound, $P(X \geq x) = P(X^2 \geq x^2) = P(e^{s X^2} \geq e^{s x^2}) \leq E[e^{s X^2}]/e^{s x^2} = (1-2s)^{-m/2}/e^{s x^2} = e^{-sx^2-\frac{m}{2} \log(1-2s)}$. You can then try optimizing the bound for $0<s<1/2$ by minimizing $-sx^2-\frac{m}{2} \log(1-2s)$ over that interval.


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.