Generating Pseudorandom Numbers

Pseudorandom numbers are generated by deterministic algorithms. They are 'random' in the sense that, on average, they pass statistical tests regarding their distribution and correlation. They differ from true random numbers in that they are generated by an algorithm, rather than a truly random process.

Jun 03, 2012  For the Love of Physics - Walter Lewin - May 16, 2011 - Duration: 1:01:26. Lectures by Walter Lewin. They will make you ♥ Physics. Recommended for you. Modern cryptography addresses the long key issue by studying how to generate long keys from short ones. IAn e cient observer can only detect ignorable di erences between a generated key and a random key. Computational Complexity, by Y. FuPseudorandom Generator3 / 49.

Random number generators (RNGs) like those in MATLAB^® are algorithms for generating pseudorandom numbers with a specified distribution.

For more information on the GUI for generating random numbers from supported distributions, see Explore the Random Number Generation UI.

Common Pseudorandom Number Generation Methods

Methods for generating pseudorandom numbers usually start with uniform random numbers, like the MATLAB rand function produces. The methods described in this section detail how to produce random numbers from other distributions.

Direct Methods

Direct methods directly use the definition of the distribution.

For example, consider binomial random numbers. A binomial random number is the number of heads in $$N$$ tosses of a coin with probability $$p$$ of a heads on any single toss. If you generate $$N$$ uniform random numbers on the interval (0,1) and count the number less than $$p$$, then the count is a binomial random number with parameters $$N$$ and $$p$$.

/ubisoft-cd-key-generator-free-download.html. This function is a simple implementation of a binomial RNG using the direct approach:

For example:

The binornd function uses a modified direct method, based on the definition of a binomial random variable as the sum of Bernoulli random variables.

You can easily convert the previous method to a random number generator for the Poisson distribution with parameter $$\lambda$$. The Poisson Distribution is the limiting case of the binomial distribution as $$N$$ approaches infinity, $$p$$ approaches zero, and $$Np$$ is held fixed at $$\lambda$$. To generate Poisson random numbers, create a version of the previous generator that inputs $$\lambda$$ rather than $$N$$ and $$p$$, and internally sets $$N$$ to some large number and $$p$$ to $$\lambda /N$$.

The poissrnd function actually uses two direct methods:

• A waiting time method for small values of $$\lambda$$

• A method due to Ahrens and Dieter for larger values of $$\lambda$$

Inversion Methods

Inversion methods are based on the observation that continuous cumulative distribution functions (cdfs) range uniformly over the interval (0,1). If $$u$$ is a uniform random number on (0,1), then using $$X=F^{-1}(U)$$ generates a random number $$X$$ from a continuous distribution with specified cdf $$F$$.

For example, the following code generates random numbers from a specific Exponential Distribution using the inverse cdf and the MATLAB® uniform random number generator rand:

Compare the distribution of the generated random numbers to the pdf of the specified exponential by scaling the pdf to the area of the histogram used to display the distribution:

Inversion methods also work for discrete distributions. To generate a random number $$X$$ from a discrete distribution with probability mass vector $$P(X=x_i)=p_i$$ where $$x_0<x_1<x_2<...$$, generate a uniform random number $$u$$ on (0,1) and then set $$X=x_i$$ if $$F(x_{i-1})<u<F(x_i)$$.

For example, the following function implements an inversion method for a discrete distribution with probability mass vector $$p$$:

Use the function to generate random numbers from any discrete distribution:

Acceptance-Rejection Methods

The functional form of some distributions makes it difficult or time-consuming to generate random numbers using direct or inversion methods. Acceptance-rejection methods provide an alternative in these cases.

Acceptance-rejection methods begin with uniform random numbers, but require an additional random number generator. If your goal is to generate a random number from a continuous distribution with pdf $$f$$, acceptance-rejection methods first generate a random number from a continuous distribution with pdf $$g$$ satisfying $$f(x)\le cg(x)$$ for some $$c$$ and all $$x$$.

A continuous acceptance-rejection RNG proceeds as follows:

1. Chooses a density $$g$$.

2. Finds a constant $$c$$ such that $$f(x)/g(x)\le c$$ for all $$x$$.

3. Generates a uniform random number $$u$$.

4. Generates a random number $$v$$ from $$g$$.

