Chance operations & probability theory

From GenerativeArt

(Difference between revisions)
Jump to: navigation, search
(→Statistical Distributions)
Current revision (04:15, 21 November 2012) (view source)
(fix image urls)
 
-
{{SingleImage|imageWidthPlusTen=655|imageURL=http://www-viz.tamu.edu/courses/viza658/wiki/prob/00.jpg|caption=Pinball Example}}
+
{{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]
-
{{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.}}
+
{{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.}}
-
{{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.}}
+
{{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.}}
-
{{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.}}
+
{{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.}}
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.  
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=594|imageURL=http://www-viz.tamu.edu/courses/viza658/wiki/prob/07.jpg|caption=}}
+
 
 +
{{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