8
$\begingroup$

Whenever one uses a quasi-Monte Carlo method for cubature or optimization, it seems that there's a wide variety of low-discrepancy sequences to choose from, associated with the names of van der Corput, Halton, Hammersley, Faure, Niederreiter, Sobol', and other names I don't quite remember. Are there any good rules of thumb on how to choose the most appropriate low-discrepancy sequence for your computations?

$\endgroup$
2
$\begingroup$

The Koksma-Hlawka Inequality states that if $f$ has bounded variation $V(f)$ in the sense of Hardy and Krause on the unit hypercube $I^s$, then the error bound is given by the product of $V(f)$ and the star-discrepancy of the sequence used. That the error depends on only the discrepancy yields two conclusions. First, choose the sequence with lowest discrepancy. Second, the regularity of the integrand plays no role in this bound and so in practice it's not very useful. To incorporate more information about the integrand into your error analysis, you have to either perform experimental comparisons between sequences or consider other approaches besides basic quasi-Monte Carlo.

$\endgroup$
2
$\begingroup$

My understanding is that the situation mirrors that found in iterative methods. We can prove general results, like $\frac{1}{N}$ decay of the quadrature error, but cannot determine the optimal algorithm for a given problem a priori. Here is a catalogue of open source software for sequence generation. I think the best approach here is more testing and comparison.

$\endgroup$
1
$\begingroup$

Each LDS sequence has specific advantages and caveats and discussing them would fill many books (check Lemieux's one for an introduction), however in general the most versatile one proved to be Sobol' sequence (make sure to use the latest parameters from Joe&Kuo). All others always require in practice significant additional modifications to both integrand and LDS points (e.g. scrambling) w.r.t. to the basic formulations. Sobol' also has many issues, but is flexible enough to be used in most sufficiently smooth integrations at low dimensions. Anyway remember to check your QMC solution against a (slower) MC one: for low (reasonable) sample sizes QMC could return biased estimates.

There are also more advanced LDS constructions for adapting to a given problems, but little SW available.

Some information on your specific task would be helpful to focus an answer.

$\endgroup$
  • $\begingroup$ I didn't really have a specific task in mind when I wrote the question (it was a seed question), but I did remember a time when I was a bit overwhelmed by the number of LDSs available while I was researching these. Thanks for the answer! $\endgroup$ – J. M. Dec 15 '11 at 12:23
0
$\begingroup$

Where we've used monte carlo simulation, the recommendation (from folks who work in the other national labs) is to use "good" pseudo-random number generators. The last one I worked on used Yarrow, but newer ones would use Fortuna or Mersenne-Twister.

$\endgroup$
  • 1
    $\begingroup$ The question is asking about quasi-Monte Carlo, not true Monte Carlo. So yes, I'm asking about low-discrepancy sequences, not pseudorandom sequences. You are answering a different question. $\endgroup$ – J. M. Dec 1 '11 at 23:41

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.