c - 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

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.