Re^2: Challenge: Detecting sequences.

However, simple generators (unlike the Mersenne Twister) are really deterministic, so if you observe the same number a second time,

A generator of the integers 0 .. 2, can generate those 3 values in 6 different sequences:

a: 0 1 2
b: 0 2 1
c: 1 0 2
d: 1 2 0
e: 2 0 1
f: 2 1 0
[download]

And those 6 (sub)sequences can be output in 720 permutations before repetition is required:

a b c d e f
a b c d f e
a b c e d f
a b c e f d
a b c f d e
a b c f e d
a b d c e f
a b d c f e
...
f e c d b a
f e d a b c
f e d a c b
f e d b a c
f e d b c a
f e d c a b
f e d c b a
[download]

That's not strictly true, because it is likely that some 18-digit overlaps between two subsequences will replicate an earlier subsequence.

But then, the last 2 digits of subsequence a, and the first digit of subsequence b; form an out-of-sync repetition of subsequence d. and given that MT can only produce 2**32 values; similar, out-of-sync subsequence repetitions have to have occurred many times to arrive at the 2**19937-1 periodicity.

So, repetition of a single value, or even a single subsequence is not an indicator that periodicity has been reached.

With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'

Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.

"Science is about questioning the status quo. Questioning authority".

In the absence of evidence, opinion is indistinguishable from prejudice.

Comment on Re^2: Challenge: Detecting sequences. Select or Download Code

