How do I generate points that match a histogram?

Question

I am working on a simulation system. I will soon have experimental data (histograms) for the real-world distribution of values for several simulation inputs.

When the simulation runs, I would like to be able to produce random values that match the measured distribution. I'd prefer to do this without storing the original histograms. What are some good ways of

1. Mapping a histogram to a set of parameters representing the distribution?
2. Generating values that based on those parameters at runtime?

EDIT: The input data are event durations for several different types of events. I expect that different types will have different distribution functions.

Answer 1

For a normal distribution, the following may help:

http://en.wikipedia.org/wiki/Normal_distribution#Generating_values_for_normal_random_variables

Answer 2

At least two options:

1. Integrate the histogram and invert numerically.
2. Rejection

Numeric integration

From Computation in Modern Physics by William R. Gibbs:

One can always numerically integrate [the function] and invert the [cdf] but this is often not very satisfactory especially if the pdf is changing rapidly.

You literally build up a table that translates the range [0-1) into appropriate ranges in the target distribution. Then throw your usual (high quality) PRNG and translate with the table. It is cumbersome, but clear, workable, and completely general.

Rejection:

Normalize the target histogram, then

1. Throw the dice to choose a position (x) along the range randomly.
2. Throw again, and select this point if the new random number is less than the normalized histogram in this bin. Otherwise goto (1).

Again, simple minded but clear and working. It can be slow for distribution with a lot of very low probability (peaks with long tails).

---

With both of these methods, you can approximate the data with piecewise polynomial fits or splines to generate a smooth curve if a step-function histogram is not desired---but leave that for later as it may be premature optimization.

---

Better methods may exist for special cases.

All of this is pretty standard and should appear in any Numeric Analysis textbook if I more detail is needed.

Answer 3

If you need to pull a large number of samples with a weighted distribution of discrete points, then look at an answer to a similar question.

However, if you need to approximate some continuous random function using a histogram, then your best bet is probably dmckee's numeric integration answer. Alternatively, you can use the aliasing, and store the point to the left, and pick a uniform number between the two points.

Answer 4

More information about the problem would be useful. For example, what sort of values are the histograms over? Are they categorical (e.g., colours, letters) or continuous (e.g., heights, time)?

If the histograms are over categorical data I think it may be difficult to parameterise the distributions unless there are many correlations between categories.

If the histograms are over continuous data you might try to fit the distribution using mixtures of Gaussians. That is, try to fit the histogram using a $\sum_{i=1}^n w_i N(m_i,v_i)$ where m_i and v_i are the mean and variance. Then, when you want to generate data you first sample an i from 1..n with probability proportional to the weights w_i and then sample an x ~ n(m_i,v_i) as you would from any Gaussian.

Either way, you may want to read more about mixture models.

Answer 5

So it seems that what I want in order to generate a given probablity distribution is a Quantile Function, which is the inverse of the cumulative distribution function, as @dmckee says.

The question becomes: What is the best way to generate and store a quantile function describing a given continuous histogram? I have a feeling the answer will depend greatly on the shape of the input - if it follows any kind of pattern there should be simplifications over the most general case. I'll update here as I go.

Answer 6

To choose from a histogram (original or reduced), Walker's alias method is fast and simple.