4

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!

Tim
  • 1
  • 29
  • 102
  • 189
  • 3
    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). – kjetil b halvorsen Sep 27 '12 at 12:59
  • @kjetilbhalvorsen: Thanks! Is the acceptance-rejection method still valid for quasi random numbers? What other methods are still valid, and are invalid? – Tim Sep 29 '12 at 23:29
  • 1
    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. – kjetil b halvorsen Sep 30 '12 at 03:22
  • 1
    Thanks, @kjetilbhalvorsen. The acception-rejection method uses more than one random variables, so is it invalid for quasi? – Tim Sep 30 '12 at 13:14
  • 2
    Yes. The acceptance-rejection method will be invalid for quasi-random numbers. – kjetil b halvorsen Sep 30 '12 at 18:31
  • 1
    @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!) – Xi'an Mar 25 '16 at 20:59
  • @Xi'an: Maybe, that would need a proof, though. What one could do is use only one element from the quasi-random sequence, and then for the rest of the numbers needed for the rejection step, using a usual pseudo-random sequence. – kjetil b halvorsen Mar 26 '16 at 13:14

2 Answers2

5

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.

Quartz
  • 878
  • 8
  • 18
0

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

Marius Hofert
  • 164
  • 4