Question

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.

Answer 1

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