Chance operations & probability theory

From GenerativeArt

(Difference between revisions)
Jump to: navigation, search
(→Pragmatic notes on using random numbers in art)
Current revision (04:15, 21 November 2012) (view source)
(fix image urls)
 
In this example a ball is dropped on the top pin of a triangular arrangement of pins. The ball ends up exiting in one of several columns. The probability that a ball will end up in a given column is a function of the number of paths that lead to that column.
In this example a ball is dropped on the top pin of a triangular arrangement of pins. The ball ends up exiting in one of several columns. The probability that a ball will end up in a given column is a function of the number of paths that lead to that column.
 +
 +
{{SingleImage|imageWidthPlusTen=655|imageURL=http://www.viz.tamu.edu/courses/viza658/wiki/prob/00.jpg|caption=Pinball Example}}
 +
 +
[[http://philipgalanter.com/howdy/applets/ballDistribution/index.html Click here to run a pinball demonstration applet.]]
<SPAN STYLE="font-size: larger;"><u>Pascal's Triangle</u></span>
<SPAN STYLE="font-size: larger;"><u>Pascal's Triangle</u></span>
-
{{SingleImage|imageWidthPlusTen=594|imageURL=http://www-viz.tamu.edu/courses/viza658/wiki/prob/01.jpg|caption=Gaussian Distribution}}
+
{{SingleImage|imageWidthPlusTen=594|imageURL=http://www.viz.tamu.edu/courses/viza658/wiki/prob/01.jpg|caption=Gaussian Distribution}}
-
{{SingleImage|imageWidthPlusTen=730|imageURL=http://www-viz.tamu.edu/courses/viza658/wiki/prob/02.jpg|caption=Faces generated with psuedo-random numbers}}
+
{{SingleImage|imageWidthPlusTen=612|imageURL=http://www.viz.tamu.edu/courses/viza658/wiki/prob/02.jpg|caption=Faces generated with psuedo-random numbers}}
-
{{SingleImage|imageWidthPlusTen=730|imageURL=http://www-viz.tamu.edu/courses/viza658/wiki/prob/03.jpg|caption=Faces generated with Gaussian Distribution}}
+
{{SingleImage|imageWidthPlusTen=612|imageURL=http://www.viz.tamu.edu/courses/viza658/wiki/prob/03.jpg|caption=Faces generated with Gaussian Distribution}}
 +
 +
[http://www.viz.tamu.edu/courses/viza658/wiki/prob/facedist.swf View Flash Application demonstrating the Normal Distribution vs Random Distribution]
In this example the intent is to suggest a large circle by populating a 1 unit radius with small circles. Using the programming environment Matlab pairs of random numbers from -1 to 1 ar generated and then tested. Those with a distance from the center (0,0) greater than 1 are rejected. The remaining (x,y) pairs are plotted as small blue circles.
In this example the intent is to suggest a large circle by populating a 1 unit radius with small circles. Using the programming environment Matlab pairs of random numbers from -1 to 1 ar generated and then tested. Those with a distance from the center (0,0) greater than 1 are rejected. The remaining (x,y) pairs are plotted as small blue circles.
-
While a large circle is formed, the smaller circles tend to clump up
 
-
as is typical when using small quantities of random numbers.
 
-
x
 
 +
{{SingleImage|imageWidthPlusTen=594|imageURL=http://www.viz.tamu.edu/courses/viza658/wiki/prob/04.jpg|caption=While a large circle is formed, the smaller circles tend to clump up as is typical when using small quantities of random numbers.}}
-
Here are the same points adjusted via software to reduce clumping.
 
 +
{{SingleImage|imageWidthPlusTen=594|imageURL=http://www.viz.tamu.edu/courses/viza658/wiki/prob/05.jpg|caption=Here are the same points adjusted via software to reduce clumping.}}
-
x
 
-
The de-clumping algorithm works by first analyzing each center point and finding the nearest neighbors.
 
 +
{{SingleImage|imageWidthPlusTen=594|imageURL=http://www.viz.tamu.edu/courses/viza658/wiki/prob/06.jpg|caption=The de-clumping algorithm works by first analyzing each center point and finding the nearest neighbors.}}
-
x
+
 
-
The distances between nearest neighbors are then iteratively adjusted. Points that
+
The distances between nearest neighbors are then iteratively adjusted. Points that are "too close" are moved a bit apart, and others "too far apart" are moved closer together. This is repeated a number of times until a balance is achieved. Note the flaws and irregularities that make the image more interesting than the result of a
-
are "too close" are moved a bit apart, and others "too far apart" are moved closer together.
+
-
This is repeated a number of times until a balance is achieved. Note the flaws
+
-
and irregularities that make the image more interesting than the result of a
+
tiling algorithm which would enforce strict symmetries and measurements.
tiling algorithm which would enforce strict symmetries and measurements.
 +
 +
 +
<span style="font-size:larger;text-decoration:underline">Other Statistical Distributions</span>
 +
 +
To be artistically useful random numbers must be mapped into an aesthetic parameter (e.g. color, pitch, size), or a transformational parameter (i.e. a point in space or time).  Uniform distributions will provide selections and mappings that are totally without bias. But in setting up a situation without bias the artist misses an opportunity to blend choice with randomness. A normal distribution is a way to express a choice but to allow for the kind of variation one frequently sees in nature. While uniform and normal distributions can be useful in some cases an artist may want to find expression in designing distributions not found in nature. The following are techniques for doing this.
 +
 +
 +
 +
<span style="font-size:larger;text-decoration:underline">Designing Arbitrary Discreet Random Distributions</span>
 +
 +
A discreet random distribution is simply a random selection among a finite number of alternatives. Where each selection is equally likely a device such as a die is often used. But where different selections may have different probabilities a device such as a game spinner can be used, where various "slices" of the "pie" diagram have different sizes.
 +
 +
 +
{{SingleImage|imageWidthPlusTen=680|imageURL=http://www.viz.tamu.edu/courses/viza658/wiki/prob/07.jpg|caption=Discreet Random Distributions}}
 +
 +
 +
One can imagine a number line from 0 to 1 wrapped around the edge of the spinner. Unwrapping this number line suggests an algorithm for generating arbitrary discreet distributions driven by a typical uniform random number generator. The following pseudo-code could be more general or more efficient, but provides and example nevertheless.
 +
 +
// There are 3 colors. Color 1 is Blue, Color 2 is
 +
// Orange, and Color 3 is Green. Rather than coding
 +
// exact probabilities relative proportions are
 +
// used in an array, and then used to calculate
 +
// the thresholds needed to make random selections.
 +
 +
n = 3              // 3 colors
 +
 +
p(1) = 2            // relative amount of blue
 +
p(2) = 3            // relative amount of orange
 +
p(3) = 5            // relative amount of green
 +
 +
// total the amounts needed to represent proportions
 +
 +
total = 0
 +
for i = 1 to n
 +
    total = total + p(i)
 +
end
 +
 +
// calculate the thresholds between 0 and 1
 +
 +
last = 0
 +
for i = 1 to n
 +
    p(i) = last + ( p(i)/ total )
 +
    last = p(i)
 +
end
 +
 +
// now randomly select a color with the given proportions
 +
 +
test = rand()            // test is between 0 & 1
 +
 +
if      test < p(1) then
 +
    color = "blue"
 +
else if test < p(2) then
 +
    color = "orange"
 +
else
 +
    color = "green
 +
end
 +
 +
 +
 +
<span style="font-size:larger;text-decoration:underline">Designing Arbitrary Continuous Random Distributions</span>
 +
 +
An arbitrary distribution of continuous values can be designed by using line segments to approximate the distribution curve, and then using a so called "Monte Carlo" method to filter candidate values yielding the wanted distribution.
 +
 +
 +
{{SingleImage|imageWidthPlusTen=665|imageURL=http://www.viz.tamu.edu/courses/viza658/wiki/prob/08.jpg|caption=Designing Arbitrary Continuous Random Distributions}}
 +
 +
 +
Here is a subroutine written as pseudo-code implementing this method. There are more efficient ways of writing this code, but this version is offered for clarity.
 +
 +
 +
Function randval = randf( xf, yf, n )
 +
 +
// randval is the returned value between 0 and 1.
 +
// xf and yf are vectors (one dimensional arrays) which
 +
// are the (x,y) pairs which form line segments that
 +
// form the distribution "curve". n is the length of
 +
// xf and yf, i.e. the number of end points
 +
 +
while()                        // loop "forever" (until break)
 +
    randval = rand()            // candidate value
 +
    test =    rand()            // test value
 +
 +
// find the x endpoints of the line segment that brackets randval
 +
 +
    for i = 2 to n
 +
      if fx(i) > randval then break
 +
    end           
 +
 +
// now interpolate the y value on that line segment
 +
 +
    x1 = fx(i-1)
 +
    x2 = fx(i)
 +
    y1 = fy(i-1)
 +
    y2 = fy(i)
 +
    m  = (y1-y2) / (x1-x2)
 +
    y  = (m*(x2-x1)) + y1
 +
 +
// now see if the test value is below the line segment
 +
// if yes return randval, if no repeat the loop to try again
 +
 +
    if test < y then break
 +
 +
end
 +
 +
return randval
 +
 +
 +
<span style="font-size:larger;text-decoration:underline">Generating Normal (Gaussian) Random Distributions</span>
 +
 +
A Gaussian distribution can be described with two numbers, the mean and the standard deviation. The shape of the distribution is always the same, but the peak (the mean) and the degree of spread (the size of the standard deviation) will be specific to the subject matter in question. For example, consider IQ as (arguably) a measure of intelligence.
 +
 +
{{SingleImage|imageWidthPlusTen=601|imageURL=http://www.viz.tamu.edu/courses/viza658/wiki/prob/09.gif|caption=Designing Arbitrary Continuous Random Distributions}}
 +
 +
 +
In this case the mean is 100 points and 1 standard deviation is equivalent to 15 points. In terms of distribution 1 standard deviation to either side of the mean will include about 68% of the population. So in this case 68% of the population will have an IQ between 85 and 115. The diagram above uses rounded numbers, and thus the total greater than 100%. More accurate numbers are:
 +
 +
standard deviation        population
 +
      +/- 1              68.27%
 +
      +/- 2              95.450%
 +
      +/- 3              99.7300%
 +
      +/- 4              99.993666%
 +
 +
A Gaussian random number generator may only return a positive or negative standard deviation with 0 assumed as the mean. You will then have to scale and shift this number to produce the property needed. For example, let's say you wanted to randomly generate IQ scores for characters in a game. You would then multiply the generated amount by 15 (the standard deviation) and add 100 (the mean).
 +
 +
random gaussian number    calculated IQ
 +
        .6                (.6 * 15) + 100 = 109
 +
      -.2                (-.2 * 15) + 100 = 97
 +
      2.3                (2.3 * 15) + 100 = 134.5
 +
      -1.5                (-1.5 * 15) + 100 = 77.5
 +
 +
In other cases you can pass the mean and the standard deviation to the Gaussian random number generator and it will do the above for you.
 +
 +
There are a number of more sophisticated methods for generating a normal distribution, but for most generative art purposes a variation of the Monte Carlo method outlined above can be used.
 +
 +
The formula for the normal distribution density function is:
 +
 +
{{SingleImage|imageWidthPlusTen=570|imageURL=http://www.viz.tamu.edu/courses/viza658/wiki/prob/10.jpg|caption=}}
 +
 +
 +
This formula can be simplified by setting the mean = 0, the standard deviation = 1, and scaling the curve so it peaks at 1. The resulting formula in pseudo-code is:
 +
 +
          e = 2.71828183
 +
          y = e^( - ( x^2 / 2 ) )
 +
 +
and is illustrated in the following fragment of Matlab code.
 +
 +
{{SingleImage|imageWidthPlusTen=500|imageURL=http://www.viz.tamu.edu/courses/viza658/wiki/prob/11.jpg|caption=}}
 +
 +
 +
The first line creates a vector of values from -4 to 4 incremented by .05. The second line creates a vector y plugging each x value into the Gaussian curve formula. The third line plots the results below.
 +
 +
{{SingleImage|imageWidthPlusTen=667|imageURL=http://www.viz.tamu.edu/courses/viza658/wiki/prob/12.jpg|caption=}}
 +
 +
 +
The X axis is labeled with the number of standard deviations away from the mean 0. In a normally distributed population 68% of the values will be within 1 standard deviation of the mean (i.e. 68% of the randomly generated values should be between -1 and 1). 95% of the population will be within 2 standard deviations (i.e. between -2 and 2), and 99.7% will be within 3 standard deviations (i.e. between -3 and 3).
 +
 +
Uniform Random numbers are typically generated between the values 0 and 1, but in theory any number can be part of a population with a Gaussian distribution. In other words in theory a random number generator should be capable of generating unbounded values. But in practice extreme values are so rare that they can be safely ignored...and indeed for artistic purposes eliminating what statisticians would call "outliers" may be a good idea.
 +
 +
The Monte Carlo method for generating arbitrary random distributions breaks down when the values to be returned are unbounded. Fortunately it's not unreasonable to clip generated values beyond 3 or 4 standard deviations. The pseudo code below allows you to set the clipping value.
 +
 +
 +
Function randval = randnorm( mean, std, clip )
 +
 +
// randval is the returned value. It is a random number from
 +
// a simulated population where mean is the average value, std
 +
// is the standard deviation from the mean, and clip is the greatest
 +
// deviation allowed.
 +
 +
 +
e = 2.71828183
 +
 +
while()                                  // loop until break
 +
 +
    randval = ( ( 2 * rand()) - 1 ) * clip // candidate value
 +
    test =    rand()                      // test value
 +
 +
// calculate height of normalized curve at randval
 +
 +
    y = e^( - ( ( randval^2 ) / 2 ) )           
 +
 +
// now see if the test value is below the curve
 +
// if yes return randval, if no repeat the loop to try again
 +
 +
    if test < y then break
 +
 +
end
 +
 +
// now that we have a random value where mean=0 and std=1
 +
// scale the result for the requested mean and std
 +
 +
randval = ( randval * std ) + mean
 +
 +
return randval
== Links ==
== Links ==

Current revision

Retrieved from "http://philipgalanter.com/generative_art/wiki/index.php5?title=Chance_operations_%26_probability_theory"
Personal tools