.\" Automatically generated by Pod::Man 4.09 (Pod::Simple 3.35)
.\"
.\" Standard preamble:
.\" ========================================================================
.de Sp \" Vertical space (when we can't use .PP)
.if t .sp .5v
.if n .sp
..
.de Vb \" Begin verbatim text
.ft CW
.nf
.ne \\$1
..
.de Ve \" End verbatim text
.ft R
.fi
..
.\" Set up some character translations and predefined strings.  \*(-- will
.\" give an unbreakable dash, \*(PI will give pi, \*(L" will give a left
.\" double quote, and \*(R" will give a right double quote.  \*(C+ will
.\" give a nicer C++.  Capital omega is used to do unbreakable dashes and
.\" therefore won't be available.  \*(C` and \*(C' expand to `' in nroff,
.\" nothing in troff, for use with C<>.
.tr \(*W-
.ds C+ C\v'-.1v'\h'-1p'\s-2+\h'-1p'+\s0\v'.1v'\h'-1p'
.ie n \{\
.    ds -- \(*W-
.    ds PI pi
.    if (\n(.H=4u)&(1m=24u) .ds -- \(*W\h'-12u'\(*W\h'-12u'-\" diablo 10 pitch
.    if (\n(.H=4u)&(1m=20u) .ds -- \(*W\h'-12u'\(*W\h'-8u'-\"  diablo 12 pitch
.    ds L" ""
.    ds R" ""
.    ds C` ""
.    ds C' ""
'br\}
.el\{\
.    ds -- \|\(em\|
.    ds PI \(*p
.    ds L" ``
.    ds R" ''
.    ds C`
.    ds C'
'br\}
.\"
.\" Escape single quotes in literal strings from groff's Unicode transform.
.ie \n(.g .ds Aq \(aq
.el       .ds Aq '
.\"
.\" If the F register is >0, we'll generate index entries on stderr for
.\" titles (.TH), headers (.SH), subsections (.SS), items (.Ip), and index
.\" entries marked with X<> in POD.  Of course, you'll have to process the
.\" output yourself in some meaningful fashion.
.\"
.\" Avoid warning from groff about undefined register 'F'.
.de IX
..
.if !\nF .nr F 0
.if \nF>0 \{\
.    de IX
.    tm Index:\\$1\t\\n%\t"\\$2"
..
.    if !\nF==2 \{\
.        nr % 0
.        nr F 2
.    \}
.\}
.\" ========================================================================
.\"
.IX Title "Statistics::Test::Sequence 3pm"
.TH Statistics::Test::Sequence 3pm "2017-10-19" "perl v5.26.0" "User Contributed Perl Documentation"
.\" For nroff, turn off justification.  Always turn off hyphenation; it makes
.\" way too many mistakes in technical documents.
.if n .ad l
.nh
.SH "NAME"
Statistics::Test::Sequence \- Sequence correlation test for random numbers
.SH "SYNOPSIS"
.IX Header "SYNOPSIS"
.Vb 3
\&  use Statistics::Test::Sequence;
\&  my $tester = Statistics::Test::Sequence\->new();
\&  $tester\->set_data( [map {rand()} 1..1000000] );
\&  
\&  my ($metric, $actual_freq, $expected_freq) = $tester\->test();
\&  use Data::Dumper;
\&  print "$metric\en";
\&  print "Frequencies:\en";
\&  print Dumper $actual_freq;
\&  print "Expected frequencies:\en";
\&  print Dumper $expected_freq;
.Ve
.SH "DESCRIPTION"
.IX Header "DESCRIPTION"
This module implements a sequence correlation test for random number
generators. It shows pairwise correlation between subsequent
random numbers.
.PP
The algorithm is as follows: (Following Blobel. Citation in \s-1SEE ALSO\s0 section.)
.IP "\(bu" 2
Given \f(CW\*(C`N+1\*(C'\fR random numbers \f(CW\*(C`u_j\*(C'\fR.
.IP "\(bu" 2
For all \f(CW\*(C`j\*(C'\fR, compare \f(CW\*(C`u_j\*(C'\fR with \f(CW\*(C`u_j+1\*(C'\fR. If \f(CW\*(C`u_j\*(C'\fR is greater
then \f(CW\*(C`u_j+1\*(C'\fR, assign a 0\-Bit to the number. Otherwise, assign a
1\-Bit.
.IP "\(bu" 2
Find all sequences of equal Bits. For every sequence, increment
a counter for the length \f(CW\*(C`k\*(C'\fR of that sequence. (Regardless of whether it's
a sequence of 1's or 0's.)
.IP "\(bu" 2
For uncorrelated random numbers, the number of sequences \f(CWN(k)\fR
of length \f(CW\*(C`k\*(C'\fR in the set of \f(CW\*(C`N+1\*(C'\fR random numbers is expected to be:
.Sp
.Vb 1
\&  N(k) = 2*((k^2+3*k+1)*N \- (k^3+3*k^2\-k\-4)) / (k+3)!
.Ve
.SH "METHODS"
.IX Header "METHODS"
.SS "new"
.IX Subsection "new"
Creates a new random number tester.
.SS "set_data"
.IX Subsection "set_data"
Sets the random numbers to operate on. First argument
must be either an array reference to an array of random
numbers or a code reference.
.PP
If the first argument is a code reference, the second
argument must be an integer \f(CW\*(C`n\*(C'\fR. The code reference is
called \f(CW\*(C`n\*(C'\fR\-times and its return values are used as
random numbers.
.PP
The code reference semantics are particularily useful if
you do not want to store all random numbers in memory at
the same time. You can write a subroutine that, for example,
generates and returns batches of 100 random numbers so no
more than 101 of these numbers will be in memory at the
same time. Note that if you return 100 numbers at once and
pass in \f(CW\*(C`n=50\*(C'\fR, you will have a sequence of 5000 random
numbers.
.SS "test"
.IX Subsection "test"
Runs the sequence test on the data that was previously set using
\&\f(CW\*(C`set_data\*(C'\fR.
.PP
Returns three items: The first is the root mean square of the bin
residuals divided by the number of random numbers. It \fIcould\fR be
used as a measure for the quality of the random number generator
and should be as close to zero as possible. A better metric is to
compare the following two return values.
.PP
The second return value is a reference to the array of frequencies.
An example is in order here. Generating one million random numbers,
I get:
.PP
.Vb 1
\&  [0, 416765, 181078, 56318, 11486, 1056, 150]
.Ve
.PP
This means there were no sequences of length 0 (obvious), 416765
sequences of length 1, etc. There were no sequences of length 7 or
greater. This example is a bad random number generator! (It's a
linear congruent generator with \f(CW\*(C`(a*x_i+c)%m\*(C'\fR and \f(CW\*(C`a=421\*(C'\fR,
\&\f(CW\*(C`c=64773\*(C'\fR, \f(CW\*(C`m=259200\*(C'\fR, and \f(CW\*(C`x_0=4711\*(C'\fR).
.PP
The third return value is similar in nature to the second in that it
is a reference to an array containing sequence length frequencies.
This one, however, contains the frequencies that would be expected for
the given number of random numbers, were they uncorrelated.
The number of bins has the maximum
length of an occurring sequence as an upper limit. In the given example,
you would get: (Dumped with Data::Dumper)
.PP
.Vb 10
\&  $VAR1 = [
\&            \*(Aq0\*(Aq,
\&            \*(Aq416666.75\*(Aq,
\&            \*(Aq183333.1\*(Aq,
\&            \*(Aq52777.64722222222222222222222222222222222\*(Aq,
\&            \*(Aq11507.89523809523809523809523809523809524\*(Aq,
\&            \*(Aq2033.72068452380952380952380952380952381\*(Aq,
\&            \*(Aq303.1287808641975308641975308641975308642\*(Aq,
\&            # ...
\&          ];
.Ve
.PP
Note that where I put in a \f(CW\*(C`# ...\*(C'\fR, you would really see a couple
more lines of numbers until the numbers go below an expected
frequency of \f(CW0.1\fR.
For \f(CW\*(C`n=1000000\*(C'\fR and \f(CW\*(C`k=7\*(C'\fR, you get about
39 sequences, \f(CW\*(C`k=8\*(C'\fR is expected to be found 4\-5 times, etc.
.SH "SUBROUTINES"
.IX Header "SUBROUTINES"
.SS "expected_frequency"
.IX Subsection "expected_frequency"
Returns the expected frequency of the sequence length \f(CW\*(C`k\*(C'\fR
in a set of \f(CW\*(C`n\*(C'\fR random numbers assuming uncorrelated random
numbers.
.PP
Returns this as a Math::BigFloat.
.PP
Expects \f(CW\*(C`k\*(C'\fR and \f(CW\*(C`n\*(C'\fR as arguments.
.PP
This subroutine is memoized. (See Memoize.)
.SS "faculty"
.IX Subsection "faculty"
Computes the factulty of the first argument recursively as a
Math::BigFloat. This subroutine is memoized. (See Memoize.)
.SH "SEE ALSO"
.IX Header "SEE ALSO"
Math::BigFloat, Memoize, Params::Util
.PP
Random number generators:
Math::Random::MT, Math::Random, Math::Random::OO,
Math::TrulyRandom, \f(CW\*(C`/dev/random\*(C'\fR where available
.PP
The algorithm was taken from: (German)
.PP
Blobel, V., and Lohrmann, E. \fIStatistische und numerische Methoden
der Datenanalyse\fR. Stuttgart, Leipzig: Teubner, 1998
.SH "AUTHOR"
.IX Header "AUTHOR"
Steffen Mueller, <smueller@cpan.org>
.SH "COPYRIGHT AND LICENSE"
.IX Header "COPYRIGHT AND LICENSE"
Copyright (C) 2007 by Steffen Mueller
.PP
This library is free software; you can redistribute it and/or modify
it under the same terms as Perl itself, either Perl version 5.6 or,
at your option, any later version of Perl 5 you may have available.