\documentstyle[med_headings]{article}
\oddsidemargin=0in\textwidth=6in\topmargin=-0.80in\textheight=10in
\renewcommand{\textfraction}{0.01}
\pagestyle{empty}\begin{document}\title{}\author{David J.C. MacKay }\date{}
\begin{center}
{\large \bf
Computational Methods in Physics
\\ \medskip
}
\end{center}
\section*{Random walks and random number generators}
Random number generators are often used in simulations of physical
systems. But some random number generators are
not good at making `random' sequences. This example is a cautionary tale
using the generator {\tt ran1} that is recommended in the first
edition of `Numerical Recipes' by Press {\em et al}. [This generator
does not appear in the second edition!]\\[2in]
\subsection*{Random walk}
Write a program that generates a one-dimensional
random walk by adding up random numbers
uniformly distributed between $-1/2$ and $1/2$.
The program should be
modular so that any generator can be plugged in.
How many
samples do you expect need to be added up to get a sum whose
distribution is practically indistinguishable from a Gaussian distribution?
What is the expected
squared distance $S$ as a function of the number of steps $t$?
Average the squared distances $S(t)$
of a number of random walks of length about $12,000$ steps
and plot the average. Does it agree with what we expect for true random
numbers?
Try some other NAG random number generators, and the system's
standard generator, and see if they have similar problems.
\subsection*{Correlations}
Take a `quick and dirty' linear congruential generator
\begin{quote}
{\tt
jran=mod(jran*ia+ic,im) \\
ran=float(jran)/float(im)
}
\end{quote}
where ({\tt im},{\tt ia},{\tt ic}) can take values that include
(14406, 967, 3041), (139968, 3877, 29573), and (714025, 1366, 150889).
Larger values of {\tt im} give
generators with a longer period which should have better properties.
Study the correlation
between two successive random numbers between 0 and 1 (in a scatter plot,
for example).
Can you see any significant
correlations? Test any of your hypotheses about correlations
by generating more random numbers.
There are in fact correlations (and for this reason
good generators `shuffle' the random numbers before spitting them out).
Hint: look at very small numbers and the
numbers that follow them.
The second cautionary tale about random number generators may be that
humans are not good at perceiving randomness. Many people tend to perceive
that structure is present when it is not.
\medskip
\hfill DJCM \today
\end{document}