0
$\begingroup$

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.

1 Answers 1

2

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.