These uses have different levels of requirements, which leads to the use of different methods. Mathematically, there are distinctions between randomization, pseudorandomization, and quasirandomization, as well as between random number generators and pseudorandom number generators. For example, applications in cryptography usually have strict requirements, whereas other uses (such as generating a "quote of the day") can use a looser standard of pseudorandomness.
Early uses
Games
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
Athenian democracy
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 politics
Allotment, also called sortition, is today used in the selection of jurors in Anglo-Saxon legal systems like the UK and United States.[4] Proposals have been made for its use in government such as a new constitution for Iraq and various proposals for Upper Houses chosen by allotment—see Reform of the House of Lords §Allotment (sortition).[4] Scholars have studied the potential of random selection of personnel in politics and organizations.[5]
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 of the population being examined, disguising the protocol of a study from a participant (see randomized controlled trial) and Monte Carlo simulation.
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
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.
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.
For example, if a user wants to use an encryption algorithm, it is best that they select a random number as the key. The selection must have high entropy (i.e., unpredictability) to any attacker, thus increasing attack difficulty. With keys having low entropy (i.e., relatively easily guessable by attackers), security is likely to be compromised. To illustrate, imagine if a simple 32 bit linear congruential pseudo-random number generator of the type supplied with most programming languages (e.g., as the 'rand' or 'rnd' function) is used as a source of keys. 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 (e.g., 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, such as coming from a hardware random number generator, 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-based) random number generators.
Since a requirement in cryptography is high entropy, 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. Their use may be tempting, but in reality, 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
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 poorly based in definite theory and more on an impression of randomness from technical fields.
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, not in a modern technical sense). See also Eugenio Montale, Theatre of the Absurd.
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.
A pseudorandom sequence of numbers is one that appears to be statistically random, despite having been produced by a completely deterministic and repeatable process.
A pseudorandom number generator (PRNG), also known as a deterministic random bit generator (DRBG), is an algorithm for generating a sequence of numbers whose properties approximate the properties of sequences of random numbers. The PRNG-generated sequence is not truly random, because it is completely determined by an initial value, called the PRNG's seed. Although sequences that are closer to truly random can be generated using hardware random number generators, pseudorandom number generators are important in practice for their speed in number generation and their reproducibility.
A linear congruential generator (LCG) is an algorithm that yields a sequence of pseudo-randomized numbers calculated with a discontinuous piecewise linear equation. The method represents one of the oldest and best-known pseudorandom number generator algorithms. The theory behind them is relatively easy to understand, and they are easily implemented and fast, especially on computer hardware which can provide modular arithmetic by storage-bit truncation.
Monte Carlo methods, or Monte Carlo experiments, are a broad class of computational algorithms that rely on repeated random sampling to obtain numerical results. The underlying concept is to use randomness to solve problems that might be deterministic in principle. They are often used in physical and mathematical problems and are most useful when it is difficult or impossible to use other approaches. Monte Carlo methods are mainly used in three problem classes: optimization, numerical integration, and generating draws from a probability distribution.
In computing, a hardware random number generator (HRNG) or true random number generator (TRNG) is a device that generates random numbers from a physical process, rather than by means of an algorithm. Such devices are often based on microscopic phenomena that generate low-level, statistically random "noise" signals, such as thermal noise, the photoelectric effect, involving a beam splitter, and other quantum phenomena. These stochastic processes are, in theory, completely unpredictable for as long as an equation governing such phenomena is unknown or uncomputable. This is in contrast to the paradigm of pseudo-random number generation commonly implemented in computer programs.
A cryptographically secure pseudorandom number generator (CSPRNG) or cryptographic pseudorandom number generator (CPRNG) is a pseudorandom number generator (PRNG) with properties that make it suitable for use in cryptography. It is also loosely known as a cryptographic random number generator (CRNG).
Manuel Blum is a Venezuelan-American computer scientist who received the Turing Award in 1995 "In recognition of his contributions to the foundations of computational complexity theory and its application to cryptography and program checking".
In computer science, a deterministic algorithm is an algorithm that, given a particular input, will always produce the same output, with the underlying machine always passing through the same sequence of states. Deterministic algorithms are by far the most studied and familiar kind of algorithm, as well as one of the most practical, since they can be run on real machines efficiently.
The security of cryptographic systems depends on some secret data that is known to authorized persons but unknown and unpredictable to others. To achieve this unpredictability, some randomization is typically employed. Modern cryptographic protocols often require frequent generation of random quantities. Cryptographic attacks that subvert or exploit weaknesses in this process are known as random number generator attacks.
A random password generator is software program or hardware device that takes input from a random or pseudo-random number generator and automatically generates a password. Random passwords can be generated manually, using simple sources of randomness such as dice or coins, or they can be generated using a computer.
In theoretical computer science and cryptography, a pseudorandom generator (PRG) for a class of statistical tests is a deterministic procedure that maps a random seed to a longer pseudorandom string such that no statistical test in the class can distinguish between the output of the generator and the uniform distribution. The random seed itself is typically a short binary string drawn from the uniform distribution.
In cryptography, a verifiable random function (VRF) is a public-key pseudorandom function that provides proofs that its outputs were calculated correctly. The owner of the secret key can compute the function value as well as an associated proof for any input value. Everyone else, using the proof and the associated public key, can check that this value was indeed calculated correctly, yet this information cannot be used to find the secret key.
A numeric sequence is said to be statistically random when it contains no recognizable patterns or regularities; sequences such as the results of an ideal dice roll or the digits of π exhibit statistical randomness.
Random number generation is a process by which, often by means of a random number generator (RNG), a sequence of numbers or symbols that cannot be reasonably predicted better than by random chance is generated. This means that the particular outcome sequence will contain some patterns detectable in hindsight but unpredictable to foresight. True random number generators can be hardware random-number generators (HRNGs), wherein each generation is a function of the current value of a physical environment's attribute that is constantly changing in a manner that is practically impossible to model. This would be in contrast to so-called "random number generations" done by pseudorandom number generators (PRNGs), which generate numbers that only look random but are in fact pre-determined—these generations can be reproduced simply by knowing the state of the PRNG.
In probability and statistics, a random variate or simply variate is a particular outcome of a random variable; the random variates which are other outcomes of the same random variable might have different values.
A randomness test, in data evaluation, is a test used to analyze the distribution of a set of data to see if it can be described as random (patternless). In stochastic modeling, as in some computer simulations, the hoped-for randomness of potential input data can be verified, by a formal test for randomness, to show that the data are valid for use in simulation runs. In some cases, data reveals an obvious non-random pattern, as with so-called "runs in the data". If a selected set of data fails the tests, then parameters can be changed or other randomized data can be used which does pass the tests for randomness.
In common usage, randomness is the apparent or actual lack of pattern or predictability in information. A random sequence of events, symbols or steps often has no order and does not follow an intelligible pattern or combination. Individual random events are, by definition, unpredictable, but if the probability distribution is known, the frequency of different outcomes over repeated events is predictable. For example, when throwing two dice, the outcome of any particular roll is unpredictable, but a sum of 7 will tend to occur twice as often as 4. In this view, randomness is not haphazardness; it is a measure of uncertainty of an outcome. Randomness applies to concepts of chance, probability, and information entropy.
OpenPuff Steganography and Watermarking, sometimes abbreviated OpenPuff or Puff, is a free steganography tool for Microsoft Windows created by Cosimo Oliboni and still maintained as independent software. The program is notable for being the first steganography tool that:
The ACORN or ″Additive Congruential Random Number″ generators are a robust family of PRNGs for sequences of uniformly distributed pseudo-random numbers, introduced in 1989 and still valid in 2019, thirty years later.
↑ Hansen, Mogens Herman (1991). The Athenian Democracy in the Age of Demosthenes: Structure, Principles, and Ideology. The Ancient World. Oxford, UK; Cambridge, MA: Blackwell. ISBN0631138226. OCLC22809482.
↑ "...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]
1 2 Dowlen, Oliver (2008). The Political Potential of Sortition: A Study of the Random Selection of Citizens for Public Office. The Luck of the Draw. Exeter, UK; Charlottesville, VA: Imprint Academic. ISBN9781845401795. OCLC213307148.
Carson, Lyn (2006). "Avoiding Ghettos of Like-Minded People: Random Selection and Organizational Collaboration". In Schuman, Sandy (ed.). Creating a Culture Of Collaboration: The International Association of Facilitators Handbook. Jossey-Bass Business & Management Series. San Francisco: Jossey-Bass. pp.419–434. ISBN0787981168. OCLC70659897.
Carson, Lyn; Lubensky, Ron (May 2009). "Appointments to Boards and Committees via Lottery, A Pathway to Fairness and Diversity". Journal of Public Affairs. 9 (2): 87–94. doi:10.1002/pa.317.
Carson, Lyn; Martin, Brian (1999). Random Selection in Politics. Westport, CT: Praeger. ISBN0275967026. OCLC41184996.
This page is based on this Wikipedia article Text is available under the CC BY-SA 4.0 license; additional terms may apply. Images, videos and audio are available under their respective licenses.