Replies are listed 'Best First'.
Re^3: Challenge: Detecting sequences. by hdb (Monsignor) on May 10, 2013 at 20:28 UTC
SIMPLE RNGs, that I was referring to, are usually working like `x[i+1] = a*x[i]+b mod m`, with suitable a, b, and m, which cause the sequence to repeat, once a number repeats.	[reply] [d/l]
Re^4: Challenge: Detecting sequences. by BrowserUk (Patriarch) on May 11, 2013 at 02:17 UTC
SIMPLE RNGs, that I was referring to, are usually working like xi+1 = axi+b mod m,* LCGs are far from the only "simple [P]RNGs"; see also ICGs (CIGs) for another class of simple PRNG with some interesting properties, but the same max.period == mod(M) limitation. But there are other, even simpler (addition/subtraction/mod only) classes that do not. Eg. this 8-bit generator (thus M=256) displays near perfect randomness by a variety of measures, but has a periodicity of nearly M²: #! perl -slw use strict; use 5.010; use Data::Dump qw[ pp ]; $Data::Dump::WIDTH = 2000; use constant { BIGPRIME => 251, SMALLPRIME => 241, }; sub x{ state $r = BIGPRIME; state $t = 0; $r += (++$t % SMALLPRIME) == 0 ? BIGPRIME : - SMALLPRIME; $r %= 256; } my @freqs; my $bytes = ''; for( 1 .. 1e6 ) { my $r = x(); $bytes .= chr( $r ); ++$freqs[ $_ ][ $r & ( 2*$_ -1 ) ] for 0 .. 8; } pp \@freqs; print STDERR 'Ones: ', unpack '%32b', $bytes; my $first256 = substr $bytes, 0, 256; if( my $p = 1 + index $bytes, $first256, 1 ) { print STDERR "The first sequence is repeated at position $p"; } __END__ C:\test>primesQ >log [ [1000000], [500000, 500000], [250000, 250000, 250000, 250000], [125000, 125001, 125000, 124999, 125000, 124999, 125000, 125001], [62500, 62501, 62500, 62499, 62499, 62499, 62500, 62501, 62500, 6250 +0, 62500, 62500, 62501, 62500, 62500, 62500], [31251, 31250, 31251, 31249, 31250, 31249, 31250, 31250, 31250, 3125 +0, 31250, 31251, 31250, 31251, 31249, 31251, 31249, 31251, 31249, 312 +50, 31249, 31250, 31250, 31251, 31250, 31250, 31250, 31249, 31251, 31 +249, 31251, 31249], [15625, 15626, 15626, 15623, 15625, 15626, 15625, 15624, 15626, 1562 +6, 15624, 15625, 15626, 15626, 15623, 15625, 15626, 15626, 15623, 156 +25, 15626, 15625, 15624, 15626, 15626, 15624, 15624, 15626, 15626, 15 +623, 15625, 15626, 15626, 15624, 15625, 15626, 15625, 15623, 15625, 1 +5626, 15624, 15624, 15626, 15626, 15624, 15625, 15626, 15626, 15623, +15625, 15626, 15625, 15623, 15625, 15626, 15625, 15624, 15626, 15626, + 15623, 15625, 15626, 15626, 15623], [7814, 7813, 7811, 7812, 7815, 7812, 7811, 7813, 7814, 7811, 7812, 7 +815, 7813, 7811, 7812, 7814, 7812, 7812, 7813, 7814, 7811, 7812, 7814 +, 7813, 7811, 7813, 7814, 7812, 7812, 7813, 7813, 7811, 7813, 7814, 7 +813, 7811, 7813, 7813, 7811, 7812, 7814, 7813, 7811, 7813, 7814, 7812 +, 7811, 7814, 7813, 7812, 7812, 7814, 7812, 7810, 7813, 7815, 7812, 7 +811, 7814, 7813, 7811, 7812, 7815, 7812, 7811, 7813, 7815, 7811, 7810 +, 7814, 7814, 7811, 7812, 7815, 7812, 7810, 7813, 7815, 7811, 7811, 7 +814, 7814, 7810, 7811, 7815, 7813, 7810, 7813, 7815, 7811, 7810, 7814 +, 7814, 7810, 7812, 7815, 7813, 7810, 7812, 7815, 7812, 7810, 7814, 7 +814, 7810, 7811, 7815, 7813, 7810, 7813, 7815, 7812, 7810, 7813, 7814 +, 7811, 7811, 7815, 7813, 7810, 7812, 7815, 7812, 7810, 7814, 7814, 7 +811, 7811], [3907, 3907, 3906, 3907, 3908, 3907, 3906, 3906, 3907, 3905, 3905, 3 +907, 3906, 3905, 3906, 3907, 3907, 3907, 3907, 3908, 3906, 3906, 3907 +, 3906, 3905, 3906, 3906, 3906, 3906, 3906, 3907, 3906, 3907, 3908, 3 +907, 3906, 3907, 3906, 3906, 3906, 3906, 3906, 3905, 3906, 3907, 3906 +, 3906, 3908, 3907, 3907, 3907, 3907, 3906, 3905, 3906, 3907, 3905, 3 +905, 3907, 3906, 3906, 3907, 3908, 3907, 3906, 3907, 3908, 3905, 3905 +, 3907, 3906, 3905, 3906, 3907, 3906, 3905, 3907, 3908, 3906, 3906, 3 +908, 3907, 3905, 3906, 3907, 3906, 3904, 3906, 3907, 3905, 3905, 3908 +, 3907, 3906, 3907, 3908, 3907, 3905, 3906, 3907, 3905, 3904, 3907, 3 +906, 3905, 3906, 3908, 3907, 3906, 3907, 3908, 3906, 3905, 3907, 3906 +, 3905, 3905, 3907, 3906, 3905, 3906, 3908, 3906, 3906, 3908, 3907, 3 +906, 3906, 3907, 3906, 3905, 3905, 3907, 3905, 3905, 3907, 3907, 3906 +, 3907, 3908, 3907, 3906, 3906, 3907, 3905, 3905, 3906, 3906, 3905, 3 +906, 3907, 3907, 3906, 3907, 3908, 3906, 3906, 3907, 3906, 3905, 3906 +, 3906, 3906, 3905, 3906, 3907, 3 905, 3906, 3908, 3907, 3906, 3907, 3907, 3906, 3905, 3906, 3906, 3905, + 3905, 3907, 3906, 3905, 3907, 3908, 3907, 3906, 3907, 3907, 3905, 39 +05, 3907, 3905, 3905, 3906, 3907, 3906, 3905, 3907, 3908, 3906, 3906, + 3908, 3906, 3905, 3906, 3907, 3905, 3905, 3906, 3907, 3905, 3905, 39 +08, 3907, 3906, 3907, 3908, 3906, 3905, 3906, 3907, 3904, 3905, 3907, + 3906, 3905, 3906, 3908, 3907, 3906, 3907, 3908, 3905, 3905, 3907, 39 +06, 3904, 3906, 3907, 3906, 3905, 3906, 3908, 3906, 3906, 3908, 3907, + 3905, 3906, 3907, 3906, 3904, 3906, 3907, 3905, 3905], ] Ones: 3999980 The first sequence is repeated at position 61697 [download] With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday' Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error. "Science is about questioning the status quo. Questioning authority". In the absence of evidence, opinion is indistinguishable from prejudice.	[reply] [d/l]