View source for Pseudorandomness

{{Use American English|date=March 2019}}
{{Use MDY dates|date=July 2020}}
{{Short description|Appearing random but actually being generated by a deterministic, causal process}}
A '''pseudorandom''' sequence of numbers is one that appears to be [[Statistical randomness|statistically random]], despite having been produced by a completely [[Deterministic system|deterministic]] and repeatable process.<ref name=RandomArticle_Phys.NYT2001>{{cite news |newspaper=[[The New York Times]] |url=https://www.nytimes.com/2001/06/12/science/connoisseurs-of-chaos-offer-a-valuable-product-randomness.html |title=Connoisseurs of Chaos Offer A Valuable Product: Randomness |author=George Johnson |date=June 12, 2001}}</ref> [[Pseudorandom number generator]]s are often used in computer programming, as traditional sources of randomness available to humans (such as rolling dice) rely on physical processes not readily available to computer programs, although developments in [[hardware random number generator]] technology have challenged this.

==Background==
The generation of random numbers has many uses, such as for [[sampling (statistics)|random sampling]], [[Monte Carlo methods]], [[board game]]s, or [[gambling]].  In [[physics]], however, most processes, such as gravitational acceleration, are deterministic, meaning that they always produce the same outcome from the same starting point.  Some notable exceptions are [[radioactive decay]] and [[quantum measurement]], which are both modeled as being truly random processes in the underlying physics.  Since these processes are not practical sources of random numbers, pseudorandom numbers are used, which ideally have the unpredictability of a truly random sequence, despite being generated by a deterministic process.<ref>{{cite book |title=Pseudorandomness|quote=pseudorandomness, the theory of efficiently generating objects that “look random” despite being constructed using little or no randomness|author=S. P. Vadhan |year=2012}}</ref>

In many applications, the deterministic process is a [[algorithm|computer algorithm]] called a [[pseudorandom number generator]], which must first be provided with a number called a [[random seed]].  Since the same seed will yield the same sequence every time, it is important that the seed be well chosen and kept hidden, especially in [[computer security|security]] applications, where the pattern's unpredictability is a critical feature.<ref>{{cite news |newspaper=BBC |title=Web's random numbers are too weak, researchers warn |url=https://www.bbc.com/news/technology-33839925|author=Mark Ward |date=August 9, 2015}}</ref>

In some cases where it is important for the sequence to be demonstrably unpredictable, physical sources of random numbers have been used, such as radioactive decay, atmospheric electromagnetic noise harvested from a radio tuned between stations, or intermixed timings of [[keystroke dynamics|keystrokes]].<ref name=RandomArticle_Phys.NYT2001/><ref name=RandomArticle.SS1998>{{cite magazine |magazine=Sun Server |title=Javatalk: Horseshoes, hand grenades and random numbers |author=Jonathan Knudson |date=January 1998 |pages=16–17}}</ref> The time investment needed to obtain these numbers leads to a compromise: using some of these physics readings as a seed for a pseudorandom number generator.

==History==
Before modern computing, researchers requiring random numbers would either generate them through various means ([[dice]], [[playing cards|cards]], [[roulette|roulette wheels]],<ref name=":0" /> etc.) or use existing random number tables.

The first attempt to provide researchers with a ready supply of random digits was in 1927, when the Cambridge University Press published a table of 41,600 digits developed by [[L.H.C. Tippett]]. In 1947, the [[RAND Corporation]] generated numbers by the electronic simulation of a roulette wheel;<ref name=":0">{{Cite web|url=http://www.rand.org/pubs/monograph_reports/MR1418/index2.html|title=A Million Random Digits|date=January 2001 |publisher=RAND Corporation|access-date=2017-03-30}}</ref> the results were eventually published in 1955 as ''[[A Million Random Digits with 100,000 Normal Deviates]]''.

==In computational complexity==
In [[theoretical computer science]], a [[probability distribution|distribution]] is '''pseudorandom''' against a class of adversaries if no adversary from the class can distinguish it from the uniform distribution with significant advantage.<ref>Oded Goldreich. Computational Complexity: A Conceptual Perspective. Cambridge University Press. 2008.</ref>
This notion of pseudorandomness is studied in [[computational complexity theory]] and has applications to [[cryptography]].

Formally, let ''S'' and ''T'' be finite sets and let '''F''' = {''f'': ''S'' → ''T''} be a class of functions.  A [[probability distribution|distribution]] '''D''' over ''S'' is ε-'''pseudorandom''' against '''F''' if for every ''f'' in '''F''', the [[total variation distance|statistical distance]] between the distributions <math>f(X)</math> and <math>f(Y)</math>, where <math>X</math> is sampled from '''D''' and <math>Y</math> is sampled from the [[uniform distribution (discrete)|uniform distribution]] on ''S'', is at most ε.

In typical applications, the class '''F''' describes a model of computation with bounded resources and one is interested in designing distributions '''D''' with certain properties that are pseudorandom against '''F'''.  The distribution '''D''' is often specified as the output of a [[pseudorandom generator]].<ref>{{cite web|url=https://people.seas.harvard.edu/~salil/pseudorandomness/pseudorandomness-Aug12.pdf|title=Pseudorandomness}}</ref>

==See also==
* {{annotated link|Assortativity}}
* {{annotated link|Cryptographically secure pseudorandom number generator}}
* {{annotated link|List of random number generators}}
* {{annotated link|Pseudorandom binary sequence}}
* {{annotated link|Pseudorandom ensemble}}
* {{annotated link|Pseudorandom number generator}}
* {{annotated link|Low-discrepancy sequence}}
* {{annotated link|Random number generation}}
* {{annotated link|Pseudorandom noise}}
* {{annotated link|Transfinite number}}

==Further reading==
* Donald E. Knuth (1997) ''[[The Art of Computer Programming]], Volume 2: Seminumerical Algorithms (3rd edition)''. Addison-Wesley Professional, {{isbn|0-201-89684-2}}
* {{cite book|first=Oded|last=Goldreich|year=2008|url=https://books.google.com/books?id=EuguvA-w5OEC|title=Computational Complexity: A Conceptual Perspective|publisher=Cambridge University Press|isbn=978-0-521-88473-0}} See especially Chapter 8: Pseudorandom generators, pp. 284–348, and Appendix C.2: Pseudorandomness, pp. 490–493.
* {{Cite journal | last1 = Vadhan | first1 = S. P. | doi = 10.1561/0400000010 | title = Pseudorandomness | journal = Foundations and Trends in Theoretical Computer Science | volume = 7 | pages = 1–336 | year = 2012 | issue = 1–3 }}

== External links ==
* [http://www.fourmilab.ch/hotbits HotBits: Genuine random numbers, generated by radioactive decay]
* [https://web.archive.org/web/20051023025710/http://www.merrymeet.com/jon/usingrandom.html Using and Creating Cryptographic-Quality Random Numbers]
* In RFC 4086, the use of pseudorandom number sequences in cryptography is discussed at length.{{Ref RFC|4086}}

==References==
<references/>

[[Category:Pseudorandomness| ]]
[[Category:Theoretical computer science]]