ChapterZero

Explicit Moment, Tail bound connection

It’s useful to know the explicit constants in the connection between the moment bounds of a variable and its tail bounds. I’m recording the calculation in this post because I don’t want to have to do it again.

Assume is a positive variable with a moment bound of the form $(\mathbb{E}X^k)^{1/k} \leq c_m k^{1/s},$ where $0 < s < \infty,$ then we'll show that this implies that the moment generating function for X^s is finite at some point. Since we'll bound the value of the moment generating function at that point, we can then use Markov's inequality to get exponentially decaying tails for

To begin, we expand the moment generating function of X^s at c_t :

$\displaystyle \mathbb{E}e^{c_t X^s} = \sum_{p=0}^\infty \frac{c_t^p \mathbb{E}X^{sp} }{p!} \leq \sum_{p=0}^\infty \frac{(c_t c_m^s s e)^p}{\sqrt{2 \pi p}},$

where we use Stirling’s approximation to see $p! \geq \sqrt{2\pi p} \left(p/e\right)^p.$
Fix $\alpha \in (0,1)$ and take $c_t = \frac{\alpha}{c_m^s s e}$ , then $\mathbb{E}e^{c_t X^s} < \frac{1}{1-\alpha}.$

By Markov's inequality,

$\displaystyle \mathbb{P}( X > \tau) \leq \frac{\mathbb{E}e^{c_t X^s} }{e^{c_t \tau^s}} < \frac{1}{1-\alpha} e^{-c_t \tau^s}.$

To summarize,

$\displaystyle (\mathbb{E}X^k)^{1/k} \leq c_m k^{1/s} \Rightarrow \mathbb{P}(X > \tau) \leq 2 \exp\left(-\frac{\tau^s}{2c_m^s s e}\right).$

Possibly relevant posts:

Sharpness of Moment bounds, exponential example (7/29/2010)
Comparing products of gaussian moments with one gaussian moment (8/13/2010)
One direction in Khintchine’s inequality for Rademacher sums (9/26/2008)

Tags: inequality, tail bound

Explicit Moment, Tail bound connection

Possibly relevant posts:

Leave a comment

Archives

intelligently designed

light and not filling

Tags