Randomness

Reading

Roberts: Chapter 7 and Chapter 8.

Terminology

Deterministic: actions are completely predictable. Deterministic programs produce identical outputs given identical inputs.
Nondeterministic: actions are not predictable. The same inputs may give very different outputs. Useful when programming games or simulations.
Random numbers: numbers whose values are totally impossible to predict. Any number that can be generated is equally likely to be generated.
Pseudo-random numbers: seemingly random numbers generated by a computer. Since the inner workings of a computer are deterministic, it is not possible to generate truly random numbers. Instead we generate a series of numbers that behave like random numbers from a statistical point of view and are sufficiently difficult to predict that no one bothers.

So far, all our programs and functions have been deterministic: given a particular set of inputs, we knew exactly what outputs would be produced (assuming that there were no bugs).

Why would you want random numbers?

Games: determinism would not necessarily be what you want.
Testing: generate input to test programs.

Today's question:

How do computers perform non-deterministic events?

Pseudo-random generator library function: rand

       int rand(void);

returns a pseudo-random integer in the range [0, RAND_MAX].

The program randtest0 is similar to the one shown in the book and generates some number of random numbers.

Is there a problem with our random number generator?

Seeding a random number generator

Each number output by rand is a function of the last number output by rand.
You need some way to get started.
rand has the same initial value each time you run.
This initial value is called a seed.
You can specify a seed value so that you generate different numbers.

		void srand(unsigned seed);

The type unsigned is the same as unsigned int.
During debugging, most people do not seed the random number generator.
After debugging, most people use the time of day to seed the random number generator.

		#include <time.h>

		srand((unsigned)time((time_t *)0));

How did we know to include time.h?
Why do we cast the result of time to an unsigned?
What is the (time_t *)?

Generating random numbers in a specific range

While the rand function is very handy, having numbers in the range 0 to RAND_MAX is not always useful.

Problem: let's assume that we wanted to simulate tossing a coin.

Solution 1 - otherwise known as "The Bad Solution."

If the number is even, call it heads.
If the number is odd, call it tails.
Why is this bad?
- The pseudo random number generator guarantees that the values are randomly distributed in the range 0 to RAND_MAX.
- It does not make any guarantees about the distribution of even and odd values.
- Some random number generators alternate between even and odd numbers!

Solution 2 - otherwise known as "The Right Solution."

Picture the number line of random values.
We know that the values are randomly distributed along this line, so what we want is to divide the entire region in half.
This leads to the implementation


		typedef enum {HEAD, TAIL} coin_t;

		coin_t
		toss_coin(void)
		{
			if (rand() < RAND_MAX / 2)
				return(HEAD);
			else
				return(TAIL);
		}

Problem 2: simulate the roll of a die.

This time we want to partition the space 6 ways
If we used the same strategy as above, we might use something like the following.

              
		int one_sixth;

		one_sixth = RAND_MAX / 6;

		num = rand();
		if (num < one_sixth)
			return(1);
		else if (num < 2 * one_sixth)
			return(2);
		else if (num < 3 * one_sixth)
			return(3);
		else if (num < 4 * one_sixth)
			return(4);
		else if (num < 5 * one_sixth)
			return(5);
		else
			return(6);

While this would work, it certainly gets clumsy, especially when you want random numbers in some larger range (e.g. 1-52 as in the case of a deck of cards).
What we need is a simple consistent way to generate any range of random numbers.
We will build a set of algorithms up incrementally.

Mapping the output of rand into other ranges and types

The function rand() produces integers in the range 0..RAND_MAX inclusive. For most purposes we have to scale those into some other range, like floating point numbers between 0 and 1, or integers between 1 and N.

First, let's normalize the interval 0..RAND_MAX to the interval [0, 1).

/* returns pseudo-random number on [0,1) */

double randfloat_01(void)    
{
	return ((double) rand() / (RAND_MAX + 1.0));
}

This is called Normalization: scaling the value of rand to a floating point number, d, in the range 0 <= d < 1.

Next let's try to generate floating point numbers in the range [lo, hi).

