Как я генерирую точки, которые соответствуют гистограмме?

Если необходимо вытянуть большое количество образцов со взвешенным распределением дискретных точек, то посмотрите на ответ на подобный вопрос.

Однако, если необходимо приблизить некоторую непрерывную случайную функцию с помощью гистограммы, затем лучший выбор является, вероятно, числовым ответом интеграции dmckee. С другой стороны, можно использовать искажение, и сохранить точку налево и выбрать универсальное число между двумя точками.

Больше информации о проблеме было бы полезно. Например, какие значения являются законченными гистограммами? Действительно ли они являются категориальными (например, цвета, буквы) или непрерывными (например, высоты, время)?

Если гистограммы по категориальным данным, я думаю, что может быть трудно параметризовать дистрибутивы, если нет много корреляций между категориями.

Если гистограммы по текущим данным, Вы могли бы попытаться соответствовать распределению с помощью смесей Gaussians. Таким образом, попытайтесь соответствовать гистограмме с помощью $\\sum_ {i=1} ^n w_i N (m_i, v_i) $, где m_i и v_i являются средним и различием. Затем когда Вы хотите генерировать данные, Вы сначала выбираете меня от 1.. n с вероятностью, пропорциональной весам w_i и затем, выбирают x ~ n (m_i, v_i), как Вы были бы от любого Гауссова.

Так или иначе можно хотеть читать больше о моделях смеси.

Таким образом, кажется, что то, что я хочу для генерации данного распределения вероятности, является Функцией Квантиля, которая является инверсией кумулятивной функции распределения, как говорит @dmckee.

Вопрос становится: Что лучший способ состоит в том, чтобы генерировать и сохранить функцию квантиля описание данной непрерывной гистограммы? У меня есть чувство, что ответ будет зависеть значительно от формы входа - если это будет следовать за каким-либо видом шаблона должны быть упрощения по наиболее общему случаю. Я обновлю здесь, когда я иду.

Править:

Я разговаривал на этой неделе, который напомнил мне об этой проблеме. Если я воздерживаюсь от описания гистограммы как уравнение и просто храню таблицу, я могу сделать выборы в O (1) время? Оказывается, что Вы можете, без любой потери точности, за счет O (N lgN) время создания.

Создайте массив объектов N. Универсальный случайный выбор в массив найдет объект с probablilty 1/Н. Для каждого объекта сохраните часть хитов, для которых этот объект должен на самом деле быть выбран, и индекс другого объекта, который будет выбран, если этот не будет.

Взвешенная Случайная Выборка, C реализация:

//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;
} 

Редактирование 2: После небольшого исследования я нашел, что даже возможно сделать конструкцию в O (N) время. С тщательным отслеживанием Вы не должны сортировать массив для нахождения больших и маленьких мусорных ведер. Обновленная реализация здесь

Для нормального распределения следующее может помочь:

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

Чтобы выбрать гистограмму (исходную или уменьшенную), Метод псевдонима Уокера быстро и просто.