Let $X$ be a positive random variable with $\Bbb E X \leq M$. I would like to compute the expectation using Monte-Carlo method, so I am looking for the bounds on $\Bbb P(|\bar X_n - \Bbb E X| \geq \epsilon)$ where $\bar X_n$ is a sample average of $n$ i.i.d. samples of $X$. Chernoff inequality provides such bounds in case I can upped bound the variance, however I only can upper bound expectation with $M$. Is there a version of Chernoff inequality for that case?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
There cannot be such a bound, since the constraint is compatible with arbitrarily high variance and hence, by the central limit theorem, high deviation probabilities for arbitrarily high $n$. The variance of $X$ with $P(X=0)=1-\epsilon$ and $P(X=M/\epsilon)=\epsilon$, with expectation $M$, is
$$ (1-\epsilon)M^2+\epsilon M^2\left(\frac1\epsilon-1\right)^2=M^2\left(\frac1\epsilon+O(1)\right)\;. $$
(This $X$ is merely non-negative, but the modificiation for positive $X$ is trivial.)
-
$\begingroup$ Thanks, I was expecting so, but at the same time I thought that bounded moment of degree $> 1$ could be sufficient. According to your argument, it is not - did I get it correct? $\endgroup$– SBFSep 28, 2015 at 11:01
-
$\begingroup$ @Ilya: Yes; a distribution with $P(X=(M/\epsilon)^{1/d})=\epsilon$ has bounded moment $M$ of degree $d$, yet variance $M^{2/d}(\epsilon^{1-2/d}+O(1))$, which is bounded only for $d\ge2$. $\endgroup$– jorikiSep 28, 2015 at 11:06