Homework 1; due on Thursday, September 19PY 502, Computational Physics (Fall 2013)Department of Physics, Boston UniversityInstructor: Anders SandvikTEST OF A RANDOM NUMBER GENERATOR USING RANDOM WALKSIn this assignment, you will test the quality of a random number generator by using it to simulatea random walk, comparing the exact probability distribution with ones obtained in simulations.Random walkConsider a stochastic process in which at each time step t = 1, . . . , n we can move one step “up”or “down” (x → x ± 1, with probability 1/2 for + and −), starting at t = 0 at x = 0. Threerealizations of such a random walk with n = 100 are shown in Fig. 1.0 20 406080100t-15-10-5051015x(t)Figure 1: Three different realizations of a random walk with n = 100 steps.It is easy to calculate the probability distribution of x after n steps: The total number of walkshaving n+moves up and n−down isN(n+, n−) =n!n+!n−!. (1)The probability for each combination of up and down moves (one random walk) is the same; 1/2n.Since n = n++ n−and x after n steps is n+− n−, we can write the distribution after n steps as;Pn(x) =12nn![(n + x)/2]![(n − x)/2]!. (2)Here it should be noted that if n is even, x must also be even (for a non-zero probability), whereasif n is odd x is also odd.1-40 -20 0 20 40x0.000.020.040.060.08P(x)-40 -20 0 20 40x10-610-510-410-310-210-1Figure 2: Probability distribution of the displacement after a random walk of n = 100 steps, basedon 5 × 105different walks (circles with error bars), compared with the exact distribution (solidcurve) plotted on linear (left) and log (right) scales.Simulated random walkIn a simulation, we use a random number generator to make the decisions of up or down movementat each time step (e.g., we generate a floating point number r between 0 and 1, and move up ordown if r < 1/2 and r ≥ 1/2, respectively). If the random numbers are not perfect, there will bedeviations in the probability distribution from the exact distribution (2).To compute the simulated distribution, we have to repeat simulations many times, using differentsequences of random numbers. Fig. 2 shows the distribution for n = 100 steps, obtained using5 × 105independent simulated random walks with a good random number generator. Here “errorbars” for the simulation results have been computed as discussed below. The comparison with theexact distribution shows no statistically significant deviations, i.e., the results agree to the degreeexpected given the size of the error bars (statistical fluctuations).Expected statistical fluctuationsWe can only perform a finite number of these simulated walks, and therefore we will not obtain theexact distribution (2). We then have to analyze the statistics of the expected deviations from theexact distrubution, to determine whether the observed deviations from (2) are just due to naturalstatistical fluctuations based on a finite sample, or whether they are larger than would be expected(in which case they must be due to flaws in the random number generator used). Let us analyzethe statistical fluctuations theoretically (we will discuss this more completely in later parts of thecourse).Let us estimate what deviations from the exact distribution (2) that should be expected based solelyon a finite number of walks used to estimate the distribution. If we approximate the statistics ofthe final point of the random walk (after n steps) as “counting statistics”, then if we end up withNxwalks at final position x the expected standard deviation would be√Nx. Thus, the expectednumber of “counts” and its standard deviation for x based on a total number Nwof random walks2isCn(x) = NwPn(x) ±pNwPn(x). (3)Let us now divide this by Nw, to get a properly normalized probability, and compute the expecteddeviation from the actual distribution;∆n(x) = Cn(x)/Nw− Pn(x). (4)The expected value of this quantity (for a perfect random number generator) is 0, and from (3) wesee that the expected (standard) deviation is;σn(x) =sPn(x)Nw. (5)We can now compute the total squared deviation (in order to have a sum over positive numberscharacterizing the average deviation) over all final outcomes x, and call it ∆2.∆2=nXx=−n∆2n(x). (6)According to Eq. (5) its expected value should beh∆2i =Xxσ2n(x) =1NwXxPn(x) =1Nw. (7)It is appropriate to take the square root, to get an RMS (root-mean-square) deviation;∆ =sXx∆2n(x) =1√Nw. (8)This expected outcome is not strictly valid, because the stochastic process underlying the prob-ability of ending up at x after n steps is not an independent process for each x (if we get morecounts for some x, we have to get less for all other x). Nevertheless if n is large, so that the numberof x values which the process can reach is large (and hence a fluctuation at one x is not affectingmuch the counts at other x), this should be close enough to reality for the present purpose. We canthen test the random number generator by computing ∆ according to (6) with (4), where Cn(x)is the actual count based on Nwsimulations. According to Eq. (8), for increasing number Nwofsimulated random walks, this number should decay as 1/√Nwif the random number generator isgood. If, on the other hand, the generator is bad, we expect ∆ to approach some non-zero value asNw→ ∞, reflecting a distribution for the “random” walk different from (2). We can also look at√Nw∆, which should approach 1 for a good generator and diverge as ∝√Nwfor a bad generator.3Programming taskThe random number generator you should test here is the 64-bit linear congruential generatordiscussed in class, which uses the algorithmrn+1= a · rn+ c, (9)with a = 2862933555777941757 and c = 1013904243 (remember to include 8 at the end of theseconstants in the program, to make them “long” integers).Normally, when using this kind of random number generator, the integers would be converted intodouble precision floating-point numbers between 0 and 1. Here we will instead test the individualbits of the sequence of integers. The Fortran 90 function btest(r,b) can be used to test (true orfalse) the value of bit b = 0, . . . 31. We can use the value of a given bit b for the x = ±1 decisionin the random walk. We want to check for differences in the randomness among the bits, throughthe quality of random walks based on them.Write a program that tests all the bits in the same run, i.e., perform 64 different random walkssimultaneously, using the 64