in reply to Challenge: Detecting sequences.

Do you really want to know?

  1. Books on the matter: http://random.mat.sbg.ac.at/literature/
  2. Tests for generators: http://www.phy.duke.edu/~rgb/General/dieharder.php
I do not think there is a simple answer...

However, simple generators (unlike the Mersenne Twister) are really deterministic, so if you observe the same number a second time, you know that the sequence now repeats.

Replies are listed 'Best First'.
Re^2: Challenge: Detecting sequences.
by BrowserUk (Patriarch) on May 10, 2013 at 18:23 UTC
    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.
[reply]
[d/l]
[select]

      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]
        SIMPLE RNGs, that I was referring to, are usually working like xi+1 = a*xi+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 M2:

        #! 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]

In Section Seekers of Perl Wisdom