Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

I need to bound the expectation of a nonnegative random variable that satisfies a Poisson-type tail bound:

$\mathbb{P}( X \geq t ) \leq \min( d \cdot (\frac{a}{t} )^{t}, \ 1)$ for $t > 0$

where $a > 0$ and $d \geq 3$. My guess for the mean:

$\mathbb{E} X \leq {\rm const} \cdot \max( a,\ \frac{\log d}{\log \log d} )$

The reference I checked (Ledoux & Talagrand, 1991) helpfully told me that this calculation is "standard". The argument apparently depends on integration by parts, but I can't figure out the trick.

share|improve this question
    
I have to admit this looks like homework to me, but here's a hint: if $t> 2a$ the decay is faster then exponential. –  Ori Gurel-Gurevich Oct 22 '10 at 3:51
    
It's not homework; it's a piece of probability folklore that no one ever bothers to explain. –  jat Oct 22 '10 at 7:39

1 Answer 1

up vote 0 down vote accepted

It's a bit late now (so maybe I made a trivial mistake), but it seems to me that the statement is actually false. Take some large $d$ and set $a=\log d / \log \log d$. Let $t=Ka=K\log d / \log \log d$ for $K$ to fixed soon. Then the tail bound is $$\mathbb{P}(X\ge t) \le d K^{-K\log d / \log \log d}=exp(\log d - \frac{K \log K \log d}{\log \log d})$$ so if we take $K$ not too large (say $K=\log \log \log d$) then the bound is more than 1 and hence the constant random variable $X=t$ satisfies the constraint but has expectation $$Ka=K\frac{\log d}{\log \log d} >> \max(a, \frac{\log d}{\log \log d}) .$$

share|improve this answer
    
@Ori. Thanks; that might explain why I couldn't establish the bound. (It is true without the $\log \log d$ factor, but I expected the Poisson decay to give a little bit extra.) –  jat Oct 24 '10 at 19:15
    
No problem. Just curios: how was this used in Ledoux & Talagrand? –  Ori Gurel-Gurevich Oct 25 '10 at 1:51
    
L&T prove a Rosenthal-type moment bound for sums of independent random variables in a Banach space (Thm. 6.20). The final step in the proof involves integration of $\exp(-u\log(u/K))$, which leads to Poisson-type growth of the constant. –  jat Nov 4 '10 at 0:08
    
Thanks, but I didn't understand: does this mean that they have a mistake? or could the argument be carried our with $\log d$ instead? –  Ori Gurel-Gurevich Nov 4 '10 at 7:02

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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