Pseudorandomness

 related topics {math, number, function} {system, computer, user} {rate, high, increase} {math, energy, light} {food, make, wine} {disease, patient, cell} {car, race, vehicle} {war, force, army} {work, book, publish}

A pseudorandom process is a process that appears to be random but it is not. Pseudorandom sequences typically exhibit statistical randomness while being generated by an entirely deterministic causal process. Such a process is easier to produce than a genuine random one, and has the benefit that it can be used again and again to produce exactly the same numbers, useful for testing and fixing software.

To generate truly random numbers requires precise, accurate, and repeatable system measurements of absolutely non-deterministic processes. The open source operating system Linux uses, for example, various system timings (like user keystrokes, I/O, or least-significant digit voltage measurements) to produce a pool of random numbers. It attempts to constantly replenish the pool, depending on the level of importance, and so will issue a random number. This system is an example, and similar to those of dedicated hardware random number generators.

Contents

History

The generation of random numbers has many uses (mostly in statistics, for random sampling, and simulation). Before modern computing, researchers requiring random numbers would either generate them through various means (dice, cards, roulette wheels, 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 Leonard H.C. Tippet. In 1947, the RAND Corporation generated numbers by the electronic simulation of a roulette wheel; the results were eventually published in 1955 as A Million Random Digits with 100,000 Normal Deviates.

John von Neumann was a pioneer in computer-based random number generators. A notable contributor in the field of pseudo-random number generation in practical use is a Pakistani mathematician Dr. Arif Zaman. In 1951, Derrick Henry Lehmer invented the linear congruential generator, used in most pseudorandom number generators today. With the spread of the use of computers, algorithmic pseudorandom number generators replaced random number tables, and "true" random number generators (Hardware random number generators) are only used in a few cases.

Almost random

A pseudo-random variable is a variable which is created by a deterministic procedure (often a computer program or subroutine) which (generally) takes random bits as input. The pseudo-random string will typically be longer than the original random string, but less random (less entropic, in the information theory sense). This can be useful for randomized algorithms.