Reading "Random number generation and Monte Carlo methods" by James E. Gentle, I encountered an example concerning the Bays-Durham Shuffling algorithm whose result I can't reproduce.
Basically, such an example is written in Random Number Generation - Durham Shuffling of Uniform Deviates. For the full text you can go to Random number generation and Monte Carlo methods.
Well, I'm trying to reproduce Figure 1.7 for the linear congruential generator of $x_{i} \equiv 3x_{i-1} \text{mod} 31$. In order to do so, I wrote the following piece of code in Mathematica:
Defines initial variables for the generator:
a = 3; mod = 31; x = 9; n = 0; m = {};
Produce a list with the initial set of numbers (In this case: 27, 19, 26, ... <<27>> ... 1, 3, 9):
While[n < 30, AppendTo[m, Mod[a x, mod]]; x = Mod[a x, mod]; n++];
The algorithm generates the first sequence of numbers in a slightly different way using the input value k, so in order to account for this, I had to use this While for the first sequence:
k = 8; i = 1; y = m[[k + 1]];
While[i == 1, choose = Mod[y, 8] + 1; y = l[[choose]];
Then, for the following sequences:
i = i + 1; m[[choose]] = k; k = k + 2];
While[i < 10000, choose = Mod[y, 8] + 1; y = m[[choose]];
i = i + 1; k++;
Given that the congruence relation is congruence modulo 31, the sequence will repeat itself after 30 digits. To avoid looking for the non-existent element m[[31]], I added the conditional:
If[k < 30, m[[choose]] = m[[k]], k = 1; m[[choose]] = m[[k]]]];
The book says:
'By continuing in this manner to yield 10,000 deviates and plotting the successive pairs, we get Figure 1.7'.
Well, as you can see, the procedure takes places 10,000 times. The output is:
{4, 4, 21, 18, 2, 4, 21, 3, 13, 8, 24, 10, 30, 28, 22, 4, 12, 5, 15, 14, 11, 2, 6, 18, 23, 7, 21, 1, 3, 9}.
Unfortunately, even if some of the points look like the ones in Figure 1.7, obviously those images are not the same. Actually, Figure 1.7 contains 122 points (assuming I didn't miscount), however, given the generator, I don't know how you can produce more than 30 points. Actually, the author writes:
... Remember that there are only 30 different values, however.
Am I missing something? Any ideas?