Solved – How to generate numbers based on an arbitrary discrete distribution

distributions

How do I generate numbers based on an arbitrary discrete distribution?

For example, I have a set of numbers that I want to generate. Say they are labelled from 1-3 as follows.

1: 4%, 2: 50%, 3: 46%

Basically, the percentages are probabilities that they will appear in the output from the random number generator. I have a pesudorandom number generator that will generate a uniform distribution in the interval [0, 1]. Is there any way of doing this?

There are no bounds on how many elements I can have, but the % will add up to 100%.

Best Answer

One of the best algorithms for sampling from a discrete distribution is the alias method.

The alias method (efficiently) precomputes a two-dimensional data structure to partition a rectangle into areas proportional to the probabilities.

In this schematic from the referenced site, a rectangle of unit height has been partitioned into four kinds of regions--as differentiated by color--in the proportions $1/2$, $1/3$, $1/12$, and $1/12$, in order to sample repeatedly from a discrete distribution with these probabilities. The vertical strips have a constant (unit) width. Each is divided into just one or two pieces. The identities of the pieces and the locations of the vertical divisions are stored in tables accessible via the column index.

The table can be sampled in two simple steps (one for each coordinate) requiring generating just two independent uniform values and $O(1)$ calculation. This improves on the $O(\log(n))$ computation needed to invert the discrete CDF as described in other replies here.

Related Solutions

Solved – Random number generation distributed like a translated weibull from uniform random generator

What the commenters are saying is this:

If $T$ is your translated Weibull, then you can generate variates $t_i$ from the translated Weibull with the following: $$t_i = \theta + \lambda(-\ln(1-x_i))^{1/k}\ ,$$ where the $x_i$ are your uniform random numbers.

Random Number Generation – Generate Random Numbers from Sloped Uniform Distribution Using Mathematical Theory

Your deriviation is ok. Note that to get a positive density on $(0,B)$, you have to constraint $$ B^2 \tan\phi < 2. $$ In your code $B = 25$ so you should take $\phi$ between $\pm\tan^{-1}{2\over 625}$, that's where your code fails.

You can (and should) avoid using a quadratic solver, and then select the roots between 0 and $B$. The quadratic polynomial equation in $x$ to be solved is $$F(x) = t$$ with $$ F(x) = {1\over 2} \tan \phi \cdot x^2 + \left( {1\over B} - {B\over 2} \tan \phi \right) x.$$ By construction $F(0) = 0$ and $F(B) = 1$; also $F$ increases on $(0,B)$.

From this it is easy to see that if $\tan \phi > 0$, the portion of parabola in which we are interested is a part of the right side of the parabola, and the root to keep is the highest of the two roots, that is $$ x = {1\over \tan \phi} \left( {B\over 2} \tan \phi - {1\over B} + \sqrt{ \left( {B\over 2} \tan \phi - {1\over B} \right)^2 + 2 \tan \phi \cdot t}. \right)$$ To the contrary, if $\tan\phi < 0$, the parabola is upside down, and we are interest in its left part. The root to keep is the lowest one. Taking into account the sign of $\tan\phi$ it appears that this is the same root (ie the one with $+\sqrt\Delta$) than in the first case.

Here is some R code.

phi <- pi/8; B <- 2
f <- function(t) (-(1/B - 0.5*B*tan(phi)) + 
       sqrt( (1/B - 0.5*B*tan(phi))**2 + 2 * tan(phi) * t))/tan(phi)
hist(f(runif(1e6)))

And with $\phi < 0$:

phi <- -pi/8
hist(f(runif(1e6)))

Best Answer

Related Solutions

Solved – Random number generation distributed like a translated weibull from uniform random generator

Random Number Generation – Generate Random Numbers from Sloped Uniform Distribution Using Mathematical Theory

Related Question