HOME

TheInfoList




A numeric
sequence In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and t ...

sequence
is said to be statistically random when it contains no recognizable
pattern A pattern is a regularity in the world, in human-made design, or in abstract ideas. As such, the elements of a pattern repeat in a predictable manner. A geometric pattern is a kind of pattern formed of geometric Geometry (from the grc, ...

pattern
s or regularities; sequences such as the results of an ideal
dice roll
dice roll
or the digits of
π
π
exhibit statistical randomness. Statistical randomness does not necessarily imply "true"
randomness In common parlance, randomness is the apparent or actual lack of pattern A pattern is a regularity in the world, in human-made design, or in abstract ideas. As such, the elements of a pattern repeat in a predictable manner. A geometric pat ...
, i.e., objective unpredictability.
Pseudorandomness A pseudorandom sequence of numbers is one that appears to be statistically randomA 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, dice ...
is sufficient for many uses, such as statistics, hence the name ''statistical'' randomness. ''Global randomness'' and ''local randomness'' are different. Most philosophical conceptions of randomness are global—because they are based on the idea that "in the long run" a sequence looks truly random, even if certain sub-sequences would ''not'' look random. In a "truly" random sequence of numbers of sufficient length, for example, it is probable there would be long sequences of nothing but repeating numbers, though on the whole the sequence might be random. ''Local'' randomness refers to the idea that there can be minimum sequence lengths in which random distributions are approximated. Long stretches of the same numbers, even those generated by "truly" random processes, would diminish the "local randomness" of a sample (it might only be locally random for sequences of 10,000 numbers; taking sequences of less than 1,000 might not appear random at all, for example). A sequence exhibiting a pattern is not thereby proved not statistically random. According to principles of
Ramsey theory Ramsey theory, named after the British mathematician and philosopher Frank P. Ramsey, is a branch of mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related s ...
, sufficiently large objects must necessarily contain a given substructure ("complete disorder is impossible"). Legislation concerning
gambling Gambling (also known as betting) is the wagering something of Value (economics), value ("the stakes") on an Event (probability theory), event with an uncertain outcome with the intent of winning something else of value. Gambling thus requires ...
imposes certain standards of statistical randomness to
slot machine A slot machine (American English American English (AmE, AE, AmEng, USEng, en-US), sometimes called United States English or U.S. English, is the set of varieties of the English language native to the United States. Currently, American ...

slot machine
s.


Tests

The first tests for random numbers were published by M.G. Kendall and
Bernard Babington Smith Bernard Babington Smith (1905-1993) was an academic, wartime intelligence officer and amateur athlete. Early Life and education He was born on 26 October 1905 at 29 Hyde Park Gate, London, the son of Sir Henry Babington Smith and Lady Elizabeth ...
in the ''
Journal of the Royal Statistical Society The ''Journal of the Royal Statistical Society'' is a peer-reviewed Peer review is the evaluation of work by one or more people with similar competencies as the producers of the work ( peers). It functions as a form of self-regulation by qua ...
'' in 1938. They were built on statistical tools such as
Pearson's chi-squared test Pearson's chi-squared test (\chi^2) is a statistical test applied to sets of categorical data In statistics Statistics is the discipline that concerns the collection, organization, analysis, interpretation, and presentation of data. In app ...
that were developed to distinguish whether experimental phenomena matched their theoretical probabilities. Pearson developed his test originally by showing that a number of dice experiments by W.F.R. Weldon did not display "random" behavior. Kendall and Smith's original four tests were hypothesis tests, which took as their
null hypothesis In inferential statistics, the null hypothesis (often denoted ''H''0) is that there is no difference between two possibilities. The null hypothesis is that the observed difference is due to chance alone. Using statistical tests it is possible to ...
the idea that each number in a given random sequence had an equal chance of occurring, and that various other patterns in the data should be also distributed equiprobably. * The frequency test, was very basic: checking to make sure that there were roughly the same number of 0s, 1s, 2s, 3s, etc. * The serial test, did the same thing but for sequences of two digits at a time (00, 01, 02, etc.), comparing their observed frequencies with their hypothetical predictions were they equally distributed. * The poker test, tested for certain sequences of five numbers at a time (AAAAA, AAAAB, AAABB, etc.) based on hands in the game
poker Poker is a family of card games in which Card player, players betting (poker), wager over which poker hand, hand is best according to that specific game's rules in ways similar List of poker hands, to these rankings. While the earliest known f ...

poker
. * The gap test, looked at the distances between zeroes (00 would be a distance of 0, 030 would be a distance of 1, 02250 would be a distance of 3, etc.). If a given sequence was able to pass all of these tests within a given degree of significance (generally 5%), then it was judged to be, in their words "locally random". Kendall and Smith differentiated "local randomness" from "true randomness" in that many sequences generated with truly random ''methods'' might not display "local randomness" to a given degree — ''very'' large sequences might contain many rows of a single digit. This might be "random" on the scale of the entire sequence, but in a smaller block it would not be "random" (it would not pass their tests), and would be useless for a number of statistical applications. As random number sets became more and more common, more tests, of increasing sophistication were used. Some modern tests plot random digits as points on a three-dimensional plane, which can then be rotated to look for hidden patterns. In 1995, the statistician
George Marsaglia George Marsaglia (March 12, 1924 – February 15, 2011) was an American mathematician and computer scientist. He is best known for creating the diehard tests, a suite of software for measuring statistical randomness. Research on random numbers ...
created a set of tests known as the
diehard testsThe diehard tests are a battery of statistical tests for measuring the quality of a random number generator. They were developed by George Marsaglia over several years and first published in 1995 on a CD-ROM of random numbers. Test overview * Bir ...
, which he distributes with a
CD-ROM A CD-ROM (, compact disc read-only memory) is a pre-pressed optical compact disc The compact disc (CD) is a digital Digital usually refers to something using digits, particularly binary digits. Technology and computing Hardware *Digital ...

CD-ROM
of 5 billion
pseudorandom A pseudorandom sequence of numbers is one that appears to be statistically randomA 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, dice ...
numbers. In 2015,
Yongge Wang Yongge Wang (born 1967) is a computer science Computer science deals with the theoretical foundations of information, algorithms and the architectures of its computation as well as practical techniques for their application. Computer scie ...
distributed a Java software package for statistically distance based randomness testing.
Pseudorandom number generator A pseudorandom number generator (PRNG), also known as a deterministic random bit generator (DRBG), is an algorithm In and , an algorithm () is a finite sequence of , computer-implementable instructions, typically to solve a class of proble ...
s require tests as exclusive verifications for their "randomness," as they are decidedly ''not'' produced by "truly random" processes, but rather by deterministic algorithms. Over the history of random number generation, many sources of numbers thought to appear "random" under testing have later been discovered to be very non-random when subjected to certain types of tests. The notion of quasi-random numbers was developed to circumvent some of these problems, though pseudorandom number generators are still extensively used in many applications (even ones known to be extremely "non-random"), as they are "good enough" for most applications. Other tests: * The Monobit test treats each output bit of the random number generator as a coin flip test, and determine if the observed number of heads and tails are close to the expected 50% frequency. The number of heads in a coin flip trail forms a
binomial distribution In probability theory and statistics, the Binomial coefficient, binomial distribution with parameters ''n'' and ''p'' is the discrete probability distribution of the number of successes in a sequence of ''n'' statistical independence, indep ...

binomial distribution
. * The
Wald–Wolfowitz runs testThe Wald–Wolfowitz runs test (or simply runs test), named after statisticians Abraham Wald Abraham Wald (; hu, Wald Ábrahám, yi, אברהם וואַלד;  – ) was a Hungarian Jewish mathematician A mathematician is someone who uses ...
tests for the number of bit transitions between 0 bits, and 1 bits, comparing the observed frequencies with expected frequency of a random bit sequence. *
Information entropy In information theory Information theory is the scientific study of the quantification (science), quantification, computer data storage, storage, and telecommunication, communication of Digital data, digital information. The field was fun ...
*
Autocorrelation Autocorrelation, also known as serial correlation, is the correlation In , correlation or dependence is any statistical relationship, whether or not, between two s or . In the broadest sense correlation is any statistical association, th ...
test *
Kolmogorov–Smirnov test In statistics Statistics is the discipline that concerns the collection, organization, analysis, interpretation, and presentation of data Data (; ) are individual facts, statistics, or items of information, often numeric. In a mo ...
* Statistically distance based randomness test.
Yongge Wang Yongge Wang (born 1967) is a computer science Computer science deals with the theoretical foundations of information, algorithms and the architectures of its computation as well as practical techniques for their application. Computer scie ...
showed that NIST SP800-22 testing standards are not sufficient to detect some weakness in randomness generators and proposed statistically distance based randomness test. *
Spectral Density Estimation In statistical signal processing, the goal of spectral density estimation (SDE) is to estimate the spectral density (also known as the power spectral density) of a random signal from a sequence of time samples of the signal. Intuitively speaki ...
- performing a Fourier transform on a "random" signal transforms it into a sum of periodic functions in order to detect non random repetitive trends * Maurer's Universal Statistical Test * The
Diehard testsThe diehard tests are a battery of statistical tests for measuring the quality of a random number generator. They were developed by George Marsaglia over several years and first published in 1995 on a CD-ROM of random numbers. Test overview * Bir ...


See also

*
Algorithmic randomness Intuitively, an algorithmically random sequence (or random sequenceThe concept of a random sequence is essential in probability theory Probability theory is the branch of mathematics concerned with probability. Although there are several differe ...
*
Check Check or cheque, may refer to: Places * Check, Virginia Check is an unincorporated community in Floyd County, Virginia, Floyd County, Virginia, United States. Check is located on U.S. Route 221 northeast of Floyd, Virginia, Floyd. Check has a pos ...
ing *
Complete spatial randomness Complete spatial randomness (CSR) describes a point process whereby point events occur within a given study area in a completely random fashion. It is synonymous with a ''homogeneous spatial Poisson process''.O. Maimon, L. Rokach, ''Data Mining and ...
*
Normal number In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers ( and ), formulas and related structures (), shapes and spaces in which they are contained (), and quantities and their changes ( and ). There is no gen ...
*
One-time pad In cryptography Cryptography, or cryptology (from grc, , translit=kryptós "hidden, secret"; and ''graphein'', "to write", or ''-logia ''-logy'' is a suffix in the English language, used with words originally adapted from Ancient G ...

One-time pad
*
Randomness In common parlance, randomness is the apparent or actual lack of pattern A pattern is a regularity in the world, in human-made design, or in abstract ideas. As such, the elements of a pattern repeat in a predictable manner. A geometric pat ...
*
Randomness tests A randomness test (or test for randomness), 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 In common parlance, randomness is the apparent or actual lack of pattern or ...
*
Statistical hypothesis testing A statistical hypothesis test is a method of statistical inference Statistical inference is the process of using data analysis Data analysis is a process of inspecting, Data cleansing, cleansing, Data transformation, transforming, and Data ...
*
Seven states of randomness 350px, Stochastic process with random increments from a standard normal distribution. The seven states of randomness in probability theory, fractals and Probabilistic risk assessment, risk analysis are extensions of the concept of randomness as ...
* TestU01


References


External links


DieHarder
A free (
GPL The GNU General Public License (GNU GPL or simply GPL) is a series of widely used free software license A free-software license is a notice that grants the recipient of a piece of software extensive rights to modify and redistribute that ...
) C Random Number Test Suite.
Generating Normal Distributed Random Numbers
{{DEFAULTSORT:Statistical Randomness