NationMaster - Encyclopedia: Random Number Generator

A random number generator is a computational or physical device designed to generate a sequence of elements (usually numbers), such that the sequence can be used as a random one. Methods for generating random results have existed since ancient times, in the form of dice and coin flipping, the shuffling of playing cards, the use of yarrow stalks in the I Ching, and many other methods. The usual tests of such sequences for randomness attempt to ensure that they do not have any (or less rigorously, no easily discernible) patterns. A number is an abstract entity that represents a count or measurement. ... // About Bees This article is about completely random and illogical things. ... Typical role-playing dice, showing a variety of colors and styles. ... Coin flipping or coin tossing is the practice of throwing a coin in the air to resolve a dispute between two parties or otherwise choose between two alternatives. ... The term shuffle can also refer to the act of dragging ones feet on the ground while walking, running, or dancing. ... Some typical Anglo-American playing cards. ... Alternative meaning: I Ching (monk) The I Ching (Traditional Chinese: 易經, pinyin y jīng; Cantonese IPA: jɪk6gɪŋ1; Cantonese Jyutping: jik6ging1; alternative romanizations include I Jing, Yi Ching, Yi King) is the oldest of the Chinese classic texts. ...

"True" random numbers vs. pseudo-random numbers

How to distinguish a "true" random number from something else is often difficult to decide, since the concept of randomness is itself somewhat difficult to define. What is universally agreed is that any "random number generator" based solely on deterministic computation cannot be regarded as a "true" random number generator, since its output is inherently predictable. John von Neumann once famously said "Anyone who uses arithmetic methods to produce random numbers is in a state of sin", thus neatly summarizing the situation. A pseudorandom number generator (PRNG) is an algorithm that generates a sequence of numbers, the elements of which are approximately independent of each other. ... The word random is used to express apparent lack of purpose, cause, or order. ... John von Neumann in the 1940s. ...

However, under some circumstances, carefully chosen pseudo-random number generators can be used instead of true random numbers in some applications. Rigorous numerical analysis is often needed to have confidence Numerical analysis is the study of algorithms for the problems of continuous mathematics (as distinguished from discrete mathematics). ...

Random numbers in computing

Most computer programming languages include functions (or library routines) that purport to be random number generators. They are usually designed to provide a floating point number uniformly distributed between 0 and 1. A floating-point number is a digital representation for a number in a certain subset of the rational numbers, and is often used to approximate an arbitrary real number on a computer. ... In mathematics, the continuous uniform distributions are probability distributions such that all intervals of the same length are equally probable. ...

Such functions are necessarily deterministic, and therefore not truly random; furthermore, they too often have poor statistical properties and sometimes will repeat patterns after only tens of thousands of trials. They are sometimes initialized using a computer's real time clock, which may provide enough randomness for such things as game play, but they should never be used for many purposes, especially cryptographic applications. Better random numbers can be produced by using clock drift measurements. Even higher quality random number sources are available on most operating systems; see, for example /dev/random on various BSD flavors, Linux, Mac OS-X, Solaris, or this note for Microsoft Windows. A real-time clock (RTC) is a computer clock (most often in the form of an integrated circuit chip) that keeps track of the current time even when the computer is turned off. ... Clock drift refers to several related phenomena where a clock does not run in the exact right speed compared to another clock. ... In Unix-like operating systems, /dev/random is a special file that serves as a pseudorandom number generator which allows access to environmental noise collected from device drivers and other sources. ...

Generating random numbers from physical processes

There is general agreement that, if there are such things as "true" random numbers, they are most likely to be found by looking at physical processes which are, as far as we know, unpredictable. In computing, a hardware random number generator is an apparatus that generates random numbers from a physical process. ...

A physical random number generator is based on an essentially random atomic or subatomic physical phenomenon which are aspects of quantum mechanics. Examples of such phenomena include radioactive decay, thermal noise, shot noise and clock drift. Radioactive decay is the set of various processes by which unstable atomic nuclei (nuclides) emit subatomic particles (radiation). ... Johnson-Nyquist noise (sometimes thermal noise, Johnson noise or Nyquist noise) is the noise generated by the equilibrium fluctuations of the electric current inside an electrical conductor, which happens without any applied voltage, due to the random thermal motion of the charge carriers (the electrons). ... Shot noise is a type of noise that occurs when the finite number of particles that carry energy, such as electrons in an electronic circuit or photons in an optical device, gives rise to detectable statistical fluctuations in a measurement. ... Clock drift refers to several related phenomena where a clock does not run in the exact right speed compared to another clock. ...

Physical random number generators that rely on quantum mechanical processes have the advantage that the sequences they produce are completely unpredictable. Fig. ...

To provide a degree of randomness intermediate between specialized hardware on the one hand and algorithmic generation (without the expense of a hardware implementation) on the other, some security related computer software requires the user to input a lengthy string of mouse movements, and/or keyboard input, or both as 'randomly' as can be managed.

