Salta al contenuto

Mese: Novembre 2018

Most common pseudorandom generators

A random number generator (RNG) is a device that generates a sequence of numbers or symbols that cannot be reasonably predicted better than by a random chance. Random number generators can be true hardware random-number generators (HRNG), which generate genuinely random numbers, or pseudo-random number generators (PRNG) which generate numbers which look random, but are actually deterministic, and can be reproduced if the state of the PRNG is known. So a pseudorandom number generator (PRNG), also known as a deterministic random bit generator (DRBG), is an algorithm for generating a sequence of numbers whose properties approximate the properties of sequences of random numbers. The PRNG-generated sequence is not truly random, because it is completely determined by an initial value, called the PRNG’s seed (which may include truly random values). There exist several computational methods for pseudo-random number generation, but all fall short of the goal of true randomness, although they may meet, with varying success, some of the statistical tests for randomness intended to measure how unpredictable their results are. The generation of pseudo-random numbers is an important and common task in computer programming. There are a couple of methods to generate a random number based on a probability density function. These methods involve transforming a uniform random number in some way. Because of this, these methods work equally well in generating both pseudo-random and truly random numbers. One method, called the inversion method, involves integrating up to an area greater than or equal to the random number (which should be generated between 0 and 1 for proper distributions). A second method, called the acceptance-rejection method, involves choosing an x and y value and testing whether the function of x is greater than y value. If it is, the x value is accepted. Otherwise, the x value is rejected and the algorithm tries again. Random numbers uniformly distributed between 0 and 1 can be used to generate random numbers of any desired distribution by passing them through the inverse cumulative distribution function (CDF) of the desired distribution (see Inverse transform sampling). Inverse CDFs are also called quantile functions. A PRNG suitable for cryptographic applications is called a cryptographically secure PRNG (CSPRNG). A requirement for a CSPRNG is that an adversary not knowing the seed has the only negligible advantage in distinguishing the generator’s output sequence from a random sequence. In other words, while a PRNG is only required to pass certain statistical tests, a…

Central Limit theorem and LLN

The Central Limit Theorem is one of the greatest results in probability theory because it says that the sum of a big number of variables has approximately a normal distribution. We define a set of random variables iid X1, X2, X3, … , Xn with mean μ and variance σ². Then if n is very big, the sum X1 + X2 + X3 + … + Xn is approximately normal with mean nμ and variance nσ². If we also normalize the sum we can say that (X1 + X2 + X3 + … + Xn – nμ)/(σ√n) is approximately a normal standard, so to a normal with mean 0 and variance 1. Look for the most popular distributions in statistics Distribution can be divided into two categories: discrete and continuous distributions. The most popular discrete distributions are: 1)    Boolean (Bernoulli) which takes value 1 with probability p and value 0 with probability q = 1 − p. 2)    Binomial which describes the number of successes in a series of independent Yes/No experiments all with the same probability of success 3)    Poisson which describes a very large number of individually unlikely events that happen in a certain time interval 4)    Hypergeometric which describes the number of successes in the first m of a series of n consecutive Yes/No experiments, if the total number of successes is known. This distribution arises when there is no replacement. The most popular continuous distributions are: 1)    Normal (or Gaussian) often used in the natural and social sciences to represent real-valued random variables 2)    Chi-squared which is the sum of the squares of n independent Gaussian random variables. It is a special case of the Gamma distribution 3)    Gamma which describes the time until n consecutive rare random events occur in a process with no memory 4)    Beta a family of two-parameter distributions with one mode, of which the uniform distribution is a special case, and which is useful in estimating success probabilities 5)    T-Student useful for estimating unknown means of Gaussian populations 6)    F-Distribution (Fisher) is a continuous probability distribution that arises frequently as the null distribution of a test statistic, most notably in the analysis of variance 7)    Weibull of which the exponential distribution is a special case is used to model the lifetime of technical devices and is used to describe the particle size distribution of particles generated by grinding, milling and crushing operations  

Derivation of the Chebyshev’s inequality and its application to prove the (weak) LLN

Derivation of the Chebyshev’s inequality and its application to prove the (weak) LLN The Chebyshev’s inequality is a direct derivation of the Markov’s inequality and it says that if we consider X as a random variable with mean μ and variance σ^2, then for every r > 0 we have that: P(|X – μ| >= r) <=  σ²/ r² Demonstration:  The events {| X – μ| > r} and {(X – μ)² >= r²} are the same and so their probability is  the same too. Since ( X – μ)^2 is a random variable not negative, then we can apply the Markov’s inequality with a = r^2, so that: P(|X – μ| >= r) = P((X – μ)² >= r²) <= (E[(X – μ)²])/r² =  σ²/ r² Chebyshev’s inequality is also used to demonstrate the weak law of large numbers. Let’s define X1, X2,. ..  Xn a succession of random variables i.i.d (independent and identically distributed) with mean μ. Then for every ε > 0, P ( |( X1 + X2+Xn )/n – μ|> ε) -> 0 when n -> to ∞ Demonstration: We prove this result with the additional hypothesis that the Xi random variables have variance limited to σ². Since the properties of mean and variance we’ve that: E[(X1 + X2 + … +Xn)/n] =  μ and Var((X1 + X2 +…+Xn)/n) = σ²/n So by applying the Chebyshev’s inequality to the random variable R = ( X1 + X2+Xn ) /n, we’ve that: P ( |( X1 + X2+Xn )/n – μ|> ε) <= σ²/nε² Since now for n -> ∞, σ²/nε² -> 0 the law is proved.