14
$\begingroup$

I am currently working on a project where I generate random values using low discrepancy / quasi-random point sets, such as Halton and Sobol point sets. These are essentially $d$-dimensional vectors that mimic a $d$-dimensional uniform(0,1) variables, but have a better spread. In theory, they are supposed to help reduce the variance of my estimates in another part of the project.

Unfortunately, I've been running into issues working with them and much of the literature on them is dense. I was therefore hoping to get some insight from someone who has experience with them, or at least figure out a way to empirically assess what is going on:

If you have worked with them:

  • What exactly is scrambling? And what effect does it have on the stream of points that are generated? In particular, is there an effect when the dimension of the points that are generated increases?

  • Why is it that if I generate two streams of Sobol points with MatousekAffineOwen scrambling, I get two different streams of points. Why is this not the case when I use reverse-radix scrambling with Halton points? Are there other scrambling methods that exist for these point sets - and if so, is there a MATLAB implementation of them?

If you have not worked with them:

  • Say I have $n$ sequences $S_1, S_2, \ldots,S_n$ of supposedly random numbers, what type of statistics should I use to show that they are not correlated to each other? And what number $n$ would I need to prove that my result is statistically significant? Also, how could I do the same thing if I had $n$ sequences $S_1, S_2, \ldots,S_n$ of $d$-dimensional random $[0,1]$ vectors?

Follow-Up Questions on Cardinal's Answer

  1. Theoretically speaking, can we pair any scrambling method with any low discrepany sequence? MATLAB only allows me to apply reverse-radix scrambling on Halton sequences, and am wondering whether that's simply an implementation issue or a compability issue.

  2. I am looking for a way that will allow me to generate two (t,m,s) nets that are uncorrelated with each another. Will MatouseAffineOwen allow me to do this? How about if I used a deterministic scrambling algorithm and simply decided to choose every 'kth' value where k was a prime?

$\endgroup$
  • $\begingroup$ what do you mean by two $(t,m,s)$ nets being uncorrelated? In particular, what does this mean when you say "us[ing] a deterministic scrambling algorithm"? Many scrambling algorithms can be applied to arbitrary $(t,m,s)$ nets; I honestly don't know if all schemes do. I would imagine the answer might be "no". (That is, one could construct a scrambling that was specialized enough that it maintained the closure property for a particular sequence, but not in general. I don't know about that off-hand.) $\endgroup$ – cardinal Mar 7 '11 at 4:38
  • $\begingroup$ @cardinal Sorry that was unclear, so let me try to rephase it. Say I have two $(t,m,s)$ nets $P$ and $Q$ that I use to generate two sequences of 100 points, $\{p_i\}^{100}_{1}$ and $\{q_i\}^{100}_{1}$. If I use a random scrambling algorithm then $\{p_i\}^{100}_{1}$ and $\{q_i\}^{100}_{1}$ should be uncorrelated, right? Clearly this is not true if I had used a deterministic scrambling algorithm. But what if generated 200 points and only kept even entries of $\{p_i\}^{200}_{1}$ and odd entries from $\{q_i\}^{200}_{1}$. Would these be correlated? And would they still be nicely "spread out"? $\endgroup$ – Berk U. Mar 7 '11 at 6:44
  • $\begingroup$ yes, if you randomly scramble two separate $(t,m,s)$ nets independently of one another, then the resulting sets will be independent. As for a deterministic scrambling algorithm, without any notion of randomness, there really cannot be a proper notion of correlation. I'd have to think about taking even and odd entries. The standard approach would be to get some points for the first one, then generate and throw away a bunch more points, then collect your second set of points. This is related to using "burned in" sets of QMC points. $\endgroup$ – cardinal Mar 8 '11 at 2:48
10
$\begingroup$

Scrambling is usually an operation applied to a $(t,m,s)$ digital net which uses some base $b$. Sobol' nets use $b = 2$, for example, while Faure nets use a prime number for $b$.

The purpose of scrambling is to (hopefully) get an even more uniform distribution, especially if you can only use a small number of points. A good example to see why this works is to look at the Halton sequence in $d = 2$ and choose two "largish" primes, like 29 and 31. The square gets filled in very slowly using the standard Halton sequence. But, with scrambling, it is filled in more uniformly much more quickly. Here is a plot for the first couple hundred points using a deterministic scrambling approach.

enter image description here

The most basic forms of scrambling essentially permute the base $b$ digit expansions of the original $n$ points among themselves. For more details, here is a clear exposition.

The nice thing about scrambling is that if you start with a $(t,m,s)$ net and scramble it, you get a $(t,m,s)$ net back out. So, there is a closure property involved. Since you want to use the theoretical benefits of a $(t,m,s)$ net in the first place, this is very desirable.

Regarding types of scrambling, the reverse-radix scramble is a deterministic scrambling. The Matousek scrambling algorithm is a random scramble, done, again, in a way to maintain the closure property. If you set the random seed before you make the call to the scrambling function, you should always get the same net back.

You might also be interested in the MinT project.

$\endgroup$
  • $\begingroup$ Thank you so much for this. I had some follow-up questions if you don't mind. Since the comment box doesn't allow me to list them clearly, I included them in the post. $\endgroup$ – Berk U. Mar 7 '11 at 0:10

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.