View source

__FORCETOC__
One of the most popular methods used by novice generative artists is the use of chance operations.  This is sometimes called "randomization." The use of indeterminate events and random numbers is also often part of other more sophisticated methods.  This entry provides a quick background in probability in the context of generative art. 

== Probability of a Single Event ==
<SPAN STYLE="font-size: larger;">Introduction and examples </SPAN>


Given an ensemble of equally possible states, the probability of a given event occurring is the number of states which qualify as that event divided by the total number of possible states. A probability of 1 means the event is certain to occur. A probability of 0 means the event cannot possibly occur. A probability of .5 means the event is equally likely to occur or not occur.


'''Example: What is the probability of flipping a coin and getting heads?'''

Total number of states in the ensemble = 2 (heads and tails) <br>
Total number of states that qualify as the event in question = 1 (heads)

Probability = 1/2 = .5
 

'''Example: What is the probability of drawing an ace of spades from a shuffled deck of cards?'''

Total number of states in the ensemble = 52 (total number of cards in the deck) <br>
Total number of states that qualify as the event in question = 1 (the ace of spades)

Probability = 1/52 = .01923
 

'''Example: What is the probability of drawing an ace from a shuffled deck of cards?'''

Total number of states in the ensemble = 52 (total number of cards in the deck) <br>
Total number of states that qualify as the event in question = 4 (the ace of spades, hearts, clubs, and diamonds)

Probability = 4/52 = .07692


== Probability of a Sequence of Independent Events ==
<SPAN STYLE="font-size: larger;">By example </SPAN>


The probability of a sequence of independent probabilistic events is the product of the individual probabilities of those events.


'''Example: What is the probability of flipping a coin and getting 4 heads in a row?'''

Probability of the individual event = .5 <br>
Probability of a sequence of 4 of those events = .5 * .5 * .5 * .5 = .0625

Although it is counter-intuitive to some, this example and the previous one show that it's more likely you can draw an ace from a shuffled deck of cards (.07692) than flip 4 heads in a row (.0625).


'''Example: What is the probability of drawing 4 aces from a shuffled deck of cards?'''

For the first card: <br>
Total number of states in the ensemble = 52 (total number of cards in the deck) <br>
Total number of states that qualify as the event in question = 4 (the ace of spades, hearts, clubs, and diamonds)

Probability = 4/52 = .07692

For the second card: <br>
Total number of states in the ensemble = 51 (total number of cards remaining in the deck) <br>
Total number of states that qualify as the event in question = 3 (the remaining aces)

Probability = 3/51 = .05882

For the third card: <br>
Total number of states in the ensemble = 50 (total number of cards remaining in the deck) <br>
Total number of states that qualify as the event in question = 4 (the remaining aces)

Probability = 2/50 = .04

For the fourth card: <br>
Total number of states in the ensemble = 49 (total number of cards remaining in the deck) <br>
Total number of states that qualify as the event in question = 4 (the remaining ace)

Probability = 1/49 = .02040

Probability of drawing 4 aces = (4/52) * (3/51) * (2/50) * (1/49) = .0000036919



== Combinatorial Probability ==
<SPAN STYLE="font-size: larger;">Analyzing the qualifying states in an event</SPAN>


As noted above the probability of an event is a function of the number of states in an ensemble and the number of those states which qualify as the event in question. In some situations counting the number of qualifying states is a matter of analyzing combinations.

In the case of flipping coins you can think of each coin as a bit in a binary number.  When you flip a single coin you have a single bit.  In other words heads or tails is analogous to 1 or 0.  So a single coin, like a single bit, has 2 states.  Getting a head has a probability of .5 because it represents one state out of the possible 2, or 1/2= .5.

Flipping 2 coins is like working with 2 bits.  2 bits have 4 states, i.e. with 2 bits you can count from 0 to 3 (00 -> 01 -> 10 -> 11).  Of those 4 states only one has both heads (HH or 11), one state has both tails (TT or 00), and two states have a head and tails (HT and TH, or 01 and 10).  So the probability of getting both heads is 1/4 or .25.  The probability of getting a head and a tail is 2/4 or .5.  The probability of getting both tails is 1/4 or .25.  

The sum of all the possible probabilities always equals 1.  This is just a way of saying that when you flip some coins one of the possible outcomes will definitely happen!  In this case .25 + .5 + .25 = 1.


'''Example: What is the probability of flipping 4 coins and getting 2 heads and 2 tails?'''

Total number of states for 4 coins = number of states for 4 bits = 2<sup>4</sup> = 16.<br>
Total number of states that includes 2 heads and 2 tails: <br>
HHTT TTHH HTHT THTH HTTH THHT = 6 states<br>
Probability of 2 heads and 2 tails from 4 flipped coins = 6/16 = .375.


