S. Denisov MNTF, Uni Augsburg
1 / 18
What for?
I simulate random events and experimental fluctuations, for example radioactive decay and stock market fluctuations;
I approximate the dynamics of systems with many degrees of freedom (e.g. Brownian motion, random walks);
I test the stability of a system with respect to perturbations;
I perform random sampling (f. e., Monte-Carlo simulations).
To perform all that we need a reliable generator of random
numbers that arenot correlatedand uniformly distributed over some interval.
2 / 18
Uniformity Consider a sequence
0,1,1 2,1
4,3 4,1
8,3 8 It is uniform butnot random.
Correlations Consider a sequence
r1,1−r1,r2,1−r2,r3,1−r3, ...
Two set of numbersr1,r2,r3, ...and 1−r1,1−r2,1−r3, ... are completely random when considered separately. They could also be perfectly uniform. But the sequence iscorrelated (think about a one-dimensional random walk governed by this sequence).
3 / 18
The key prerequisite
Mathematically, the probability of a number occurring is described by a distribution functionP(r); where P(r)dr is the probability of findingr in the interval [r,r+dr]. A uniform distribution means that the distribution constant is constant,P(r) =a. The standard random-number generator on computers generates uniform
distributions between 0 and 1.
The standard random-number generator produces numbers in this interval, each with an equal probability yet each independent of the previous number (as we shall see, numbers can also be generated nonuniformly and still be random).
4 / 18
How to produce random numbers
Computers are completely deterministic and so cannot create anything random.
Computer-generated random number sequencesmustcontain correlations and in this way are not truly random. Although it may be a bit of work, if we knowri and its preceding elements, it is always possible to figure outri+1. Therefore, computers generate pseudorandomnumbers.
While more sophisticated generators do a better job at hiding the correlations, experience shows that if you (i) analyze the sequence of computer-generated random numbers or (ii) use these numbers long enough, you will notice correlations.
5 / 18
How to produce random numbers
An alternative to generating random numbers is to read in a table of true random numbers determined by naturally random
processes such as radioactive decay (use a file, but it can be used only once) or to connect the computer to an experimental device that produces & measures random events.
Electrical flicker-noise RN generator (Protego,
Sweden) A RN generators based on photon
emmision by a semiconductor)
6 / 18
A simple algorithm
A linear congruent or multiplicative method to generate a pseudorandom sequence of numbers 0<ri <M−1 over the interval [0;M−1].
It is based on the modulo-operationmod: the reminder of a division. amodn is the remainder (an integer)x of the division of an inetegeraby an integer n,x,n,a∈Z. Another words,
a=nq+x, where 0≤x ≤ |n|.
To start you need three integers,a,c,p and aseed r0. Then do ri = (ari−1+c) mod p =remainder[cri−1+c
p ]
7 / 18
A simple algorithm (continuation)
For example, ifc = 1,a= 4,p = 9, and you start with the seed r0 = 3, you obtain:
r0 = 3 r1 = (4×3 + 1)mod 9 = 13 mod9 = 4 r2 = (4×4 + 1)mod 9 = 17 mod9 = 8 r3 = (4×8 + 1)mod 9 = 33 mod9 = 6 r4−9 = 7,2,0,1,5,3
8 / 18
A simple algorithm (continuation)
We get a sequence of lengthM = 9, after which the entire sequence repeats.
If we want numbers in the range [0,1], we divide the allri’s by p= 9:
0.333, 0.444, 0.889, 0.667, 0.778, 0.222, 0, 0.111, 0.555, 0.333 If random numbers in the range [A,B] are needed, you only need to scale: xi =A+ (B−A)ri, then if
0<ri <1⇒A<xi <B.
9 / 18
A simple algorithm (continuation) Let plot the dependencey=ri+1,x=ri
Left: A plot of successive random numbersy=ri+1,x=ri generated with a “bad”
generator. Right: A plot generated with a simeengly good generator.
10 / 18
A simple algorithm (continuation)
The linear congruent method produces integers in the range [0,M1] and therefore becomes completely correlated if a particular integer comes up a second time (the whole cycle then repeats).
In order to obtain a longer sequence,aand M should be large numbers but not so large thatari−1 overflows. A 32-bit (double floats) generator may useM = 231−1w2×109. If your program uses approximately 2×109 random numbers, you may need to reseedthe sequence during intermediate steps to avoid the cycle repeating.
11 / 18
A simple algorithm (continuation): Another example Takep = 231−1 (it is a ’Mersenneprime’), a= 16807, c = 0, andr0 = 42.
Run it and then plot 3d dependenceri+1,ri,ri−1.
12 / 18
A simple algorithm (continuation): Another example
Sample plotri+1,ri,ri−1of consecutive 105random number
13 / 18
How good is your random generator Possible tests:
I Square test: the plot of two consecutive numbers (ri,ri+1) should be distributed homogeneously. Any sign of lines or clustering means the presence of correlations in the sequence {ri}.
I Cube test: this test is similar to the square test, but this time the plot is three-dimensional with the tuples (ri,ri+1,ri+2).
I Average value: the arithmetic mean of all the numbers in the sequence {ri} should correspond to the analytical mean value. Assume that the numbers ri are rescaled to be in the interval [0,1]. Then the arithmetic mean should be:
¯ r = lim
N→∞
1 N
N
X
i=1
ri = 1 2
14 / 18
How good is your random generator(continuation) Possible tests:
I Fluctuation of the mean value (χ2-test): the distribution around the mean value should behave like a Gaussian distribution.
I Correlation test: Analysis of correlations hri ·ri+di − hri2i for different d.
15 / 18
Example: radiactive decay
The circle shows a sample ofNnuclei, each of which has the same probability 1/λof decaying per unit time. The semi-log plots show the results from several simulations of
the nucleus decaying. Notice how the decay appears exponential (like a straight line) when the number of nuclei is large, but stochastic when there are 100 or fewer nuclei.
16 / 18
Experiment: the decay of beer froth
A. Leike, Demonstration of the exponential decay law using beer froth, Eur. J. Phys. 23 (2002) 21
The height of the froth for different kinds of beer as function of time. Shown are the
data and the best fits 17 / 18
Non-uniform distribution: transformations of random variables Will be added latter. Now turn to the whiteboard!
18 / 18
