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.

Answer 2

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 3

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.

---

Edit:

I had a conversation this week that reminded me of this problem. If I forgo describing the histogram as an equation, and just store the table, can I do selections in O(1) time? It turns out you can, without any loss of precision, at the cost of O(N lgN) construction time.

Create an array of N items. A uniform random selection into the array will find an item with probablilty 1/N. For each item, store the fraction of hits for which this item should actually be selected, and the index of another item which will be selected if this one is not.

Weighted Random Sampling, C implementation:

//data structure
typedef struct wrs_data {
  double share; 
  int pair;
  int idx;
} wrs_t;


//sort helper
int wrs_sharecmp(const void* a, const void* b) {
  double delta = ((wrs_t*)a)->share - ((wrs_t*)b)->share;
  return (delta<0) ? -1 : (delta>0);
}


//Initialize the data structure
wrs_t* wrs_create(int* weights, size_t N) {
  wrs_t* data = malloc(sizeof(wrs_t));
  double sum = 0;
  int i;
  for (i=0;i<N;i++) { sum+=weights[i]; }
  for (i=0;i<N;i++) {
    //what percent of the ideal distribution is in this bucket?
    data[i].share = weights[i]/(sum/N); 
    data[i].pair = N;
    data[i].idx = i;
  }
  //sort ascending by size
  qsort(data,N, sizeof(wrs_t),wrs_sharecmp);

  int j=N-1; //the biggest bucket
  for (i=0;i<j;i++) {
    int check = i;
    double excess = 1.0 - data[check].share;
    while (excess>0 && i<j) {
      //If this bucket has less samples than a flat distribution,
      //it will be hit more frequently than it should be.  
      //So send excess hits to a bucket which has too many samples.
      data[check].pair=j; 
      // Account for the fact that the paired bucket will be hit more often,
      data[j].share -= excess;  
      excess = 1.0 - data[j].share;
      // If paired bucket now has excess hits, send to new largest bucket at j-1
      if (excess >= 0) { check=j--;} 
    }
  }
  return data;
}


int wrs_pick(wrs_t* collection, size_t N)
//O(1) weighted random sampling (after preparing the collection).
//Randomly select a bucket, and a percentage.
//If the percentage is greater than that bucket's share of hits, 
// use it's paired bucket.
{
  int idx = rand_in_range(0,N);
  double pct = rand_percent();
  if (pct > collection[idx].share) { idx = collection[idx].pair; }
  return collection[idx].idx;
} 

---

Edit 2: After a little research, I found it's even possible to do the construction in O(N) time. With careful tracking, you don't need to sort the array to find the large and small bins. Updated implementation here

Answer 4

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

Answer 5

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 6

For a normal distribution, the following may help:

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