daniel shiffman

Examples

 

simple probability

multiple event probability

graphing the bell curve (feel free to ignore)

simple gaussian

multiple gaussian

 

monte carlo method

1D perlin noise

2D perlin noise

3D perlin noise

random walk

Reading

Random Walk Resources:

Probability Basics

Single Event Probability: Given a system with a certain number of possible outcomes, the probability of any given event occuring is the number of outcomes which qualify as that event divided by total number of possible outcomes. The simplest example is a coin toss. There are a total of 2 possible states (heads or tails). There is only one way to flip heads, therefore the probability of flipping heads is one divided by two, i.e. 1/2 or 50%.

Consider a deck of 52 cards. The probability of drawing an ace from that deck is:
number of aces / number of cards = 4 / 52 = 0.077 = ~ 8%

The probability of drawing a diamond is:
number of diamonds / number of cards = 13 / 52 = 0.25 = 25%

Sequence of events probability:

The probability of a sequence of events occuring is the product of the individual probabilities of each event.

The probability of drawing 2 aces from a deck is:
First card –> 4 / 52 (4 cards out of 52 as above)
Second card –> 3 / 51 (assuming we already drew one ace, there are only 3 left out of 51 cards left)
(4 / 52) * (3 / 51) = 0.00452 = 0.45%

The probability of drawing a 5 card flush is:
(52 / 52) * (12 / 51) * (11 / 50) * (10 / 49) * (9 / 48) = 0.00198 = ~0.2%
(note the first probability is 1 since by definition, every card that can be drawn has a suit)

What is the probability of drawing 5 cards without a single pair?

(52 / 52) * (48 / 51) * ( 44 / 50) * (40 / 49) * (36 / 48) = 0.507 = ~ 51%
(for each outcome, we have to count how many total cards are left and how many of those cards will not pair one of the cards previously drawn)

Some Probability Resources

Uniform Distribution of Random Numbers

Processing has a random function that returns a random floating point value within a minimum
and maximum specified by the arguments passed i.e.:

float r = random(0,100);      // random floating points between 0 and 100
int   n = int(random(4,7));   // converting random values to integers

