How to estimate the accuracy of an integral? An extremely common situation in computer graphics is that the colour of some pixel is equal to the integral of some real-valued function. Often the function is too complicated to solve analytically, so we're left with numerical approximation. But the function is also often very expensive to compute, so we're greatly constrained in how many samples we can compute. (E.g., you can't just decide to take one million samples and leave it at this.)
In general then, what you want to do is evaluate the function at randomly-chosen points until the estimated integral becomes "accurate enough". Which brings me to my actual question: How do you estimate the "accuracy" of the integral?

More specifically, we have $f : \mathbb{R} \rightarrow \mathbb{R}$, which is implemented by some complicated, slow computer algorithm. We want to estimate
$$k = \int_a^b f(x) \ dx$$
We can compute $f(x)$ for any $x$ we desire, but it's expensive. So we want to choose several $x$-values at random, and stop when the estimate for $k$ becomes acceptably accurate. To do this, of course, we need to know how accurate the current estimate actually is.
I'm not even sure what statistical tools would be appropriate for this kind of problem. But it appears to me that if we know absolutely nothing about $f$, then the problem is unsolvable. For example, if you compute $f(x)$ a thousand times and it's always zero, your estimated integral would be zero. But, knowing nothing about $f$, it's still possible that $f(x) = 1,000,000$ everywhere except the points you happened to sample, so your estimate is horribly wrong!
Perhaps, then, my question should have started with "what do we need to know about $f$ to make it possible to estimate the accuracy of our integral?" For example, often we know that it is impossible for $f$ to ever be negative, which would appear to be a highly relevant fact...

Edit: OK, so this seems to have generated lots of responses, which is good. Rather than reply to each of them individually, I'm going to try to fill in some additional background here.
When I say we know "nothing" about $f$, I mean that we can compute $f$, but we don't know anything further about it. I would expect (and the comments seem to agree) that having more knowledge allows us to use better algorithms. It seems that knowing bounds on $f$ and/or the first derivative of $f$ would be useful.
In most of the problems I'm thinking about, $f$ changes depending on scene geometry and the location within the scene under consideration. It's not some nice, tidy piece of algebra that you can analytically solve. Typically $f$ represents light intensity. Obviously light intensity can't ever be negative, but there is no limit to how large its positive values can be. And finally, object edges usually result in sharp discontinuities in $f$, and usually you can't predict where these are.
In short, $f$ is damned fiddly, so my first port of call was to ask what we can do with it given no further information. It appears that without at least some upper and lower bounds, the answer is "not a hell of a lot"... So it looks like I need to start making up some assumptions to make any headway here.
Also, given the number of times "Monte Carlo" has come up, I'm guessing that's the technical term for this sort of integration?
 A: This is a non-trivial question that involves issues like total variation of $f$ and its reasonable multivariate extensions. The Stanford statistician Art Owen has worked on this using randomized quasi-Monte Carlo techniques. The regular Monte Carlo allows direct estimation of the accuracy of the integral, but each individual evaluation is not that accurate. Quasi-Monte Carlo produces more accurate estimates, but it is a fully deterministic technique, and as such does not allow to estimate the variance of your result. He showed how to combine the two approaches, and his paper is very lucid, so I won't try to reproduce it here.
A supplementary reading to this would of course be Niederreiter (1992) monograph.
A: For simplicity assume f(x)>=0 for all x in[a,b] and we know M such that f(x) < M for all x in [a,b].  The the integral I of f over [a,b] can be enclosed in the rectangle with width b-a and hight M.  The integral of f is the proportion of the rectangle that falls under the function f multiplied by M(b-a).  Now if you pick points in the rectangle at random and count the point as a success if it falls under the curve and as a failure otherwise you have set up a Bernoulli trial .  The sample fraction of points inside is a binomial proportion and hence has mean p and variance p(1-p)/n where n is the number of points taken.  Hence you can construct a confidence interval for p and since I =p M(b-a) a confidence interval for I also since for the estimate I^ =p^ M (b-a), Var(I^)= M$^2$(b-a)$^2$ p(1-p)/n.  So to use statistics to determine the smallest n for which the integral is accurate enough you could specify an upper limit S on the variance of I^. Note p(1-p)/n <=1/(4n) for every 0<=p<=1. So set S=M$^2$(b-a)$^2$ /(4n) or n = smallest integer> M$^2$(b-a)$^2$ /(4S). 
