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. 



Estimating mean and variance of a distribution based on error-prone estimates of its cdf
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)


