Pseudorandomness

Content sourced from Wikipedia, licensed under CC BY-SA 3.0.

Pseudorandomness: a short, simple explanation

What it is
- A pseudorandom sequence looks random, but it is produced by a deterministic process.
- A computer usually uses a pseudorandom number generator (PRNG) that starts with a seed. The same seed always produces the same sequence.
- Good seeds and strong algorithms make the sequence hard to predict, which is important for security and many programs.

Why it’s used
- True randomness from physical processes exists (like radioactive decay), but it can be slow or impractical to use directly.
- Pseudorandom numbers are fast and convenient for programming, simulations, games, and many other tasks.
- In security, unpredictability matters a lot, so seeds must be kept secret and PRNGs must be carefully designed.

Background
- Random numbers are needed for sampling, Monte Carlo methods, and games. Many physical processes are deterministic, so we rely on pseudorandomness to imitate randomness.
- When high-quality true randomness is not feasible, pseudorandom sequences provide a good substitute that behaves like randomness in practice.

History in brief
- Before computers, people generated random digits with dice, cards, or roulette.
- In 1927, Tippett published a table of many random digits.
- In the 1940s–1950s, RAND and others produced random-looking numbers by simulating physical processes, with a famous result published as A Million Random Digits with 100,000 Normal Deviates (1955).

In computational complexity
- Pseudorandomness studies when a distribution D “looks” random to observers who are limited by computing power.
- A distribution is ε-pseudorandom against a class F if no function in F can distinguish samples from D from samples drawn uniformly, by more than ε advantage.
- This idea helps explain why certain distributions can replace true randomness in cryptography and other areas.
- In practice, pseudorandomness is often achieved with a pseudorandom generator, which stretches a short seed into a long, seemingly random sequence.

Key takeaway
- Pseudorandomness lets computers use deterministic processes to produce numbers that behave like randomness, which is essential for many algorithms and for keeping certain systems secure.