# Chapter 4Random Selection I: Direct Randomness

The typescript for chapter 4 is provided in AutomatedComposition04.pdf.

### Synopsis

The opening discussion of randomness was inspired by Donald Knuth's essay, “What is a Random Sequence?” from Chapter 5, page 127 of Seminumerical Algorithms. The chapter explains how the statistical distribution of a population — which may or may not be of random genesis — can be graphed using a histograms. It then embarks upon a survey of distributions.

The historical discussions presented in Chapter 4 would subsequently find publication in Automated Composition in Retrospect at the pages indicated: Of American efforts, Hiller & Isaacson's 1959 Illiac Suite is described on pp. 170-171; James Tenny's 1963 Stochastic String Quartet is described on pp. 171-172; and Herbert Brun's 1964 Sonoriferous Loops is described on p. 172. European efforts included Iannis Xenakis's Morisma-Amorisma, created in 1962 using Xenakis's iconic Stochastic Music Program (p. 175). Barry Truax's POD program (for POisson Distribution) is also relevant since Truax, a Canadian, was then affiliated with the Institute of Sonology in Utrecht.

The present Chapter 4 and its topic continuations into Chapter 6 together spawned several articles published in the Leonardo Music Journal. These articles began with a paired set, a “Catalog of Statistical Distributions” in 1991 and a “Catalog of Sequence Generators” in 1992.

Seminumerical Algorithms remains excellent for its treatment of Derrick Henry Lehmer's linear congruence algorithm, the method universally used today. However the only two non-uniform cases dealt with by Knuth were the "polar" method of generating bell-curve randomness and a method for generating negative-exponential values. My chapter took things several steps farther by presenting generalized numerical methods. These methods accepted uniform numbers from zero to unity; some methods produced discrete nonuniform distributions, while other methods produced continuous distributions. The latter were obtained using rectangular approximations of the probability density curve. By the the 1991 publication of my Catalog of Statistical Distributions, the rectangular approximations had been refined into trapezoidal approximations.

By this time it had also become clear that the passive problem of transforming a uniform distribution into a non-uniform distribution was something entirely separate from the active problem of generating sequences, thus the “Catalog of Sequence Generators” presents random number generation as just one of many sequence types, each with its own characteristics. A third contribution to Leonardo Music Journal, “How to Level a Driver Sequence, explains how to redistribute non-uniform (e.g. chaotic) sequences so that relative highs and lows are retained but so that equal-sized regions between zero and unity contain equal numbers of samples.

An interactive graphic application illustrating sequence generators, statistical transforms, and how each influences the other is available on this site here.

### Commentary

The selection model adopted in this chapter carries over from Gottfried Michael Koenig's Project Two. For note attributes such as registers, entry delays, durations, and dynamics (chromatic degrees are more elaborate), the user provides a supply of options, then specifies a selection feature for choosing elements from the supply. Of the selection features, the one named ALEA is directly pertinent to the present chapter. ALEA selects randomly from the supply, with equal probability assigned to each element.

The inventor of probability theory is Jacob Bernoulli, who also developed the ball-and-urn paradigm as a way to explain the nature of randomness.

PitchE4F4G4A4B4C5D5
Probability 0.0850.1550.1740.1730.1740.1550.085
Denominator: 12 1/122/122/122/122/122/121/12
Denominator: 34 3/345/346/346/346/345/343/34
Table 1: Pitch probabilities with ratio approximations.

Suppose you have a sequence of notes and you want to assign a pitch to each note. Suppose further that you want to draw these pitches from the set E4, F4, G4, A4, B4, C5, and D5 and that you want the choices to be balanced according to the distribution enumerated in Table 1;. The genesis of this distribution will be explained in Chapter 6. For the present purposes it is sufficient to note that it prescribes generally uniform usage but tapers down both toward the lowest pitch E4 and toward the highest pitch D5.

The ball-and-urn paradigm suggests a way of pursuing selection; however working with three decimal places as in first Probability row of Table 1 would require the urn to contain 1000 balls. Rows 2 and 3 of the same table provide managable approximations using 12 and 34 balls. Applying the second row would institute the following process:

• Fill the urn with one ball marked E4, two balls marked F4, two marked G4, two marked A4, two marked B4, two marked C5, and one ball marked D5.
• To select a pitch for note #1, populate the balls into the urn and mix the balls blindly. Draw out a ball and assign the pitch name on the ball to note #1, then replace the draw in the urn.
• To select a pitch for note #2, repeat what happened for note #1: Mix the balls blindly. Draw out a ball and assign the pitch name on the ball to note #2, then replace the draw in the urn.
• Keep on going until all notes have pitches.

The practice just described is known as “random selection with replacement” in deference to the ball-and-urn paradigm. Computers implement weighted randomness much differently, using the linear congruence algorithm to generate a “pseudorandom” value ranging from zero to unity, then by mapping different regions of this range (larger regions for heavier weights) to different choices. This implementation has the advantage that probabilities need not be coarsened in order to reduce the total number of balls in the urn.

