Re: the -other- shuffling question

I personally have not heard of this approach to "extending" random number generators. However, it is possible that this extension is not used because it is unclear whether or not many of the "randomness" properties hold using this extension.

For example, is the resulting sequence "well-distributed"? In the case of the transformed $M=8 sequence, it is. Are consecutive pairs of the resulting sequence well-distributed? In the case of the same sequence, no they are not (for example, two identical consecutive digits is 20% less likely than it should be). In this particular case, this is perhaps expected, because the original sequence didn't have this property. But in general, if we take a sequence that has some "good randomness property", will the transformed sequence have the property too? In short, period length isn't always the only thing to consider.

Comment on Re: the -other- shuffling question Download Code

Replies are listed 'Best First'.
Re^2: the -other- shuffling question by mstone (Deacon) on Jun 13, 2005 at 04:39 UTC
As I understand it, shuffling doesn't decrease any desirable qualities. It only leaves them unchanged or increases them. It's vaguely like a sorting algorithm that preserves existing order.. sorting on B then sorting on A gives you a sequence sorted with A as the major key and B as the minor key. In this case, shuffling took a sequence that had no consecutive doubles and introduced a few. If there are weaknesses, I'd like to know about those, too. I've found that some values for array size perform very badly (@T=7 leads to a period of 424, despite being relatively prime to $M), and adding a second shuffle doesn't seem to do much of anything. And clocking the generator: `$M = 8; $A = 5; $X = 0; $C = 0; sub lcrng { $X = (($X * $A) + 1) % $M; $C++; if ($C = $M-1) { $C = 0; $X = lcrng(); } return ($X); }` [download] frankly sucks. This all follows Knuth's admonition that RNGs are delicate creatures, and tend to be sensitive to 'minor' adjustments. I'd like to learn the theory behind these things so I know what's safe to touch.	[reply] [d/l]

Replies are listed 'Best First'.

Re^2: the -other- shuffling question
by mstone (Deacon) on Jun 13, 2005 at 04:39 UTC

As I understand it, shuffling doesn't decrease any desirable qualities. It only leaves them unchanged or increases them. It's vaguely like a sorting algorithm that preserves existing order.. sorting on B then sorting on A gives you a sequence sorted with A as the major key and B as the minor key. In this case, shuffling took a sequence that had no consecutive doubles and introduced a few.

If there are weaknesses, I'd like to know about those, too. I've found that some values for array size perform very badly (@T=7 leads to a period of 424, despite being relatively prime to $M), and adding a second shuffle doesn't seem to do much of anything. And clocking the generator:

    $M = 8;
    $A = 5;
    $X = 0;
    $C = 0;
    
    sub lcrng {
        $X = (($X * $A) + 1) % $M;
        
        $C++;
        if ($C = $M-1) {
            $C = 0;
            $X = lcrng();
        }
        return ($X);
    }
[download]

frankly sucks.

This all follows Knuth's admonition that RNGs are delicate creatures, and tend to be sensitive to 'minor' adjustments. I'd like to learn the theory behind these things so I know what's safe to touch.

[reply]
[d/l]