Generate random number with non-uniform density

Question

Did someone know how to generate random numbers with a non-uniform density?

Answer 1

Easiest solution if applicable: Use C++11 random facilities or the ones from Boost, which have lots of non-uniform distributions for you.

Answer 2

You should state what distribution you need. Basically, you use the inverse of the probability function you want. For example, the most common way to get normal distribution is Box-Muller transform.

Here is the code for Box-Muller just to get the idea:

float box_muller(float m, float s)  /* normal random variate generator */
{                       /* mean m, standard deviation s */
    float x1, x2, w, y1;
    static float y2;
    static int use_last = 0;

    if (use_last)               /* use value from previous call */
    {
        y1 = y2;
        use_last = 0;
    }
    else
    {
        do {
            x1 = 2.0 * ranf() - 1.0;
            x2 = 2.0 * ranf() - 1.0;
            w = x1 * x1 + x2 * x2;
        } while ( w >= 1.0 );

        w = sqrt( (-2.0 * log( w ) ) / w );
        y1 = x1 * w;
        y2 = x2 * w;
        use_last = 1;
    }

    return( m + y1 * s );
}

Answer 3

This class takes a distribution as a matrix (each row is a couple of a number and its frequency) and generates random numbers. So you can have Look at main method and run.

public class RandomGenerator {
    HashMap<Integer,Range> mappa = new HashMap<Integer,Range>();
    Random random = new Random();
    int max;




    public static void main(String as[]){ 
        int[][] matrice = new int[3][2];
        //number 5 occurs 5 times
        matrice[0][0] = 5 ;
        matrice[0][1] = 5 ;
        //number 18 occurs 18 times
        matrice[1][0] = 18 ;
        matrice[1][1] = 18 ;
        //number 77 occurs 77 times
        matrice[2][0] = 77 ;
        matrice[2][1] = 77 ;

        RandomGenerator randomGenerator = new RandomGenerator(matrice); 


        for (int i = 0; i < 100; i++) {
            System.out.println( randomGenerator.getNext() );
        }
    }





    public int getNext(){
        int percentile = random.nextInt(max);
        Range r =mappa.get(percentile);
        return r.getValMax();
    }

    public HashMap<Integer, Range> getMappa() {
        return mappa;
    }

    public void setMappa(HashMap<Integer, Range> mappa) {
        this.mappa = mappa;
    }

    public RandomGenerator(int[][] distribuzioneOriginale ){
        ArrayList<Range> listaRange = new ArrayList<Range>();
        int previous = 0;
        int totaleOccorrenze = 0;
        for (int riga = 0; riga < distribuzioneOriginale.length; riga++) {

            Range r = new Range();
            r.setValMin(previous);
            r.setValMax(distribuzioneOriginale[riga][0]);
            r.setOccorrenze(distribuzioneOriginale[riga][1]);
            totaleOccorrenze += distribuzioneOriginale[riga][1];
            previous = distribuzioneOriginale[riga][0];

            listaRange.add(r);
        }



        int indice = 0;
        for (int iRange = 0; iRange < listaRange.size(); iRange++) {
            Range r = listaRange.get(iRange);

            int perc = (int) ( 1000* (r.getOccorrenze() / (double)  totaleOccorrenze)  )  ;

            for (int i = 0; i < perc; i++) {
                mappa.put( i + indice  , r);
            }
            indice += perc;
        }

        max = indice;

    }



    class Range{
        int valMin;
        int valMax;
        int occorrenze; 


        public int getValMin() {
            return valMin;
        }
        public void setValMin(int valMin) {
            this.valMin = valMin;
        }
        public int getValMax() {
            return valMax;
        }
        public void setValMax(int valMax) {
            this.valMax = valMax;
        }
        public int getOccorrenze() {
            return occorrenze;
        }
        public void setOccorrenze(int occorrenze) {
            this.occorrenze = occorrenze;
        }  

    }
}

Answer 4

Use a uniform density RNG, and pass its result through a mapping function to convert to your desired density distribution.

Answer 5

In your comment in the question:

1/sqrt(2*pi) * e^(-x^2)

The only variable is x. x itself will have a uniform density. So just pick a good random number, then stick it into that equation.