A pseudo-random number is a number belonging to a sequence which appears to be random, but can in fact be generated by a finite computation. They are used extensively in computer science in places where randomness is essential to some application, but cannot be generated due to computation being deterministic.
The qualities which are required of a pseudo-random sequence of (binary) digits -- if it is to be used in any application where apparent randomness is important -- are as follows:
the 2n different patterns of n successive digits should each occur about as often as each other
sequences of n(>1) 0s should occur about half as often as sequences of n-1 0s, and about as often as n 1s
A pseudorandom generator for such rectangles is a deterministic function maping short strings to elements in [m]^d such that these elements form a good sample space for approximating each rectangle's volume.
Pseudorandom generators for combinatorial rectangles have been actively studied for a while in theoretical computer science.
Explicit constructions of extractors have a variety of important applications, such as the simulation of randomized algorithms using weak random sources; the explicit construction of expanders and superconcentrators; randomness-efficient reduction of error in sampling and in randomized algorithms; and simpler proofs of certain complexity-theoretic results.
Feeds |
Contact