Randomness is subject to the Laws of Large Numbers. One particular law proved mathematically by Émile Borel applies specifically to the ball-and-urn paradigm. Borel's Law of Large Numbers says that as populations increase, the proportions of states within the population will converge to the proportions of correspondingly marked balls in the urn. But how large does a population need to be for Borel's Law to come into effect? If the states of the distribution are strongly distinguishable (e.g. chromatic steps as opposed to quarter tones), then for a distribution to ‘speak’, each state appear in the population at least once. Understand that by accepting this requirement, one implicitly settles for the coarsest approximation, that is, the proportions listed for denominator 12 in Table 1.

 Attempt   Length  Content Summary Counts  Proportions  Counts Proportions Counts Proportions E4 F4 G4 A4 B4 C5 D5 2 15 B4 C5 A4 D5 C5 D5 F4 E4 B4 D5 E4 B4 C5 E4 G4 3 1 1 1 3 3 3 0.200 0.0667 0.0667 0.0667 0.200 0.200 0.200 3 20 B4 E4 E4 C5 F4 B4 C5 E4 C5 D5 F4 C5 D5 A4 D5 F4 A4 F4 A4 G4 3 4 1 3 2 4 3 0.150 0.200 0.0500 0.150 0.1000 0.200 0.150 6 10 B4 A4 C5 F4 G4 B4 A4 C5 E4 D5 1 1 1 2 2 2 1 0.1000 0.1000 0.1000 0.200 0.200 0.200 0.1000 8 63 B4 B4 F4 C5 A4 B4 E4 B4 A4 C5 G4 C5 G4 C5 F4 G4 A4 C5 F4 B4 B4 E4 C5 E4 F4 G4 F4 E4 B4 E4 F4 A4 E4 G4 F4 G4 G4 A4 C5 B4 B4 C5 C5 E4 F4 G4 C5 G4 A4 B4 A4 F4 E4 A4 G4 E4 A4 G4 C5 B4 B4 G4 D5 9 9 12 9 12 11 1 0.143 0.143 0.190 0.143 0.190 0.175 0.0159 23 9 B4 E4 F4 G4 C5 A4 C5 A4 D5 1 1 1 2 1 2 1 0.111 0.111 0.111 0.222 0.111 0.222 0.111 31 12 B4 G4 C5 B4 B4 D5 A4 F4 A4 D5 B4 E4 1 1 1 2 4 1 2 0.0833 0.0833 0.0833 0.167 0.333 0.0833 0.167 48 8 B4 D5 C5 E4 A4 F4 B4 G4 1 1 1 1 2 1 1 0.125 0.125 0.125 0.125 0.250 0.125 0.125 57 28 B4 A4 C5 F4 C5 F4 C5 C5 A4 C5 G4 B4 C5 F4 C5 F4 D5 D5 B4 C5 B4 A4 F4 A4 D5 A4 G4 E4 1 5 2 5 4 8 3 0.0357 0.179 0.0714 0.179 0.143 0.286 0.107 80 42 B4 G4 E4 F4 G4 B4 F4 C5 F4 B4 F4 B4 F4 F4 C5 B4 C5 F4 C5 F4 C5 B4 F4 B4 G4 G4 G4 C5 G4 D5 D5 D5 C5 D5 C5 B4 G4 G4 E4 E4 E4 A4 4 9 8 1 8 8 4 0.0952 0.214 0.190 0.0238 0.190 0.190 0.0952
Table 2: Nine sequence generated using the weights prescribed in Table 1.

To illustrate how actual random populations can stray from prescribed distributions, I coded a process which selects pitches according to the decimal probabilities in Table 1. This process built sequences, continuing to appending pitches until all seven pitch values had been selected at least once. I ran this process 100 times using as many different random seeds What resulted were 100 sequences ranging in length from 8 to 63 pitches, with an average of 21 pitches per sequence. Table 2 reproduces nine of these sequences. These sequences expose an ugly truth, that even a population size of 63 is insufficient for Borel's Law of Large Numbers to exert influence. The distribution in Table 1 prescribes generally uniform usage tapering down slightly at the outside, but what actually resulted from these experiments is anything but that. Indeed, attempts #6, #23, and #31 greatly favor pitches higher pitches (A4 to D5) over lower pitches (E4 to G4).

### Demonstration

The practical programming content of Chapter 4 was provided by Demonstration 2: Random Selection. The outer loop of this program employs direct randomness to select attributes for phrases: phrase duration, average note duration, articulation, and register. The inner loop of the program decides randomly whether to generate a rest or a note; it employs direct randomness to select a duration and (for notes), a chromatic degree.

 © Charles Ames Page created: 2017-03-12 Last updated: 2017-03-12