\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}