http://processing.org/reference/random_.html
(Note that the random numbers we get here are pseudo-random. We aren’t going to get into a discussion of random number generation here, but if you’re interested check out: http://random.mat.sbg.ac.at/.)

If we ask for a random number over a given time period, we will get a uniform distribution
of all possibilities, e.g.

void draw() {
  float brightness = random(255);
  background(brightness);
}

Non-Uniform Random Number Distribution Using Probabilities

There are many different ways we can produce a non-uniform distributions of random numbers. One simple way would be to fill an array with the appropriate distribution of possibilities, picking one random element from that array each time. Try:

int[] stuff = new int[5];
stuff[0] = 1;
stuff[1] = 1;
stuff[2] = 2;
stuff[3] = 3;
stuff[4] = 3;
int index = int(random(stuff.length));
println(stuff[index]);

This is a terribly inefficient example in many ways, but it’s easy to see how we now have a 40% chance of picking 1, 20% chance of picking 2, and 40% chance of picking 3. Think about how you might extend this code to work with a much larger array with many different possibilities. You might even consider using a java ArrayList, which would allow you to remove elements as you pick them if that were a requirement of your program.

Another strategy for how we can create a likelihood for different events to occur is to ask for a random number (for simplicity, we consider random numbers between 0 and 1) and only allow the event to happen if the random number we pick is within a certain range, i.e.

float prob = 0.10f;     //to store a probability of 10%
float r = random(1);   //get a random floating point value between 0 and 1
if (r < prob) {        //if our random is less than .1
   /*INSTIGATE THE EVENT HERE*/
}

In our applets, we are often tempted to simply map some parameter or variable to a random number (i.e. produce random colors, set random velocities, locations, etc.) producing a uniform distribution of values. However, a more interesting way is to assert control over the probabilities of a set of possible outcomes.

Outcome A — 10% | Outcome B — 60% | Outcome C — 30%

To implement this in code, we pick one random float and check where it falls (between 0 and 0.10 (10%) –> outcome A, between 0.10 and 0.70 (60%) –> B,
and between 0.70 and 1.0 (30%) –> C).

//probabilities for 3 different cases (these need to add up to 100% since something always occurs here!)
float red_prob   = 0.10;              // 10% chance of red color occurring
float green_prob = 0.60 + red_prob;   // 60% chance of green color occuring
float blue_prob  = 0.30 + green_prob; // 30% chance of blue color occuring
float num = random(1);                // pick a random number between 0 and 1
if (num < red_prob) {
  fill(255,0,0,50);
} else if (num < green_prob) {
  fill(0,255,0,50);
} else {
  fill(0,0,255,50);
}
ellipse(random(width),random(height),16,16);

Normal (Gaussian) Distribution

An interesting way of generating random values is to use a “normal” distribution (otherwise known as the Gaussian distribution or Bell Curve.) The probability of any given value x (over an infinite space) occuring is expressed as a function of the mean (’mu’ or ) and variance (standard deviation squared, i.e. sigma squared or ).

Notice that if we pick random numbers from a normal distribution as above, we’ll mostly get values that cluster around the middle (mean) of the curve. How much the values will differ from the mean is the standard deviation.

Fortunately for us, we don’t have to do these calculations in our applets since the Java Random class will produce Gaussian distributions for us. A Random generator object will give us numbers with a default mean of 0 and a standard deviation of 1 (and it’s up to us to scale the values based on what we want.)

java.util.Random

First, we declare and initialize the Random object:

Random generator;
generator = new Random();

Second, we ask for the next gaussian value (mean of 0, standard deviation of 1)

float num = (float) generator.nextGaussian();

Finally, we pick a standard deviation and mean and scale our value appropriately:

float sd = 20;
float mean = 100;
num = ( num  * sd ) + mean;

Try running this code and see what values you get (see examples above for further help).

Custom Distribution with Two Random Numbers

Consider the following scenario where we pick a random number between 0 and 1, the higher the number, the more likely it is to be picked. In other words if x is the random number, we could map the likelihood on the y-axis with y = x. (Using more complex formulas will produce more interesting results.) Our strategy to implement such a scenario is as follows:

Here is the code implementing the above steps:

// An algorithm for picking a random number based on monte carlo method
// Here probability is determined by formula y = x
public float montecarlo() {
  // Have we found one yet
  boolean foundone = false;
  int hack = 0;  // let's count just so we don't get stuck in an infinite loop by accident
  while (!foundone && hack < 10000) {
    // Pick two random numbers
    float r1 = (float) random(1);
    float r2 = (float) random(1);
    float y = r1*r1;  // y = x*x (change for different results)
    // If r2 is valid, we'll use this one
    if (r2 < y) {
      foundone = true;
      return r1;
    }
    hack++;
  }
  // Hack in case we run into a problem (need to improve this)
  return 0;
}

If this seems confusing, consider a situation with only two possible numbers available for step 1: 0.1 and 0.9. If you implement the above steps by hand, you’ll notice that 0.9 will be picked 9 times as often as 0.1.

Perlin Noise (A Smoother Approach)

In our applets, as demonstrated above, we can use a random number generator to produce values with uniform and non-uniform distributions. However, in each of these cases, there is no relationship between a given random and the next random produced in sequence by the generator. Perlin noise (invented in the 1980s by Ken Perlin), however, allows us to produce a naturally ordered (”smooth”) sequence of numbers.

Following are two graphs, one, a graph of Perlin noise over time (the x-axis represents time, note how the curve is smooth) compared to a graph of pure random numbers over time. Click on them to view the applet version and source code.

Perlin noise resources:

Fortunately we don’t have to implement the Perlin noise algorithm ourselves. The calculations are built into processing and we can simply call the “noise” function. The noise function is different from random, however, in that Perlin noise is defined in an infinite n-dimensional space (Processing can compute noise for 1, 2, and 3 dimensions).

Let’s examine 1 dimensional noise first. For any given value x, the noise function will produce a floating point value between 0 and 1.

for (int i = 0; i < 5; i++) {
  float xoff = 0.0;
  float noisevalue = noise(xoff);
  println(noisevalue);
}

If you run the above code, you’ll notice that you get the same noise value for each cycle through the loop (since we are asking for the noise value at the same x coordinate over and over again). Now try:

float xoff = 0.0;
for (int i = 0; i < 5; i++) {
  xoff += 0.01;
  float noisevalue = noise(xoff);
  println(noisevalue);
}

Here with each cycle through the for loop, we increment the x coordinate and a new noise value is returned from the noise function. How we increment affects the character of the noise. Smaller steps produce smoother noise, etc.

Two dimensional noise works in much the same, only, instead of calculating noise along a one dimensional path (such as time), noise is calculated as a function of an x,y coordinate in a two dimensional space. This is easier to understand once you consider what pure randomness looks like in a two dimensional space — if you’re old enough to remember receiving broadcast television via. . .I think they called it an “antenna”? . . .well, then you probably remember that look of “snow.” In digital-speak, that snow is just a random grayscale color at every pixel, we could code it really quickly:

2D “snow” (pure randomness):

loadPixels();
for (int x = 0; x < width; x++) {
  for (int y = 0; y < height; y++) {
    float bright = random(255);
    pixels[x+y*width] = color(bright);
  }
}
updatePixels();

With perlin noise, however, instead of having passing just one argument into the noise function (’xoff’ as above), we’ll have two — ‘xoff’ and ‘yoff’ (note these are just made up variable names, you can call them whatever you want. . .)

2D “clouds” (Perlin Noise):

loadPixels();
float xoff = 0.0; // Start xoff at 0
// For every x,y coordinate in a 2D space, calculate a noise value and produce a brightness value
for (int x = 0; x < width; x++) {
  xoff += increment;   // Increment xoff
  float yoff = 0.0;   // For every xoff, start yoff at 0
  for (int y = 0; y < height; y++) {
    yoff += increment; // Increment yoff
    // Calculate noise and scale by 255
    float bright = noise(xoff,yoff)*255;
    // Set each pixel onscreen to a grayscale value
    pixels[x+y*width] = color(bright);
  }
}
updatePixels();

It should also be noted that Perlin noise produces a gaussian distribution of numbers. Visit Paul Bourke’s site for an excellent explanation of how Perlin noise is generated. The two applets below demonstrate the distribution of numbers generated via Perlin noise vs. Randomness.