Post-processing and statistical checks

Even given sources of plausible random numbers (perhaps from a quantum mechanically based hardware generator), obtaining numbers which are completely unpredictable and unbiased is very difficult. Since random number generators are designed to be unpredictable, it is difficult to ensure that they are being predictably unpredictable. For example, many hardware random number generators generate sequences of numbers around certain areas rather than having uniform distribution across all possibilities. In addition, behavior of these generators often changes with temperature, power supply voltage, the age of the device, or other outside interference. And a software bug in a pseudo-random number routine, or a hardware bug in the hardware it runs on, may be similarly difficult to detect.

For these reasons, random numbers are generally subjected to statistical tests before use (to ensure that the underlying source is still working), and then post-processed to improve their statistical properties. Especially paranoid users may test them again, to ensure there are no detectable patterns.

Random numbers uniformly distributed between 0 and 1 can be used to generate random numbers of any desired distribution by passing them through the inverse cumulative distribution function of the desired distribution. To generate a pair of independent standard normally distributed random numbers (x, y), one may first generate the polar coordinates (r, θ), where r~χ₂² and θ~UNIFORM(0,2π). In probability theory, the cumulative distribution function (abbreviated cdf) completely describes the probability distribution of a real-valued random variable, X. For every real number x, the cdf is given by where the right-hand side represents the probability that the random variable X takes on a value less than... The normal distribution, also called Gaussian distribution, is an extremely important probability distribution in many fields. ... This article describes some of the common coordinate systems that appear in elementary mathematics. ... In probability theory and statistics, the chi-square distribution (also chi-squared distribution), or Ï‡2 distribution, is one of the theoretical probability distributions most widely used in inferential statistics, i. ... In mathematics, the continuous uniform distributions are probability distributions such that all intervals of the same length are equally probable. ...

Also, when using random numbers, care must be taken to consider whether they include or exclude their upper and lower bounds. Some 0 to 1 RNGs include 0 but exclude 1, while others include or exclude both.

If you have access to many independent RNGs, combining their outputs (using, for example, XOR) will provide a combined RNG at least as good as the best RNG you have access to. More details about uncorrelated near random bit streams. Exclusive disjunction (usual symbol xor) is a logical operator that results in true if one of the operands (not both) is true. ... In computing, a hardware random number generator is an apparatus that generates random numbers from a physical process. ...

Computational and hardware random number generators are commonly combined to reflect the benefits of both kinds. Computational random number generators can typically generate pseudo-random numbers much faster than physical generators can generate true randomness.

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 die roll, or the digits of Pi (as far as we can tell) exhibit statistical randomness. ...

Uses of random numbers

Random number generators have several important applications in gambling, statistical sampling, computer simulation, etc. Randomness has many uses in gambling, divination, statistics, cryptography, art, etc. ... Slot machines in Las Vegas, Nevada. ... Sampling is that part of statistical practice concerned with the selection of individual observations intended to yield some knowledge about a population of concern, especially for the purposes of statistical inference. ... A computer simulation or a computer model is a computer program that attempts to simulate an abstract model of a particular system. ...

Note that, in general, in applications where human fraud or adversaries exist, hardware-generated numbers should be used in preference to pseudo-random number generators.

Low-discrepancy sequences as an alternative

Some computations making use of a random number generator can be summarized as the computation of a total or average value, such as the computation of integrals by the Monte Carlo method. For such problems, it may be possible to find a more accurate solution by the use of so-called low-discrepancy sequences, also called quasirandom numbers. Such sequences have a definite pattern that fills in gaps evenly, qualitatively speaking; a truly random sequence may, and usually does, leave larger gaps. Monte Carlo methods are a widely used class of computational algorithms for simulating the behavior of various physical and mathematical systems. ... In mathematics, a low-discrepancy sequence is a sequence with the property that for all N, the subsequence x1, ..., xN is almost uniformly distributed (in a sense to be made precise), and x1, ..., xN+1 is almost uniformly distributed as well. ... In mathematics, a low-discrepancy sequence is a sequence with the property that for all N, the subsequence x1, ..., xN is almost uniformly distributed (in a sense to be made precise), and x1, ..., xN+1 is almost uniformly distributed as well. ...

Contents

"True" random numbers vs. pseudo-random numbers

Random numbers in computing

Generating random numbers from physical processes

Post-processing and statistical checks

Uses of random numbers

Low-discrepancy sequences as an alternative

See also

External links

Contents

"True" random numbers vs. pseudo-random numbers GA_googleFillSlot("encyclopedia_square");

Random numbers in computing

Generating random numbers from physical processes

Post-processing and statistical checks

Uses of random numbers

Low-discrepancy sequences as an alternative

See also

External links

"True" random numbers vs. pseudo-random numbers