# easy definition of pseudorandomness

I'm trying to make some understanding of the Wikipedia definition of a pseudorandom number generator.

Can someone explain the intuition behind this definition (how is this describing "seeming randomness for polynomial time")?

• It's not $P(E)$ that's infinite but the cardinality of $E$. – kodlu Dec 22 '16 at 21:18
• @Kodlu, true. I was thinking in terms of general measures for some reason. Question is edited – Louis Dec 23 '16 at 2:00
• The accepted answer by Pornin to “What is the difference between CSPRNG and PRNG?” as well as the other answers there could be helpfull… – e-sushi Dec 23 '16 at 15:52
• I agree with e-sushi's comment, but I'd highlight epsfooling's answer to the same question. – Luis Casillas Jan 23 '17 at 1:06

A random sequence is not predictable (per Shannon's 'surprise' idea). Predictable by what technique, by which procedure, by what algorithm? There being no answer to that, we're on squishy ground. Shannon's approach was to apply the idea of entropy (stolen from thermo???) as a measure, though not exactly of random, as a random sequence (if we could be sure we had one) might have low entropy because it has little of his surprise factor. But, there are physical sources of randomness (if we could collect, measure, accumulate, them without bias; experimentalists should affirm the maddening reality of measurement error / bias / failure to act in reality as design expectation suggested). And there are mathematical objects with high randomness (as in the next digit is not more predictable than by chance), but low entropy.

We can test for randomness (or rather for some expected patterns -- the Diehard tests, for instance), but they are suggestive only, ruling out only some kinds of patterns (and so non-randomness) but not ruling out all possible patterning. In practice, we do the best we can. Monte Carlo methods may not require absolute randomness in some cases, for instance. Computers, being deterministic devices cannot produce truly random outputs, but they may be able to produce ones which are "random enough" for some purposes. These are called pseudo random sequences, and have a spotty record. RANDU, widely used for years in the IBM community, turned out to be embarrassingly patterned. Had anyone looked, it couldn't have continued in use for so long. The random number functions in libraries and compilers are too often inadequate for anything except one's kid sister's randomness needs.

Some applications require something rather closer to actual random (how to measure this is a conundrum, a real one), notably cryptography whose underlying assumptions rely heavily on the randomness inherent in this or that choice. So a cryptographically secure pseudo random generator is a higher level of performance requirement. And running one successfully on a deterministic device is a pretty remarkable achievement.

So defining pseudorandomness understandably is a bit tricky. Passing all of the Diehard tests (as modified and updated) might be enough for someone or some requirement, but not another. Knuth discussed this business at some length in Art of Computer Programming (vol 2, if I recall correctly) and his treatment will be rewarding.

Pseudo random not being actually random requires some discussion and understanding of the difference in various particular cases, and that's not easy. There's philosophy, mathematical foundations (consider any of assorted mathematical constants from e, to pi, to phi, to Chaitin's Omega, to ...), computer design and operation reality (consider Intel's random number generator design, for instance), and computer economic reality (eg, is a computer with infinite memory capable of more satisfactory pseudo random performance than a finite memory machine?), and so on. I don't think easy is possible, for most needs.

Generating a random number is an expensive (i.e. slow) operation. It can be done using atmosphere noise (random.org), comparing the parity of the number of ticks (on a certain amount of time) counted by two clocks or shuffling a deck of cards.

Since we need a more efficient implementation we can settle for pseudo-random number generators, which are faster and ensure some important properties, such as having in output a uniform distribution. A PRNG is a deterministic algorithm which produces a sequence of numbers having approximately the same statistical properties of a random process.

In order to begin the process we need an initial value (the initial condition if the system we're working on), the seed. This seed is a real random number produced in the ways specified above. In order to improve the sequence produced by the PRNG we can use more seed values: everytime we add a seed we add some true randomness to the PRNG. This makes obviously the computation more expensive; to factor in the purposes of a PRNG (efficiency is a fundamental property) is important to make sure that it isn't more expensive than directly picking real random numbers.

• Note that we do know how to reasonably fast produce perfectly random numbers using quantum physics or effects like thermal noise. – SEJPM Dec 23 '16 at 22:05

A simple pseudorandom generator would be to use a phone book. Whenever you needed a random number, use the first phone number in the book that's not crossed out. After you use the phone number, cross it out with a pencil. It would seem random. But if somebody knew you were using the phone book for random numbers, they could look at your last random number and predict what number you'd use next. This would not be good for an internet poker game. Also, there would be patterns in the numbers generated if you looked closely (such as same area code). A real random number generator wouldn't have those problems.