5. If $$cu\le f(v)/g(v)$$, accepts and returns $$v$$. Otherwise, rejects $$v$$ and goes to step 3.

For efficiency, a 'cheap' method is necessary for generating random numbers from $$g$$, and the scalar $$c$$ should be small. The expected number of iterations to produce a single random number is $$c$$.

The following function implements an acceptance-rejection method for generating random numbers from pdf $$f$$ given $$f$$, $$g$$, the RNG grnd for $$g$$, and the constant $$c$$:

For example, the function $$f(x)=x{e}^{-x^2/2}$$ satisfies the conditions for a pdf on $$[0,\infty )$$ (nonnegative and integrates to 1). The exponential pdf with mean 1, $$f(x)=e^{-x}$$, dominates $$g$$ for $$c$$ greater than about 2.2. Thus, you can use rand and exprnd to generate random numbers from $$f$$:

The pdf $$f$$ is actually a Rayleigh Distribution with shape parameter 1. This example compares the distribution of random numbers generated by the acceptance-rejection method with those generated by raylrnd:

The raylrnd function uses a transformation method, expressing a Rayleigh random variable in terms of a chi-square random variable, which you compute using randn.

Acceptance-rejection methods also work for discrete distributions. In this case, the goal is to generate random numbers from a distribution with probability mass $$P_p(X=i)=p_i$$, assuming that you have a method for generating random numbers from a distribution with probability mass $$P_q(X=i)=q_i$$. The RNG proceeds as follows:

Pseudo Random Number Generator Algorithm

1. Chooses a density $$P_q$$.

2. Finds a constant $$c$$ such that $$p_i/q_i\le c$$ for all $$i$$.

3. Generates a uniform random number $$u$$.

4. Generates a random number $$v$$ from $$P_q$$.

5. If $$cu\le p_v/q_v$$, accepts and returns $$v$$. Otherwise, rejects $$v$$ and goes to step 3.

Pseudo Random Number Generator Formula

Related Topics

A pseudorandom process produces predictable outcomes given information which is typically difficult to acquire; absent such information, pseudorandom sequences of numbers exhibit statistical randomness.

In general, a random process generates unpredictable outcomes: for any single event any particular outcome cannot be predicted in advance given available information. For example, consider an unbiased coin which on any given flip is either heads or tails: on a single flip no outcome is certain. Recording 1,000 flips in a logbook provides a sequence of pseudorandom outcomes: in possession of the logbook each outcome is known for certain; however, a person without the logbook sees only a random string of heads and tails.

To generate random numbers that can never be predicted by any observer requires a causally non-deterministic process where events are not fully determined by prior states (e.g., whether a photon is emitted by an atom in any given nanosecond). Due to the physical impossibility of acquiring sufficient information to predict the outcome of such an event, its outcomes are guaranteed to be random to all.

Randomness is therefore a condition which holds of a sequence relative to the information available to the predictor, with pseudorandomness indicating that information sufficient to predict the next outcome may be acquired by the predictor under some circumstances. The most prominent example is the pseudorandom number generators used by digital computers in which knowing a starting 'seed' number produces an entirely predictable string of numbers which are unpredictable without it.

History[edit]

The generation of random numbers has many uses (mostly in statistics, for random sampling, and simulation). Before modern computing, researchers requiring random numbers would either generate them through various means (dice, cards, roulette wheels,^[1] etc.) or use existing random number tables.

The first attempt to provide researchers with a ready supply of random digits was in 1927, when the Cambridge University Press published a table of 41,600 digits developed by L.H.C. Tippett. In 1947, the RAND Corporation generated numbers by the electronic simulation of a roulette wheel;^[1] the results were eventually published in 1955 as A Million Random Digits with 100,000 Normal Deviates.

Almost random[edit]

A pseudorandom variable is a variable which is created by a deterministic algorithm, often a computer program or subroutine, which in most cases takes random bits as input. The pseudorandom string will typically be longer than the original random string, but less random (less entropic in the information theory sense). This can be useful for randomized algorithms.

Pseudorandom number generators are widely used in such applications as computer modeling (e.g., Markov chains), statistics, experimental design, etc.

Linux uses various system timings (like user keystrokes, I/O, or least-significant digit voltage measurements) to produce a pool of random numbers. It attempts to constantly replenish the pool, depending on the level of importance, and so will issue a random number.

In computational complexity[edit]

