Applications of randomness

From Wikipedia, the free encyclopedia
Jump to: navigation, search
Main article: Randomness

Randomness has many uses in art, statistics, cryptography, gambling, etc.

These uses have different randomness requirements, which leads to the use of different randomization methods. For example, applications in cryptography have strict requirements,[citation needed] whereas other uses (such as generating a "quote of the day") can use a looser standard of randomness.

Early uses[edit]

Divination[edit]

Many ancient cultures saw natural events as signs from the gods; many attempted to discover the intentions of the gods through various sorts of divination. The underlying theory was that the condition of, say, a chicken's liver, was connected with, perhaps, the dangerous storms or military or political fortune. Divination is still practiced and on much the same basis as formerly.

Games[edit]

Unpredictable (by the humans involved) numbers (usually taken to be random numbers) were first investigated in the context of gambling developing, sometimes, pathological forms like apophenia. Many randomizing devices such as dice, shuffling playing cards, and roulette wheels, seem to have been developed for use in games of chance. Electronic gambling equipment cannot use these and so theoretical problems are less easy to avoid; methods of creating them are sometimes regulated by governmental gaming commissions.

Modern electronic casino games contain often one or more random number generators which decide the outcome of a trial in the game. Even in modern slot machines, where mechanical reels seem to spin on the screen, the reels are actually spinning for entertainment value only. They eventually stop exactly where the machine's software decided they would stop when the handle was first pulled. It has been alleged that some gaming machines' software is deliberately biased to prevent true randomness, in the interests of maximizing their owners' revenue; the history of biased machines in the gambling industry is the reason government inspectors attempt to supervise the machines—electronic equipment has extended the range of supervision. Some thefts from casinos have used clever modifications of internal software to bias the outcomes of the machines—at least in those which have been discovered. Gambling establishments keep close track of machine payouts in an attempt to detect such alterations.

Random draws are often used to make a decision where no rational or fair basis exists for making a deterministic decision, or to make unpredictable moves.

Political use[edit]

Athenian democracy[edit]

Fifth century BC Athenian democracy developed out of a notion of isonomia (equality of political rights), and random selection was a principal way of achieving this fairness.[1] Greek democracy (literally meaning "rule by the people") was actually run by the people: administration was in the hands of committees allotted from the people and regularly changed. Although it may seem strange to those used to modern liberal democracy, the Athenian Greeks considered elections to be essentially undemocratic.[2][3] This was because citizens chosen on merit or popularity contradicted the democratic equality of all citizenry. In addition, allotment prevented the corrupt practice of buying votes as no one could know who would be selected as a magistrate, or to sit on a jury.

Modern use[edit]

Allotment is today restricted mainly to the selection of jurors in Anglo-Saxon legal systems like the UK and United States. Proposals have been made for its use in government such as a new constitution for Iraq[4] and various proposals for Upper Houses chosen by allotment. (See Lords reform.)

Science[edit]

Random numbers have uses in physics such as electronic noise studies, engineering, and operations research. Many methods of statistical analysis, such as the bootstrap method, require random numbers. Monte Carlo methods in physics and computer science require random numbers.

Random numbers are often used in parapsychology as a test of precognition.

Statistical sampling[edit]

Statistical practice is based on statistical theory which is, itself, founded on the concept of randomness. Many elements of statistical practice depend on randomness via random numbers. Where those random numbers fail to be actually random, any subsequent statistical analysis may suffer from systematic bias. Elements of statistical practice that depend on randomness include: choosing a representative sample, disguising the protocol of a study from a participant (see randomized controlled trial) and Monte Carlo simulation.

These applications are useful in auditing (for determining samples - such as invoices) and experimental design (for example in the creation of double-blind trials).

Analysis[edit]

Many experiments in physics rely on a statistical analysis of their output. For example, an experiment might collect X-rays from an astronomical source and then analyze the result for periodic signals. Since random noise can be expected to appear to have faint periodic signals embedded in it, statistical analysis is required to determine the likelihood that a detected signal actually represents a genuine signal. Such analysis methods requires the generation of random numbers. If the statistical method is extremely sensitive to patterns in the data (such as those used to search for binary pulsars), very large amounts of data with no recognizable pattern are needed.

Simulation[edit]

In many scientific and engineering fields, computer simulations of real phenomena are commonly used. When the real phenomena are affected by unpredictable processes, such as radio noise or day-to-day weather, these processes can be simulated using random or pseudo-random numbers.

Automatic random number generators were first constructed to carry out computer simulation of physical phenomena, notably simulation of neutron transport in nuclear fission.

Pseudo-random numbers are frequently used in simulation of statistical events, a very simple example being the outcome of tossing a coin. More complicated situations are simulation of population genetics, or the behaviour of sub-atomic particles. Such simulation methods, often called stochastic methods, have many applications in computer simulation of real-world processes.

Some more speculative projects, such as the Global Consciousness Project, monitor fluctuations in the randomness of numbers generated by many hardware random number generators in an attempt to predict the scope of an event in near future. The intent is to prove that large scale events that are about to happen build up a "pressure" which affects the RNGs.

Cryptography[edit]

A ubiquitous use of unpredictable random numbers is in cryptography which underlies most of the schemes which attempt to provide security in modern communications (e.g., confidentiality, authentication, electronic commerce, etc.).

