3
$\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$
  • 2
    $\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$ – kjetil b halvorsen Sep 27 '12 at 12:59
  • $\begingroup$ @kjetilbhalvorsen: Thanks! Is the acceptance-rejection method still valid for quasi random numbers? What other methods are still valid, and are invalid? $\endgroup$ – Tim Sep 29 '12 at 23:29
  • $\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$ – kjetil b halvorsen Sep 30 '12 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 '12 at 13:14
  • 1
    $\begingroup$ Yes. The acceptance-rejection method will be invalid for quasi-random numbers. $\endgroup$ – kjetil b halvorsen Sep 30 '12 at 18:31
5
$\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$
  • $\begingroup$ Welcome to our site, Quartz! $\endgroup$ – whuber Sep 28 '12 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, privacy policy and cookie policy

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