Do Something Random
From BenningtonWiki
Notes I prepared for my co-taught course Music, Interactivity and Technology. The term random had been thrown around in class in discussions about automatic and interactive music. I wanted to dig deeper into what random means.
Contents |
[edit] Intro (of sorts)
People who think about this topic almost invariably get into philosophical discussions about what the word "random" means. In a sense, there's no such thing as a random number. Is "2" a random number? Rather, we will speak of a sequence of independent random numbers from a given set, with a specified distribution.
[edit] Stochastic Processes, Random Sequences
- Generated by a random process (stochastic)
- Examples: flipping a coin, rolling dice, drawing balls from an urn
- Random sequence (random)
- Irregular, impossible to express in a shorter form
- Unpredictable, unexpected - "he was acting so random", "god, that was so random"
- 1000 heads in a row does not look random, because it's not. Even if a sequence is generated stochastically, it's not guaranteed to produce a random sequence.
- Terminology
- Generated by a random process - stochastic, from the Greek 'to guess'; what's the next coin toss going to be?
- An unpredictable sequence - random, from Old English meaning 'an impetuous headlong rush'
- Stochastic processes
- A table of over 40,000 random digits "taken at random from census reports" was published in 1927 by L.H.C. Tippet.
- The Mark I computer, first installed in 1951, had a built-in instruction that would place 20 random bits into the accumulator using a resistance noise generator; this mechanism was suggested by Alan Turing.
- More recently, G. Marsaglia in 1995 distributed a CD with 650 random megabytes, generated by combining the output of a noise-diode circuit with deterministically scrambled rap music.
- Are there truly stochastic methods? Quantum mechanical processes, radioactive decay, noise from a vacuum tube.
- Random number tables from the 50s used truly stochastic methods
- Machines make random sequences using methods that are deterministic but with chaotic properties
[edit] Chaos
Let's take a side trip through chaos:
- Deterministic chaos
- A system is chaotic if its trajectory through state space is sensitively dependent on the initial conditions, that is, if unobservably small causes can produce large effects.
- Processes which are very sensitive to small fluctuations are called chaotic. This is because their trajectories are in general very irregular, so that they give the impression of being random, even though they are driven by deterministic forces.
- Amplifiers: they turn small causes into large effects; although the process is deterministic in principle, "equal causes having equal effects", it is unpredictable in practice.
- Causes (initial conditions) that seem equal to the best of our knowledge can still have unobservable differences and therefore lead to very different effects.
The meteorologist Edward Lorentz invented the expression "the butterfly effect". While studying the equations that determine the weather he noticed that their outcomes are strongly dependent on the initial conditions. The weather is a chaotic system. The tiniest fluctuations in air pressure in one part of the globe may have the most spectacular effects in another part. Thus, a butterfly flapping its wings somewhere in Brazil may cause a tornado in Texas. This explains why scientists find it so difficult to predict the weather. In order to predict future situations one needs to know the present situation in its finest details. But it's very difficult to know all the details, to monitor every butterfly flapping its wings! The fewer details one knows, the less accurate the long term predictions. That is why weather prediction seldom extend more than a few days in the future.
This is where "emergence" comes in. Emergence describes the behavior of a deterministic system at a higher level than that of the butterfly's wings. My favorite examples of emergence in action lie in Computing. The operation of a modern electronic computer is entirely deterministic. At its lowest level, the butterfly wings level, you're describing literally billions of electronic gates operating on primitive boolean rules. I imagine that if you could observe these gates in action it would look like static on a TV. They are entirely deterministic, doing exactly what they're designed to do. But meaningless when observed at that level. But something emerges from that noise. A step up from the gates you begin describing the operations in machine language, and algorithms begin to come into the picture. There's design. Groups of operating gates can be clumped into human readable operations, and the bits become recognizeable as they form sequences of tens of thousands of instructions. Still very difficult to visualize, when programs reach the millions of instructions, as they do. So we computer scientists abstract further. We clump machine language instructions into higher languages and begin to express our algorithms in pages of highly compressed instructions. We also give meaning to complex patterns of bits in memory. Letters of the alphabet, images, sounds. Now a seemingly meaningless sequence of a million bits becomes an mp3, Beyonce singing Crazy in Love. Or these million bits are the complete works of Shakespeare. At this level, stories emerge. That's emergence.
[edit] Properties of Randomness
Back to randomness. Distribution, probability, odds.
- We generally expect that in a stochastic process every possible outcome has equal probability. Coins have two sides and we expect the odds to be 50/50. With a six sided die we expect that each side has a 1 in 6 chance of being rolled. This is called uniform distribution.
- Some questions about our expectations of stochastic processes:
- Do you expect to see some outcomes more often that others?
- Do you expect to see all of the outcomes before you see an outcome repeated?
- Which sequence is more "random"? Which process is more "stochastic"?
- When you play an iPod on shuffle, is the process stochastic? Is the sequence random?
- In statistics, a histogram is a graphical display of tabulated occurrences. It shows what proportion of cases fall into each of several or many specified categories.
- 6-sided die roll histogram.
- Image histogram.
- Audio: white noise has equal probability. Called a flat power spectral density. A flat histogram.
- Pink noise and red or "Brownian" noise have histograms that are not flat, they taper off (higher values have less probability).
- Can a stochastic process generate pink noise? Consider a 6-sided die with different probabilities for each side (1 more likely than 2, 2 more likely than 3, etc.) Draw it. (1-1-1-2-2-3)
[edit] Random Number (Sequence) Generators
- "Anyone who considers arithmetical methods of producing random digits is, of course, in a state of sin." – Von Neumann
- Definite mathematical or algorithmic rule, but one so messy that it is supposed to simulate a chance process, a chaotic rule
- Purely deterministic.
- Linear Congruential method
- One of the oldest and best-known pseudo-random number generating algorithms. D.H. Lehmer in 1949.
- x = xa mod m; x = (x * 48271) % (2^31 - 1)
- http://www.cs.wm.edu/~va/software/park/park.html
- Random Number Generator
- General properties of LCM: same seed gives the same sequence; sequence repeats: there is ultimately a cycle of numbers that is repeated endlessly.
[edit] Summary
For practical use, the question is do you want a stochastic process or do you want a random sequence? Stochastic processes have their own intrinsic aesthetic. Example, Matmos' use of snails and laser beams. But the resulting sequence may not be random. You could look at a sequence and say, "That's not random enough." Even if it was generated stochastically. Enough said.
[edit] Sources
- Murray Gell-Mann, The Quark and the Jaguar, 1994. ISBN 0805072535
- Donald E. Knuth, The Art of Computer Programming, Volume 2: Seminumerical Algorithms (3rd Ed.), 1998. ISBN 0201896842