For example, if a user wants to use an encryption algorithm, it is best that they select a random number as the key. These numbers must have high entropy for any attacker, thus increasing attack difficulty. With low entropy numbers used as keys (i.e., relatively easily guessable by attackers), security is likely to be compromised. For example, if a simple 32 bit linear congruential pseudo-random number generator of the type supplied with most programming languages is used as a source of keys, then there will only be some four billion possible values produced before the generator repeats itself. A suitably motivated adversary could simply test them all; this is practical as of 2010, using readily available computers. Even if a linear congruential RNG is used with 1000-bit parameters, it is a simple exercise in linear algebra to recover the modulus m, and the constants a and b, where x' = ax +b (mod m), given only five consecutive values. Even if a better random number generator is used, it might be insecure (i.e., its starting value, the seed) might be guessable, producing predictable keys and reducing security to nil. (A vulnerability of this sort was famously discovered in an early release of Netscape Navigator, forcing the authors to quickly find a source of "more random" random numbers). For these applications, truly random numbers are ideal, and very high quality pseudo-random numbers are necessary if truly random numbers are unavailable.

Truly random numbers are absolutely required to be assured of the theoretical security provided by the one-time pad — the only provably unbreakable encryption algorithm. Furthermore, those random sequences cannot be reused and must never become available to any attacker, which implies a continuously operable generator. See Venona for an example of what happens when these requirements are violated when using a one-time pad.

For cryptographic purposes, one normally assumes some upper limit on the work an adversary can do (usually this limit is astronomically sized). If one has a pseudo-random number generator whose output is "sufficiently difficult" to predict, one can generate true random numbers to use as the initial value (i.e., the seed), and then use the pseudo-random number generator to produce numbers for use in cryptographic applications. Such random number generators are called cryptographically secure pseudo-random number generators, and several have been implemented (for example, the /dev/urandom device available on most Unixes, the Yarrow and Fortuna designs, server, and AT&T Bell Laboratories "truerand"). As with all cryptographic software, there are subtle issues beyond those discussed here, so care is certainly indicated in actual practice. In any case, it is sometimes impossible to avoid the need for true (i.e., hardware) random number generators.

Since a requirement in cryptography is high entropy (i.e., unpredictability to an attacker), any published random sequence is a poor choice, as are such sequences as the digits in an irrational number such as the φ or even in transcendental numbers such as π, or e. All are available to an enterprising attacker. Put another way, in cryptography, random bit streams need to be not only random, but also secret and hence unpredictable. Public or third-party sources of random values, or random values computed from publicly observable phenomena (weather, sports game results, stock prices), are almost never cryptographically acceptable, though often tempting and too often used by the unwary. They permit easier attacks than attacking the cryptography.

Since most cryptographic applications require a few thousand bits at most, slow random number generators serve well—if they are actually random. This use of random generators is important; many informed observers[who?] believe every computer should have a way to generate true random numbers.

Literature, music and art[edit]

Some aesthetic theories claim to be based on randomness in one way or another. Little testing is done in these situations, and so claims of reliance on and use of randomness are generally abstract.

An example of a need for randomness sometimes occurs in arranging items in an art exhibit. Usually this is avoided by using a theme. As John Cage pointed out, "While there are many ways that sounds might be produced [i.e., in terms of patterns], few are attempted". Similarly, the arrangement of art in exhibits is often deliberately non-random. One case of this was Hitler's attempt to portray modern art in the worst possible light by arranging works in worst possible manner.[citation needed] A case can be made for trying to make art in the worst possible way; i.e., either as anti-art, or as actually random art.

Dadaism, as well as many other movements in art and letters, has attempted to accommodate and acknowledge randomness in various ways. Often people mistake order for randomness based on lack of information; e.g., Jackson Pollock's drip paintings, Helen Frankenthaler's abstractions (e.g., "For E.M."). Thus, in some theories of art, all art is random in that it's "just paint and canvas" (the explanation of Frank Stella's work).

Similarly, the "unexpected" ending is part of the nature of interesting literature. An example of this is Denis Diderot's novel Jacques le fataliste (literally: James the Fatalist; sometimes referred to as Jacques the Fatalist or Jacques the Servant and his Master). At one point in the novel, Diderot speaks directly to the reader:

Now I, as the author of this novel might have them set upon by thieves, or I might have them rest by a tree until the rain stops, but in fact they kept on walking and then near night-fall they could see the light of an inn in the distance.

(not an exact quote). Diderot was making the point that the novel (then a recent introduction to European literature) seemed random (in the sense of being invented out of thin air by the author). See also Eugenio Montale, Theatre of the Absurd.

Randomness in music is generally thought[by whom?] to be postmodern, including John Cage's chance derived Music of Changes, Iannis Xenakis' stochastic music, aleatoric music, indeterminate music, or generative music.

Other uses[edit]

Random numbers are also used in situations where "fairness" is approximated by randomization, such as selecting jurors and military draft lotteries. In the Book of Numbers (33:54), Moses commands the Israelites to apportion the land by lot.

Other examples include selecting, or generating, a "Random Quote of the Day" for a website, or determining which way a villain might move in a computer game.

Weaker forms of randomness are also closely associated with hash algorithms and in creating amortized searching and sorting algorithms.

See also[edit]

References[edit]

  1. ^ Herodotus 3.80
  2. ^ The Athenian Democracy in the Age of Demosthenes", Mogens Herman Hansen, ISBN 1-85399-585-1
  3. ^ “it is thought to be democratic for the offices to be assigned by lot, for them to be elected is oligarchic,” [Aristotle, Politics 4.1294b]
  4. ^ http://www.sortition.org.uk

External links[edit]