4
$\begingroup$

From Wikipedia

quasi-Monte Carlo method is a method for numerical integration and solving some other problems using low-discrepancy sequences (also called quasi-random sequences or sub-random sequences).

It seems to me low discrepancy sequences if seen as random samples are samples of uniform distributions, and not non-uniform distributions. Am I correct or not? Thanks!

$\endgroup$
7
  • 3
    $\begingroup$ As defined it is usually meant for uniform distribution on $[0,1]$, but you can use the same inversion methods that you use with pseudo-random numbers to get to other distributions. (But you must stay with inversion, most other methods for generating non-uniform distributions will be invalid). $\endgroup$ Sep 27, 2012 at 12:59
  • 1
    $\begingroup$ All methods I have seen that use more tha one random number in input per output non-uniform-random, will be invalid with quasi-random numbers, the point withn quasi-random numbera are just to avoid independence to get better reselts for numerical integration. Inversion uses just one number, so do not depend on independence. $\endgroup$ Sep 30, 2012 at 3:22
  • 1
    $\begingroup$ Thanks, @kjetilbhalvorsen. The acception-rejection method uses more than one random variables, so is it invalid for quasi? $\endgroup$
    – Tim
    Sep 30, 2012 at 13:14
  • 2
    $\begingroup$ Yes. The acceptance-rejection method will be invalid for quasi-random numbers. $\endgroup$ Sep 30, 2012 at 18:31
  • 1
    $\begingroup$ @kjetilbhalvorsen: I am not sure it is invalid if you generate a different sequence of quasi-random numbers for each acceptance, using bounds on the acceptance probability to make sure the sequence is long enough. (I am not sure either this would have any form of efficiency!) $\endgroup$
    – Xi'an
    Mar 25, 2016 at 20:59

2 Answers 2

6
$\begingroup$

I second what kjetil said. Additionally beware that because of their determinism you cannot apply the usual MC confidence estimates to the result, those are based on randomness and CLT theorems. So LDS are uniform sequences but not random at all. This means you can use them for tasks such as integration (where uniformity is important, not randomness) and search, but not in those relying necessarily on randomness without proper corrections. E.g. for some LDS you get a lower bound on distance between two points, contrarily to pseudo/random sequences. You can also lookup "randomized QMC" to see hybrid methods to recover probabilistic confidence intervals.

$\endgroup$
1
  • $\begingroup$ Welcome to our site, Quartz! $\endgroup$
    – whuber
    Sep 28, 2012 at 16:56
0
$\begingroup$

You might find this article interesting, in fact, it addresses exactly your question. Disclaimer: I'm one of the authors of the article.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.