Linear Congruential Generators, Bays-Durham Shuffle

[koenigcochran]

Hi!

I've got an idea of how LCGs work. However, I'm reading "Exploring Monte Carlo Methods" and came across the Bays-Durham Shuffle, a means of getting rid of low-order correlations in the minimal standard LCG.

The outline of this algorithm in the book makes no sense to me. Can someone summarize the algorithm?

 

[NemoReally]

Hi!

I've got an idea of how LCGs work. However, I'm reading "Exploring Monte Carlo Methods" and came across the Bays-Durham Shuffle, a means of getting rid of low-order correlations in the minimal standard LCG.

The outline of this algorithm in the book makes no sense to me. Can someone summarize the algorithm?

I don't know if this is any improvement on what you read, but ...

Create the table of length k from an Linear Congruential Generator (LCG). Continue the LCG to create a stream S of length n. Initialize RNG output stream to first element (13 in this case) of S, then repeat following until output stream has n elements ..

• get next number s from S
• form the index j into the table (j = s mod k)
• get jth element of table and add it to the output stream
• replace jth element of table with s

Here's Mathcad-produced list of the a 5-number sequence:


And the algorithm ...

The worksheet is attached (unless it's too big!)

 

[koenigcochran]

Three things

(1) The illustration of the table and output stream were very helpful; thank you so much! I think its the diction that has confused me--I would describe the algorithm with a choice of words totally different from what I've found in literature (probably just a consequence of my background).
(2) Did you use an initial seed 8 and divisor 30 in the image of the table and output stream? I'd like to check my own implementation of the shuffle.
(3) For your name's sake, I hope you've seen "Little Nemo: Adventures in Slumberland." A trippy, childhood favorite.

Thanks again!

 

[koenigcochran]

Also:

Is the final vector of 'random' numbers the appendage of the output stream to the table? Just the table? Just the output stream? Or does it matter?

Thanks Nemo.

 

[koenigcochran]

Disregard that last question, I've answered it for myself. The output stream is of arbitrary length and should be used as the vector of 'random' numbers.

However the question remains: does the length of the table matter? Is there an optimal length?

 

[NemoReally]

Three things

(1) The illustration of the table and output stream were very helpful; thank you so much! I think its the diction that has confused me--I would describe the algorithm with a choice of words totally different from what I've found in literature (probably just a consequence of my background).
(2) Did you use an initial seed 8 and divisor 30 in the image of the table and output stream? I'd like to check my own implementation of the shuffle.

No, I used an initial seed of 9. The '8' is the length of the 'shuffle' table and '30' is the length of the output vector. What you wouldn't have seen without Mathcad is the first half of the worksheet containing the LCG. See attached, the LCG agrees with the sequence given in Gentle.

(3) For your name's sake, I hope you've seen "Little Nemo: Adventures in Slumberland." A trippy, childhood favorite.

Nope, but my children probably have. My name's more to do with the Latin I studied at school.

Thanks again!

No problem.

 

[NemoReally]

I'd like to check my own implementation of the shuffle.

I'm reasonably certain that my LCG implementation is correct (or I've made the same mistake as the original implementation!), however, I'm not so sure about the Bays-Durham algorithm. The initial 3 numbers agree with those given by Gentle, but the plot of successive pairs is completely different. I can see a pattern of sorts in Gentle's plot but mine appears to be far more random, even in the 3D version (it's really interesting to compare the 'before' and 'after' shuffle plots). So, there is a possibility that I'm either plotting the data incorrectly and/or I've made an error in the implementation that doesn't show up until later in the sequence. I've had a brief webtrawl but can't find anything better to check against at the moment.

NR