April 1, 2013---Class 23---Shell Scripts for Metropolis Method,
Pseudorandom Numbers Generators, Serial Correlation Tests
Activities:
Shell Scripts for Metropolis Method
-----------------------------------
In ~sg/metropolis you will find some shell and awk scripts that you
can use to go from plotting the autocorrelation as a function of
the lag for fixed delta in the gaussian random walk, to plotting
for fixed lag, the autocorrelation as a function of delta. This is
useful for finding the optimal delta as you are requested to do for
the homework. The way these scripts work was discussed in class.
run.csh can be used to run the metropolis program for a range of delta
makeauto.csh makes the autocorrelations out to a lag of 10
aut_vs_delta.csh uses the awk script aut_vs_delta.a
The scripts have been modified a bit since the class to use a more
consistent notation so that delta is referred to as delta or DELTA.
Properties of Pseudo Random Number Generators
---------------------------------------------
We looked at some properties of Linear Congruential PRNGs.
x_{n+1} = (a x_n + c) mod m
a is the multiplier
c is the increment
m is the modulus.
If c=0, this is a multiplicative generator, otherwise, it is mixed.
We start the sequence with a seed x_0.
m determines the maximum possible length of the sequence. It is
necessary to pick a and c carefully to get the maximum length
sequence.
Here is a theorem: The length of the period is m if the following
three conditions all hold.
a) c is relatively prime to m
b) (a-1) is a multiple of p for every prime factor of m
c) if m is a multiple of 4, (a-1) is a multiple of 4.
We looked at the case, m=32, a=3, c=4. This does not obey the
theorem and there is no sequence longer than 8. There is even a
sequence of length one. So much for randomness! To explore this
generator use the Mathematica definition
myrand[x_] := Mod[ 3x+4, 32]
The NestList command can be used to study a sequence:
seed = 3
NestList[myrand, seed, 32]
Adjusting a and c, we can easily find sequences of length 32;
however, that is not enough to ensure that the sequence looks random.
A Mathematica notebook April1_2013.nb may be found in my home
directory with some of the tests we did, including how to make a
set of random numbers with a triangular probability density.
Serial Correlation Tests
------------------------
In addition to having a uniform probability density, a pseudo random
number generator should have zero autocorrelation. There are tests
based on looking at pairs or triplets of numbers. For linear
congruential random number generators, there is a well known
problem that like the rain in Spain they tend to fall mainly in
the planes. This can be demonstrated by showing a two dimensional
scatter plot of (r_n, r_{n+1}). If you would like to see this, there
is an executable in ~sg/bin called random_lc:
random_lc | axis m 0 | xplot
will show you the correlations. The code is in ~sg/src and this
makes use of a poor linear congruential random number generator. You
would not see the same pattern with the fsr random number generator.
We looked in detail at another test of correlations based on
triplets of numbers. If we divide the interval (0,1) into L bins,
and look at triplets in the resulting L^3 cells, we derived that
the probability of having a cell remain unoccupied is exponentially
falling. Specifially, if we examine the occupancy after tL^3
triplets have been generated, the number of unoccupied cells should
be L^3 Exp[-t]. We will test this in the next class.