In theoretical computer science, a distribution is pseudorandom against a class of adversaries if no adversary from the class can distinguish it from the uniform distribution with significant advantage.^[2]This notion of pseudorandomness is studied in computational complexity theory and has applications to cryptography.

Formally, let S and T be finite sets and let F = {f: S → T} be a class of functions. A distributionD over S is ε-pseudorandom against F if for every f in F, the statistical distance between the distributions f(X), where X is sampled from D, and f(Y), where Y is sampled from the uniform distribution on S, is at most ε.

In typical applications, the class F describes a model of computation with bounded resourcesand one is interested in designing distributions D with certain properties that are pseudorandom against F. The distribution D is often specified as the output of a pseudorandom generator.

Cryptography[edit]

Though random numbers are needed in cryptography, the use of pseudorandom number generators (whether hardware or software or some combination) is insecure. When random values are required in cryptography, the goal is to make a message as hard to crack as possible, by eliminating or obscuring the parameters used to encrypt the message (the key) from the message itself or from the context in which it is carried. Pseudorandom sequences are deterministic and reproducible; all that is required in order to discover and reproduce a pseudorandom sequence is the algorithm used to generate it and the initial seed. So the entire sequence of numbers is only as powerful as the randomly chosen parts—sometimes the algorithm and the seed, but usually only the seed.

There are many examples in cryptographic history of ciphers, otherwise excellent, in which random choices were not random enough and security was lost as a direct consequence. The World War IIJapanesePURPLE cipher machine used for diplomatic communications is a good example. It was consistently broken throughout World War II, mostly because the 'key values' used were insufficiently random. They had patterns, and those patterns made any intercepted traffic readily decryptable. Had the keys (i.e., the initial settings of the stepping switches in the machine) been made unpredictably (i.e., randomly), that traffic would have been much harder to break, and perhaps even secure in practice.^[3]

In security[edit]

Since pseudorandom numbers are in fact deterministic, a given seed will always determine the same pseudorandom number. This attribute is used in security, in the form of rolling code to avoid replay attacks, in which a command would be intercepted to be used by a thief at a later time.^[4]

Monte Carlo method simulations[edit]

A Monte Carlo method simulation is defined as any method that utilizes sequences of random numbers to perform the simulation. Monte Carlo simulations are applied to many topics including quantum chromodynamics, cancer radiation therapy, traffic flow, stellar evolution and VLSI design. All these simulations require the use of random numbers and therefore pseudorandom number generators, which makes creating random-like numbers very important.

A simple example of how a computer would perform a Monte Carlo simulation is the calculation of π. If a square enclosed a circle and a point were randomly chosen inside the square the point would either lie inside the circle or outside it. If the process were repeated many times, the ratio of the random points that lie inside the circle to the total number of random points in the square would approximate the ratio of the area of the circle to the area of the square. From this we can estimate pi, as shown in the Python code below utilizing a SciPy package to generate pseudorandom numbers with the MT19937 algorithm. Note that this method is a computationally inefficient way to numerically approximate π.

See also[edit]

References[edit]

1. ^ ^ab'A Million Random Digits'. RAND Corporation. Retrieved 2017-03-30.
2. ^Oded Goldreich. Computational Complexity: A Conceptual Perspective. Cambridge University Press. 2008.
3. ^Alberto-Perez. 'How the U.S. Cracked Japan's 'Purple Encryption Machine' at the Dawn of World War II'. io9. Retrieved 2017-03-30.
4. ^Brain, M., 'How Remote Entry Works', HowStuffWorks Auto Auto Basics. Retrieved July 8, 2018.

Further reading[edit]

• Donald E. Knuth (1997) The Art of Computer Programming, Volume 2: Seminumerical Algorithms (3rd edition). Addison-Wesley Professional, ISBN0-201-89684-2
• Oded Goldreich. (2008) Computational Complexity: a conceptual perspective. Cambridge University Press. ISBN978-0-521-88473-0.^{[page needed]}(Limited preview at Google Books)
• Vadhan, S. P. (2012). 'Pseudorandomness'. Foundations and Trends in Theoretical Computer Science. 7: 1–336. doi:10.1561/0400000010.

External links[edit]

• In RFC 1750, the use of pseudorandom number sequences in cryptography is discussed at length.

Pseudorandom Number Generator Key Generation Free