Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

1 Answer 1

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.