Skip to main content
2 of 7
added 40 characters in body
alfC
  • 161
  • 1
  • 3

I recently stumbled upon this problem. Naively I thought that any transformation from uniform would work, so I plugged in a 1D Sobol (and Halton) sequence as if the sequence where a random number generator into an std::normal_distribution<> variate. To my surprise it didn't work, it obviously generated a non normal distribution.

Ok, then I took the Numerical Recipes Third Edition Chapter 7.3.9 Normal_dev function to generate normal numbers from the Sobol or Halton sequences by the method of "Ratio-of-Uniforms" and it failed in the same way. Then I though, ok, if you look at the code, it takes two uniform random numbers to generate two normally distributed random numbers. Perhaps if I used a Sobol (or Halton) 2D sequence it will work. Well, it failed again.

The I remembered about the "Box-Muller method" (mentioned in the comments) and since it has a more geometric interpretation then I though it could work. Well, it did work! I was very excited an starting doing other test, the distribution looks normal.

The problem I saw was that the distribution was no better than random, it terms of filling, so I was a bit disappointed, but ready to publish the result.

Then I did a deeper search (now that I knew what to look for), and it turn out that there is already a paper on this subject: http://www.sciencedirect.com/science/article/pii/S0895717710005935

In this paper it is actually claimed

Two well known methods used with pseudorandom numbers are the Box–Muller and the inverse transformation methods. Some researchers and financial engineers have claimed that it is incorrect to use the Box–Muller method with low-discrepancy sequences, and instead, the inverse transformation method should be used. In this paper we prove that the Box–Muller method can be used with low-discrepancy sequences, and discuss when its use could actually be advantageous.

So the overall conclusion is this:

  1. You can use the Box-Muller on 2D low discrepancy sequences to obtain normally distributed sequences. But the low discrepancy/space filling properties seem to be lost.

  2. You can use the inverse method, presumably the low discrepancy/space filling properties will be preserved.

  3. Ratio-of-Uniforms cannot be used.

EDIT: This http://mathoverflow.net/a/144234 points to the same conclusions.

I made an illustration:

figures

alfC
  • 161
  • 1
  • 3