How can I compute an upper bound for expectation from CCDF upper bound?

89 Views Asked by At

Consider the following setup:

  1. $X$ is a non-negative random variable.
  2. $t \in \{1,2,3,\dots\}$.
  3. $a, b, c > 0, d > 1$ are fixed constants.

I know the following bound: For any $\delta \in (0,1)$, there exists $t_0$ such that for all $t \geq t_0$:

$$P(X > \frac{a}{\sqrt{t}} \sqrt{b - \log \delta} + \frac{c}{\delta} d^{-\log^2 t}) \leq 4\delta.$$

Intuitively, this bound says the following. For any small $\delta$, if $t$ is large enough, then with high probability $X$ is small.

I want to use this probability bound to find a bound on $\mathbb{E}[X]$. Here is my attempt:

Let

$$x = \frac{a}{\sqrt{t}} \sqrt{b - \log \delta} + \frac{c}{\delta} d^{-\log^2 t} \quad \Rightarrow \quad \frac{d x}{d \delta} = - \frac{a}{\sqrt{t}\delta} - \frac{c d^{-\log^2 t}}{\delta^2}$$

We can write

$$ \mathbb{E}[X] = \int_{x=0}^\infty P(X>x) dx \leq \int_{\delta = 0}^1 4 \delta (\frac{a}{\sqrt{t}\delta} + \frac{c d^{-\log^2 t}}{\delta^2}) d\delta = \int_{\delta = 0}^1 \frac{4a}{\sqrt{t}} + \frac{4c d^{-\log^2 t}}{\delta} d\delta, $$

But the above integral is not finite. Is my approach correct, specifically regarding integrating over $\delta$? Is it possible to compute a finite bound on $\mathbb{E}[X]$?


Update: Here is another approach that gives a different result. Set $\delta = 1/t$ and assume $t \in \mathbb{R}, t \geq 1$. In this case, we have

$$x = \frac{a}{\sqrt{t}} \sqrt{b + \log t} + c t d^{-\log^2 t} \quad \\ \Rightarrow \quad \frac{d x}{d \delta} = - \frac{a\sqrt{b + \log \delta}}{2t^{3/2}} + \frac{a}{2t^{3/2} \sqrt{b + \log t}} - 2 c \log(d) \log(t) d^{-\log^2 t} = g(t)$$

And the following integral is finite

$$\mathbb{E}[X] = \int_{t=1}^\infty \frac{4}{t} g(t) dt < \infty.$$

Which approach is correct?