Research 8 -- Most common PRG

-

Random number generators are important in many fields, including physics, engineering, mathematics, computer science and cryptographic applications (where they play a crucial role in some situations). Random number generators can be divided in two main classes: true random number generators (TRNG), which typically make use of an unpredictable physical mean to generate numbers (e.g. atmospheric noises);  and pseudorandom number generators (PRNG), which uses a mathematical deterministic algorithm, computed on an initial value (aka the seed) to generate the random numbers.

Even though it should be obvious, is worth to insist on the fact that the choice of the random number generator strictly depend on what the generated numbers will be used for. For instance, not every PRG is good for cryptographic applications. Such a PRG should pass all the statistical tests another required condition is that an adversary, without knowing the seed, cannot distinguish its output from a truly random source with non-negligible probability.
Some non-secure random number generators can be constructed from any block cipher using CTR mode whereas some example of cryptographically secure PRG are the Blum-Micali algorithm, the Blum Blum Shub and the Naor-Reingold pseudorandom function.

That being said, let's consider random number generators that aren't good for cryptography but can be used in several application like statistics. There are several techniques used to generate a random number on a probability density function and they typically consists into modifying a uniform random number.

- Inversion method: integrating up to an area greater than or equal to the random number (which should belong to the range [0,1]).

- Acceptance-rejection: choose x and y and test whether the function of x is greater than the y value. If it is, the x value is accepted; otherwise it's rejected and the algorithm tried again.


Another common generator is the Box-Muller transform, which is a pseudorandom sampling method for generating pairs of independent, standard, normally distributed (zero mean, unit variance) random numbers, given a source of uniformly distributed random numbers. The method is expressed in two forms: the basic form takes two samples from the uniform distribution on the interval [0, 1] and maps them to two normally distributed samples whereas the polar form takes two samples from [-1, +1] and maps them to two samples without the use of sine or cosine functions.

Suppose U1 and U2 are independent samples chosen from the uniform distribution on the unit interval (0, 1). Let






Then Z0 and Z1 are independent random variables with a standard normal distribution.

Box-Mueller Transform -- Polar Form

The polar form is most widely used, in part due to its inclusion in an important series of books on algorithms and numerical analysis (Numerical Recipes).
Given u and v uniformly distributed in the closed interval [-1, +1], set s = R2 = u2 + v2.
If s = 0 or s ≥ 1, discard u and v, and try another pair.

Because u and v are uniformly distributed and because only points within the unit circle have been admitted, the values of s will be uniformly distributed in the open interval (0, 1), too.










Other PRGs


  • Lehmer generator (and LFSR, LCG)
  • Mersenne Twister 
The latter takes a seed of w bits as input and outputs integers in the range [0, 2w-1] using an algorithm which is based on a matrix linear recurrence over a finite binary field F2. The Mersenne Twister is the most used general-purpose PRNG, it's the default random number generators for several software systems including Python, Ruby and PHP.

Commenti

Posta un commento

Post popolari in questo blog

Welford Algorithm

-
Immagine
The variance is the expectation of the squared deviation of a random variable form its mean.  Informally, it measures how far a set of (random) numbers are spread out from their average value. The variance is the square of the standard deviation, the second central moment of a distribution and the covariance of the random variable with itself, and it is often represented by Var(X), σ 2 , s 2 . One of the most widely known formula for computing the variance is: where x-bar is the mean of the sample. The definition given above can be converted into an algorithm that computed the variance and the standard deviation in two passes: 1. Compute the mean                            (O(n)) 2. Compute the square differences       (O(n)) Output the variance Even though this algorithm seems working properly, it may become too expensive on some input instances. Just consider a sampling procedu...
Continua a leggere

Research 6 - Derivation of Chebyshev's inequality and its application to prove the (weak) LLN

-
Immagine
Chebyshev's Inequality In probability theory, the Chebyshev's inequality guarantees that, for a wide class of probability distributions, no more than a certain fraction of values can be more distant than a certain value from the mean. In particular, the mentioned inequality states that no more than 1/k 2 of the distribution's values can be more than k standard deviations away from the mean. In other words, this mean that at least (1 - 1/k 2 ) of the distribution's values are within k standard deviations of the mean. The Chebyshev's inequality can be easily derived from the Markov's inequality, where the latter defines an upper bound for the probability that a non-negative random variable is greater than (or equal to) some positive integer constant. Remember the Markov's inequality where   a  > 0 and  X  is a nonnegative random variable The Chebyshev inequality follows by considering the random variable ( X - E ( X )) 2  and the constant a 2...
Continua a leggere

Research 7 -- Central Limit Theorem, LLN, and most common probability distributions

-
Immagine
Law of Large Numbers and CLT Intuitively, everyone can be convinced of the fact that the average of many measurements of the same unknown quantity tends to give a better estimate than a single measurement. The law of the large numbers (LLN) and the central limit theorem (CLT) formalise this general ideas through mathematics and random variables. Suppose X 1 , X 2 , ..., X n are independent random variables with the same underlying distribution. In this case, we say that the X i are independent and identically-distributed (or, i.i.d.). In particular, the X i have all the same mean μ and standard deviation σ. The average of the i.i.d. variables is defined as: The central limit theorem states that when an infinite number of successive random samples are taken from a population, the sampling distribution of the means of those samples will become approximately normally distributed with mean μ and standard deviation σ/ √N as the sample size becomes larger, irrespective of the sh...
Continua a leggere