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.

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

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}) .$$

| cite | improve this answer | |
  • $\begingroup$ @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.) $\endgroup$ – jat Oct 24 '10 at 19:15
  • $\begingroup$ No problem. Just curios: how was this used in Ledoux & Talagrand? $\endgroup$ – Ori Gurel-Gurevich Oct 25 '10 at 1:51
  • $\begingroup$ 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. $\endgroup$ – jat Nov 4 '10 at 0:08
  • 1
    $\begingroup$ 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? $\endgroup$ – Ori Gurel-Gurevich Nov 4 '10 at 7:02

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.