Random Numbers

Monte-Carlo method is widely used to solve many problems in science, technology and even in commerce. In science, the only requirement to adopt Monte-Carlo method is – physical system should be described by probability distribution function [PDF]. Once the PDFs are known, Monte-Carlo method can proceed by random sampling of PDFs.  Finally, average of large number of trials is taken as the result. Following elements are required to understand basic Monte-Carlo strategy.

·        Random variables

·        Probability distribution functions

·        Moments of PDFs

·        Standard deviation and variance

Random variables are characterised by a domain which contains all possible values that random variable may take and this domain has a corresponding PDF. Rolling the dice is a best example for generation of random sequence. Before rolling the dice, we can't predict the result exactly. We can only say that the output will be from the domain {1, 2, 3, 4, 5, 6}. Even though the outcome cannot be predicted exactly, we can give the likelihood or probability of particular outcome. In case of dice problem, all members in the domain have equal probability (ie 1/6). If the rolling is repeated large number of times (say n) , then the frequency of occurrence of each member in the domain will be almost same and will be exactly equal if n ® ¥.

Random number generator: Random number generator is a program whose output cannot be predicted even after large number of iterations and uniform deviates are the building blocks of random number generators. Uniform deviates generate random numbers within a specified range (generally between 0 and 1) where any one number in the range is as likely as any other number in the range. It should be noted that computers cannot generate purely random numbers. Numbers generated by any of the standard algorithms are , in reality, pseudo-random numbers. The algorithm used for generation of uniform deviates should have following features:

·        They should produce random numbers with uniform distribution in the specified range

·        Correlation between random numbers should be negligible

·        The period before the same sequence of random numbers is repeated should be as large as possible

·        Algorithm should be fast

Some random number generators:

n_i+1 = c*n_i*(1-n_i)

n_i+1 = (a*n_i+c) mod (m)

n_i+1 = (a*n_i + c*n_i+1-j) mod (m)

In all the algorithms, first number n₀, called seed, should be provided by the user.

rand() function in C uses second algorithm in the above list and values of a, c, m are 1103515245, 12345, 2³² respectively. Here srand(<value>) will provide the seed.

References:

1.          Computational physics – An introduction, Verma, R C, Ahluwalia, P K, Sharma, K C, New Age International (P) Limited, Publishers (2005)

2.          Computational Physics, Richard Fitzpatrick Professor of Physics, University of Texas at Austin

3.          Computational Physics, M. Hjorth – Jensen, Department of Physics, University of Oslo (2003)