2
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • $\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
    Commented Oct 22, 2010 at 3:51
  • $\begingroup$ It's not homework; it's a piece of probability folklore that no one ever bothers to explain. $\endgroup$
    – jat
    Commented Oct 22, 2010 at 7:39

1 Answer 1

Reset to default
0
$\begingroup$

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

Improve this answer
$\endgroup$
4
  • $\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
    Commented Oct 24, 2010 at 19:15
  • $\begingroup$ No problem. Just curios: how was this used in Ledoux & Talagrand? $\endgroup$
    – Ori Gurel-Gurevich
    Commented Oct 25, 2010 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
    Commented Nov 4, 2010 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
    Commented Nov 4, 2010 at 7:02

You must log in to answer this question.

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