The coverage sampler algorithm, described above, requires
estimating , and using it, the coefficient . We
estimate by computing the expectation in equation
(4) at uniform random samples in . To estimate the
confidence and accuracy of this estimate, note that
Then, using Hoeffding’s Inequality the
probability of the average of samples, denoted
, not falling within of
Thus, we get an additive -approximation with
probability by picking larger than
This yields the following
Monte-Carlo algorithm to estimate .
Algorithm 5.Estimate Ball Integral
Input. The region, , error threshold ,
and confidence parameter .
Output. Estimate of .
- Compute .
- set sum = 0
- for i = :
- sample uniformly in
- set sum = sum +
- return sum / n
Finally, we get a lower bound on the max ratio:
where is the estimate using algorithm above, with
the error threshold.