Welcome to OStack Knowledge Sharing Community for programmer and developer-Open, Learning and Share
Welcome To Ask or Share your Answers For Others

Categories

0 votes
374 views
in Technique[技术] by (71.8m points)

c - How do I generate points that match a histogram?

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.

See Question&Answers more detail:os

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome To Ask or Share your Answers For Others

1 Answer

0 votes
by (71.8m points)

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.


与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome to OStack Knowledge Sharing Community for programmer and developer-Open, Learning and Share
Click Here to Ask a Question

...