Suppose I have some random variable $X$ taking values in $[a, b]$ with unknown distribution (I am happy to assume the distribution is smooth, though it would be nice to not have to).

I have a function $F(t)$ which takes a value in $[a, b]$ and returns a random variable on $[0, 1]$ such that $E(F(t)) = P(X <= t)$. I can't actually get the distribution of $F(t)$, only sample from it. This is 'expensive to compute' so I want to do it as few times as possible. The set $\{F(s)\}$ may be assumed to be independent.

I would like to use $F$ to construct estimators of $E(X)$ and $Var(X)$. Ideally they'd be unbiased estimators, but I don't actually care that much as long as they're reasonably accurate.

An obvious approach is to divide up $[a, b]$ into a grid $x_1, \ldots, x_m$, sample $F(x_i)$ enough times to get a good estimate of $E(F(x_i)) = P(X \leq x_i)$ and use this to get an approximation to the expectations. This is quite expensive, and seems to ignore a bunch of available information (like the fact that $P(X \leq x_i)$ is monotonic increasing, or the fact that $P(X \leq x - \epsilon)$ is probably still a pretty good estimate for $P(X \leq x)$).

An approach that I think works better is to use the fact that $E(X) = \int\limits_a^b P(X \geq x) dx$. So $E(\frac{1}{n}\sum 1 - F(x_i)) = \frac{1}{n} \sum P(X \geq x_i)$ can also be used as an estimate, and I think this requires fewer samples for accuracy, however I'm not really sure how accurate this is.

So, basically I'm wondering what the best approach is for trading off accuracy / number of samples. Any suggestions? Pointers to keywords and/or literature that might have bearing on this are also appreciated as I haven't been able to find much.


It turns out that the second approach is actually pretty good, because you can apply Hoeffding's inequality.

Let $R$ be uniform on $[a, b]$. Then $E(1 - F(R)) = \frac{E(X) - a}{b - a}$. So if we sample $T_1, \ldots, T_n$ from $a + (b - a)(1 - F(R))$ we have that $P(|\frac{1}{n} \sum T_i - E(X)| \geq \epsilon (b - a)) \leq 2 e^{-2 \epsilon^2 n}$

So if we want to get within $\epsilon(b - a)$ with probability $p$ all we need is $n \geq \frac{-\log(\frac{p}{2})}{2 \epsilon^2}$

You can then do the same thing with $1 - F(R^2)$ to get a good estimate of $E(X^2)$ and from there the variance.

That $\frac{1}{\epsilon^2}$ factor is kinda painful though.

(Leaving this answer unaccepted in the hope that someone has a better one)


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.