How to generate a set of values that follow certain distribution in c++/java?

F开发者_如何转开发or example, I have a p.d.f f(x) = 1/25 - x/1250 (from x = 0 to 50); My question is that how to generate a set of values that satisfy the given p.d.f. Please give an idea about how to implement in c++ or java. Thanks so much.

I don't know about directly from a pdf, but you can convert a pdf to a cdf (by integrating) and then use inverse transform sampling. This assumes that you have a technique to generate a random number u in [0, 1] (e.g. Math.random() in Java).

Once you have generated such a u, find an x such that cdf(x) = u. That x is the value that you want.

Your function is similar to f(x) := 1 - x. For that case I did the following:

1. integrate the function f to yield F.
2. normalize the function F so that its domain is [0;1), yielding NF.
3. invert NF to yield dist.

Then I used the following code to check the result:

package so7691025;

import java.awt.Color;
import java.awt.Graphics;
import java.awt.image.BufferedImage;
import java.io.File;
import java.io.IOException;
import java.util.Random;

import javax.imageio.ImageIO;

public class DistImage {

  private static double dist(double x) {
    return 1.0 - Math.sqrt(1.0 - x);
  }

  public static void main(String[] args) throws IOException {
    final Random rnd = new Random(0);

    BufferedImage img = new BufferedImage(1000, 1000, BufferedImage.TYPE_BYTE_GRAY);
    int[] distrib = new int[1000];
    for (int i = 0; i < 500000; i++) {
      distrib[(int) (dist(rnd.nextDouble()) * 1000)]++;
    }

    Graphics g = img.getGraphics();
    g.setColor(Color.WHITE);
    g.fillRect(0, 0, 1000, 1000);
    g.setColor(Color.BLACK);
    for (int i = 0; i < 1000; i++) {
      g.drawLine(i, 1000, i, 1000 - distrib[i]);
    }

    ImageIO.write(img, "png", new File("d:/distrib.png"));
  }
}

The resulting image looked pretty good to me.

If your values-set is discrete, a valid algorithm is described in the article "A Linear Algorithm For Generating Random Numbers With a Given Distribution". The algorithm contains a simple pseudo-code, and has O(n) time, where n is the set size.

When the pdf is not discrete, as in your example, see section 5.1 in "Introduction to Monte Carlo Simulation".