Scale the range [0,1) to [lo, hi).

Translate the interval from 0 to lo.

/* returns pseudo-random number on [lo,hi) */

double randfloat(double lo, double hi)
{
	return (randfloat_01() * (hi - lo) + lo);
}

Now, let's use these building blocks to generate random integers.

The way that we go from floating point values to integer values is to truncate (remove everything to the right of the decimal point).

However, notice that our randfloat function computes the interval [lo, hi), it never actually generates the value hi. Therefore, if we simply truncated, we would generate random integers in the range (lo, hi - 1).

To fix this, we need to change our scaling step to generate random floats in the range [0, (hi - lo + 1)).

Finally, we truncate the floating point number to yield an integer.


	int rand_int(int low, int high)
	{
		int r, range, random_integer;
		double d;

		r = rand();

		/* 1. Normalize. */ 
		d = (double)r / ((double)RAND_MAX + 1);

		/* 2. Scale. */
		range = high - low + 1;
		d *= range;

		/* 3. Translate & Truncate */
		random_integer = (int)d + low;

		return(random_integer);
	}

The Roberts library has a set of random number generating routines that you may use. However, you should understand what these routines do and how they work. You will need to include "random.h" in order to use them.

Randomize(): seeds the random number generator.
RandomInteger(int low, int high): generates random integers in the range [lo, high].
RandomReal(double low, double high): generates random double precision floating point numbers in the range [lo, high).
RandomChance(double p): generates TRUE with probability p (p should be in the range [0, 1]).

Monte Carlo Methods

Topics:

Using randomness (in real life).
Using randomness (in the computer).

Using Randomness in Real Life

There are also practical applications of randomness. We can use random numbers to approximate real numbers.

When you entered, you should have drawn a number from the box at the entrance.

In the same way that the random number generator guarantees that all values are equally likely and evenly distributed across the line, we have guaranteed that the likelihood of any number between 1 and 300 is equally likely (by using only 300 numbers).

We will use random sampling to estimate the distribution of freshman, sophomores, juniors, seniors, and others attending lecture.

The Basic Idea

Assume that we had only 100 students in the class and that half were freshman and half were seniors. If we asked ten people at random (i.e., randomly distributed through the class) we would expect that half would be freshman and half would be seniors.

The Experiment

I will draw 20 - 30 numbers from my box (I have the numbers 1-300 also).
If I call your number, you tell us what year you are.
We will keep track of how many in each class we get.
After 20-30 random samples, we will calculate what percentage of the random samples were in each class.
Then, we will compare these percentages with the actual percentages.

Class	Tally	Percentage	Real %
Freshman
Sophomores
Juniors
Seniors
Other

The Big Picture

You can use random sampling to estimate the characteristics of a large group.
Sampling must be truly random.
You need a "statistically significant" number of samples (take Stat 110 to figure out what that is).
This technique is called Monte Carlo Simulation.

Using Randomness in the Computer

In the problem set, you will use this technique to help you compute the number of valid 3-letter words in the dictionary. We will use it here in a very simplistic manner to convince you that it really works!

Consider the square whose edges are each 2 units long.
Its area is 4.
Let's use that fact to figure out the area of the triangle.

Although we can probably figure out the area of the triangle more easily, let's use a Monte Carlo technique to compute it.

The Algorithm

Generate random points in the square.
Figure out if each point is in the triangle.
Compute the ratio of the number of points in the triangle to the number of points we try.
Multiply this ratio by the area of the square.

Problem 1: How do we determine if a point is in the triangle?

Problem 2: How do we generate random points in the square?

Problem 3: What is the expression to compute the estimated area?

Caveat: Computer-generated pseudo-random numbers are not to be trusted. They are not really random, they usually have subtle correlations, and they repeat after a short time. Don't rely on off-the-shelf generators for anything that matters!

Other Applications

Generate test cases.
Select pieces to drop in a game (e.g., Tetris).
Select directions for players to move (e.g., Pacman).
Make bad guys appear (e.g., Doom).