1
$\begingroup$

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?

$\endgroup$
1
  • $\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$ Jan 11, 2019 at 12:31

1 Answer 1

4
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .