Suppose that, for a discrete, simple, and positive random variable $X$, it happens with probability $ 1 - 1/n$ that $X\le f(n)$, for some function $f(n) \in o(n)$. I don't know anything else about the actual distribution of $X$.

Is it possible to upper bound $E[X]$ in terms of $f(n)$? The intuition I have is that if $X$ is less than $f(n)$ with high probability, then clearly it's expectation should also be less than $f(n)$.

This seems to be like a converse statement of Markov's inequality where we know something about the expectation and use it to bound the random variable itself.


It's not entirely clear to me what it would mean for the expectation to be less than $f(n)$, which depends on $n$. I think you'll need something a bit stronger than $f(n)\in o(n)$ to get a bound. Assume that $f(n)$ is strictly increasing, and consider the discrete distribution that assigns probability $2^{-k}$ to $f(2^k)$ for $k\in\mathbb N$. Then for $f(n)=n\log_2^{-s}(n)$ with $0\lt s\lt1$ we have

$$E[X]=\sum_{k=1}^\infty2^{-k}f(2^k)=\sum_{k=1}^\infty2^{-k}2^kk^{-s}=\sum_{k=1}^\infty k^{-s}=\infty$$

despite $f(n)\in o(n)$. Perhaps $f(n)\in o(n^{1-\epsilon})$ might lead to something.


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.