<SPAN STYLE="font-size: larger;"><u>Pascal's Triangle</u></SPAN>

The geometric arrangement of numbers below was devised by Blaise Pascal to demonstrate and calculate the probability of a proposition that is a combination of binary events.  It can be used as an aid in coin flipping examples where you need to know the number of ways a given combination can occur.  (I.e. the number of permutations for a given combination). 

To construct Pascal's Triangle each number is the sum of the 2 numbers in the line above.  The resulting numbers can be viewed as the expected statistical distribution.  Reading from left to right in the line for 3 coins, there is one way to get 3 heads (HHH), 3 ways to get 2 heads (HHT, HTH, THH), 3 ways to get 1 head (HTT, THT, TTH), and 1 way to get 0 heads (TTT).

If you add up all the numbers in a line you get the sum of all the possible states or outcomes.  So for 3 coins there are 1 + 3 + 3 + 1 = 8 possible outcomes.  Note that this is consistent with using 3 bits to count from 0 to 7.  
<br><tt>
                              1 
 1 coin                     1   1                    sum = 2<sup>1</sup> =   2
 2 coins                  1   2   1                  sum = 2<sup>2</sup> =   4 
 3 coins                1   3   3   1                sum = 2<sup>3</sup> =   8
 4 coins              1   4   6   4   1              sum = 2<sup>4</sup> =  16 
 5 coins            1   5  10  10   5   1            sum = 2<sup>5</sup> =  32 
 6 coins          1   6  15  20  15   6   1          sum = 2<sup>6</sup> =  64 
 7 coins        1   7  21  35  35  21   7   1        sum = 2<sup>7</sup> = 128 
 8 coins      1   8  28  56  70  56  28   8   1      sum = 2<sup>8</sup> = 256 
</tt>

To calculate the probability of a given outcome one simply takes the number of outcomes that lead to the desired result, divided by the number of possible results.  So the probability of flipping 3 coins and  getting a head and 2 tails is: 

(3) / ( 1 + 3 + 3 + 1 ) = 3/8 = .375


'''Example: What is the probability of flipping 6 coins and getting 3 heads and 3 tails?'''

The "6 coins" row indicates there are 20 ways to get 3 heads and 3 tails.
It also indicates there are 64 possible outcomes. 
The probability of flipping 6 coins and getting 3 heads and 3 tails is then 20/64 = .3125

Note that even though the most likely result of flipping 6 coins is an equal number of heads and tails, this actually happens less than than 1/3 of the time.  An even money bet against getting 3 heads and 3 tails is a winner!


== The Independence of Events and the Gambler's Fallacy ==
<SPAN STYLE="font-size: larger;">The myth of streaks </SPAN>

Its important to remember that each random event is unrelated to any other preceding event.  While flipping 10 heads in a row is very unlikely, once one has flipped 9 heads in a row the probability for the 10th flip is the same as it ever was, .5 for heads and .5 for tails.  Gamblers often think that so called "streaks" are meaningful, but in the case of random events they are not.  Oddly, for every misguided gambler who thinks that 9 heads in a row constitutes a streak that is likely to continue, there is usually another gambler who thinks 9 heads in a row means that tails are "due".  Both are wrong.
 

== Statistical Distributions ==
<SPAN STYLE="font-size: larger;">Different kinds of randomness </SPAN>


(Text Pending)


<SPAN STYLE="font-size: larger;"><u>Uniform Distributions</u></SPAN>

(Text and Illustration Pending)


<SPAN STYLE="font-size: larger;"><u>The Normal or Gaussian Distribution</u></SPAN>

As more and more lines are added to Pascal's Triangle the distribution approximates a "bell curve" or "normal distribution", also known as a "Gaussian distribution."  This distribution is found throughout nature.  For example height and weight measurements of a given population will approximate a normal distribution.  

The reason this happens is that such natural phenomena are typically determined by a large number of factors.  In the case of the height of an individual some factors will contribute to being tall while others will contribute to being short.  Just as there are more ways to flip a mix of heads and tails than there are ways to flip all or mostly heads, there are more ways to combine these factors to lead to medium height than there are to lead to being very tall or very short.


<SPAN STYLE="font-size: larger;"><u>Pinball Example</u></SPAN>

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>


