Section 7.7 - Sobol sequence


Edo
01-05-2004, 02:01 PM
When I use the sobseq routine in Section 7.7, I seem to get different results than the ones presented in Figure 7.7.1? Any idea why?

I get the following 2d sequence...
0.5 0.5
0.25 0.75
0.75 0.25
0.375 0.625
0.875 0.125
0.125 0.375
0.625 0.875
0.3125 0.3125
0.8125 0.8125
0.0625 0.5625
0.5625 0.0625
0.1875 0.9375
0.6875 0.4375
0.4375 0.1875
0.9375 0.6875
0.46875 0.84375
0.96875 0.34375
0.21875 0.09375
0.71875 0.59375
0.09375 0.46875

The first 3 points seem to agree, but the 4th (0.375, 0.625) and 5th (0.875, 0.125) seem to be missing from the first graph ("points 1 to 128") in the figure. (There even seems to be some discrepancies between the 4 plots in Figure 7.7.1 - where is the tight cluster of 3 points in the far upper left corner of the 3rd panel in the cumulative 4th panel?) Which sequence is correct, the one above or the one used to generate the figure? If the data I've listed is correct, Figure 7.7.1 and the corresponding comments about filling in the "gaps" seem to be incorrect as I do not get the same patterns in the plots from the above sequence. If the figure is correct, is the code for sobseq() wrong? Comments?

I also have questions about the generation of Figure 7.7.2...

Which "conventional pseudo-random sequence" was used?

Was some sort of smoothing done to the graph (beyond the rms averaging of 100 trials)? My re-creation of the plot is more jagged. How often did you sample along the x-axis (number of points N)?

Also, why average 100 trials? While that may make sense when using the "pseudo-random sequence", wouldn't the Sobol sequence perform better using 10,000 points instead of the average of 100 trials each using 100 points? And if you DO average 100 trials using the Sobol sequence, where do you start the sequence for the second trial? Do you start over at the beginning (makes no sense to average then) or do you start where you left off in the sequence (doesn't make sense if Figure 7.7.1 is correct - for example using 512 points, the second iteration would look like the 3rd panel... very spotty!)?

Thanks for your help!

Edo
01-14-2004, 08:04 PM
Figure 7.7.1 appears to be plots of the 2nd vs. the 3rd sequences (ie. generate a 3d Sobol sequence and plot the 2nd vs the 3rd dimensions).

The discrepancies I claimed to see between the 4 plots appears to be a graphical problem in the layout of the book. Once I plotted the points generated as above, it was obvious that the plots matched those in the figure.

So, to answer my own question, the sequence I offered and the plots BOTH seem to be correct. My sequence being the first two dimensions and the plots being the next two. This leads to two comments I would make about the Sobol sequence.
1) There are a number of variations out there.
The one presented in ACM Transactions on Mathematical Software (TOMS) VOL. 29, NO. 1, P.49-57

http://portal.acm.org/citation.cfm?id=641876.641879&dl=GUIDE&dl=ACM&idx=J782&part=periodical&WantType=periodical&title=ACM%20Transactions%20on%20Mathematical%20Sof tware%20

- Source code at:
http://www.netlib.no/netlib/toms/659

includes an extra sequence to begin with, then the next three match the first three from NRinC and then the next several differ! It appears to come down to different primitive polynomials being used from the onset.

2) The "gap-iness" of Figure 7.7.1 is just a hint of the problem of Sobol being used in large dimensions. Try plotting the first 4096 points of dimensions 27 vs. 28 (can't be done with the NRinC code which only goes to 6 dimensions.)
See p. 36 of:
http://citeseer.nj.nec.com/rd/54517387%2C161781%2C1%2C0.25%2CDownload/http://citeseer.nj.nec.com/cache/papers/cs/4246/ftp:zSzzSzftp.math.ucla.eduzSzpubzSzcaflischzSzdis crepancy.pdf/morokoff94quasirandom.pdf