COMP1927 - Randomness

preemptive tl;dr:

srand = time(NULL);
 
double randNumBetweenZeroAndOne () {
   return (double) random()/(RAND_MAX + 1);
}
 
int randomNumber = randNumBetweenZeroAndOne() * 1000;

Randomness is important for practical applications like random game movements, gambling, security encryption or for data testing, where if not every point is tested with equal randomness then crucial flaws may be missed.

Computers only produce pseudo random numbers, rather than true randomness.

Briefly, this means that they are predetermined and have a cycle period where they start to repeat themselves. They are often calculated with a mathematical formula, rather than true randomness generators which use mouse movements or background noise as their seeds.

Within PRNG (Pseudo Random Number Generators), the Linear Congruential Generator is a common method. It uses a recurrence relation.

Linear Congruential Generator

  • Xn+1 = (aXn + c) mod m where:
    • m is the "modulus"
    • a, 0<a<m is the "multiplier"
    • c, 0<=c<m is the "increment"
    • X0 is the "seed"
  • if c=0 it is called a multiplicative congruential generator

The cycle length (i.e. how long before it starts looping) is very short, which is an issue as it’s unpredictable and the numbers tend to correlate.

Computing Pi – Monte Carlo

Complexity?action=AttachFile&do=get&target=pi.png

Area of the circle = pi, Area of quadrant = pi/4, Area of square = 1

If we generate N points (with an x random and a y random, between o and 1) then all of them will lie in the square, but only M of them will lie in the circle. Where M is determined as the ones where x2 + y2 <= 1.

From this we can get that (Pi/4)/1 = M/N, or in otherwords,

Pi = 4M/N

Computing Pi - Classical Grid Method

Complexity?action=AttachFile&do=get&target=grid.png

We can compute pi by splitting the square into x grid cells and checking if each of those fits the x2 + y2 <= 1 pattern, rather than generating random numbers.

Reasons to Pick Monte Carlo

  1. Grids do not scale well as the dimension increases - many variable problems where you have many dimensional grids get complicated, and slow.
  2. Dimensionality doesn't play a role in Monte Carlo: the error goes something like 1/sqrt(N), which is independent of the number of dimensions
  3. It is difficult to program the grid technique incrementally; in Monte Carlo, you can keep adding random points to increase accuracy, in the grid technique, you need to re-divide the multi-dimensional space and start again
  4. The dynamic error behaviour is subtly different. Dupire & Savine (1998) state: the "regular grid generates small errors that add up, whereas random sampling generates big errors that cancel on average"