如何生成与直方图匹配的点?

1. 对直方图进行积分,并进行数值反转。
2. 拒绝

数值积分

从…起 现代物理学中的计算 威廉·吉布斯:

人们总是可以对[函数]进行数值积分,并反转函数[ ] 但这通常不是很令人满意,特别是如果 变化 迅速地

你真的建立了一个表来转换范围 [0-1)

拒绝:

1. 掷骰子选择一个位置( x
2. 再次抛出,如果新的随机数小于此容器中的标准化直方图,则选择此点。否则转到(1)。

同样,头脑简单,但清晰且有效。对于概率很低的分布(长尾巴的峰值),它可能会很慢。

使用这两种方法,您可以 如果不需要阶跃函数直方图,则使用分段多项式拟合或样条曲线近似数据,以生成平滑曲线,但将其留待以后,因为这可能是过早的优化。

对于特殊情况,可能存在更好的方法。

所有这些都是相当标准的,如果我需要更多的细节,应该出现在任何数值分析教科书中。

关于这个问题的更多信息将是有用的。例如,直方图覆盖哪些类型的值?它们是分类的(例如颜色、字母)还是连续的(例如高度、时间)?

如果直方图超过了分类数据,我认为可能很难对分布进行参数化,除非类别之间存在许多相关性。

无论哪种方式,您都可能想了解更多关于 mixture models .

所以,为了生成一个给定的概率分布,我想要的是一个 Quantile Function cumulative distribution function 正如@dmckee所说。

问题是:生成和存储描述给定连续直方图的分位数函数的最佳方法是什么?我有一种感觉,答案将在很大程度上取决于输入的形状——如果它遵循任何类型的模式,那么在最一般的情况下应该进行简化。我会在这里更新。

本周我有一次谈话提醒了我这个问题。如果我放弃将柱状图描述为一个等式,而只存储表格,我可以在O(1)时间内进行选择吗?事实证明,您可以在不损失任何精度的情况下,以O(N lgN)构造时间为代价。

创建N个项目的数组。在数组中进行均匀随机选择将发现概率为1/N的项目。对于每个项目,存储实际应选择此项目的命中分数,以及如果未选择此项目,将选择的另一个项目的索引。

加权随机抽样,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;
} 

经过一点研究,我发现甚至可以在O(N)时间内完成构建。通过仔细跟踪,您无需对阵列进行排序即可找到大小箱子。 Updated implementation here

如果需要使用离散点的加权分布提取大量样本,请查看 an answer to a similar question .

要从直方图(原始或缩小)中进行选择, Walker's alias method 它快速而简单。

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