This geometric arrangement of numbers was devised by Blaise Pascal to demonstrate and calculate the probability of a proposition that is the combination of binary events.  To construct Pascal's Triangle each number is the sum of the 2 numbers in the line above.  The resulting numbers can be viewed as the expected statistical distribution.  For example, flipping 3 coins there is only one way to get all heads or all tails, but 3 ways to get 1 tail and 2 heads (THH, HTH, HHT), and 3 ways to get 1 head and 2 tails.
 
 
           1
          1 1
         1 2 1
        1 3 3 1
       1 4 6 4 1
     1 5 10 10 5 1
   1 6 15 20 15 6 1
  1 7 21 35 35 21 7 1
 1 8 28 56 70 56 28 8 1


To calculate the probability of a given outcome one simply takes the number of combinations that can lead to the desired result, divided by the number of possible results.  So the probability of flipping 3 coins and  getting a head and 2 tails is:

 (3) / ( 1 + 3 + 3 + 1 ) = 3/8 = .375

 
The probability of flipping 6 coins and getting the most likely result of 3 heads and 3 tails is:

 (20) / ( 1 + 6 + 15 + 20 + 15 + 6 + 1 ) = 20/64 = .3125

Note that the result common sense would expect, an equal number of heads and tails, when flipping 6 coins happens less than than 1/3 of the time!



<SPAN STYLE="font-size: larger;"><u>The Independence of Events and the Gambler's Fallacy</u></span>
 

It's important to remember that each random event is unrelated to any other preceding event.  While flipping 10 heads in a row is very unlikely, once one has flipped 9 heads in a row the probability for the 10th flip is the same as it ever was, .5 for heads and .5 for tails.  Gamblers often think that so called "streaks" are meaningful, but in the case of random events they are not.  Oddly, for every misguided gambler who thinks that 9 heads in a row constitutes a streak that is likely to continue, there is usually another gambler who thinks 9 heads in a row means that tails are "due".  Both are wrong.


<SPAN STYLE="font-size: larger;">The Normal or Gaussian Distribution</span>

As more and more lines are added to Pascal's Triangle the distribution approximates a "bell curve" or the normal distribution, also known as a Gaussian Distribution.  This distribution is found throughout nature, for example height and weight measurements of a given population will approximate a normal distribution. 


{{SingleImage|imageWidthPlusTen=594|imageURL=http://www.viz.tamu.edu/courses/viza658/wiki/prob/01.jpg|caption=Gaussian Distribution}}


{{SingleImage|imageWidthPlusTen=612|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/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]


<SPAN STYLE="font-size: larger;"><u>The Law of Large Numbers</u></SPAN>

Even though events in nature will often tend towards a normal distribution, any particular set of measures or samples will show variation.  Where sample sizes are small the general distribution in nature may not be at all apparent.  As the sample size grows the apparent distribution will incrementally grow closer to the actual distribution in all of nature.

Here is a simulation of a pinball machine that demonstrates the Gaussian distribution of the result. Note how as more balls are put into play the distribution moves closer and closer to a Gaussian distribution.

http://www.jcu.edu/math/isep/Quincunx/Quincunx.html

== Pragmatic notes on using random numbers in art ==


<span style="font-size:larger;text-decoration:underline">Pseudo Random Number Generators</span>

Because a computer is a finite state machine it cannot generate truly random numbers.  There are algorithms for generating pseudo random numbers which, however, for all practical art purposes can be thought of as random.  Typically pseudo random number generators use a "seed value" to begin the sequence of numbers it will generate.  If the same seed value is used, the same sequence will be generated, and the generative system will produce the same artwork over and over again.  When using a random number generator be sure to use it in a mode where it changes the seed value every time it is used to prevent this from happening.
 

<span style="font-size:larger;text-decoration:underline">Uniform Random Distributions and Clustering</span>

Pseudo random number generators create a uniform distribution of values in the long run. Any value is as likely as any other value. However, as the Law of Large Numbers suggests, small collections of random numbers will not be distributed uniformly,  For some artistic applications it may be useful to post process a set of random values by either removing outliers (extreme cases that stand out as odd), removing near duplications (where 2 cases are almost the same value), or smoothing the numbers to achieve a more uniform distribution without losing the random "feel" of the events.

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.



{{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/06.jpg|caption=The de-clumping algorithm works by first analyzing each center point and finding the nearest neighbors.}}


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
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 ==

[[Category:Systems]]
[[Category:Systems used in The code as art movement]]
[[Category:Systems used in Computer animation and effects]]
[[Category:Systems used in Computer graphics]]
[[Category:Systems used in Conceptual and minimal art]]
[[Category:Systems used in The demo scene]]
[[Category:Systems used in Design]]
[[Category:Systems used in Electronic music]]
[[Category:Systems used in Live coding]]
[[Category:Systems used in Music composition]]
[[Category:Systems used in Physical computing]]
[[Category:Systems used in Robotic art]]
[[Category:Systems used in VJ culture]]