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

Question

我正在研究一个模拟系统。 我很快就会获得几个模拟输入的真实世界分布值的实验数据（直方图）。

当模拟运行时，我希望能够生成与测量分布相匹配的随机值。 我宁愿在不存储原始直方图的情况下执行此操作。 有哪些好方法

1. 将直方图映射到一组表示分布的参数
2. ？ 在运行时根据这些参数生成值？

编辑：输入数据是几种不同类型事件的事件持续时间。 我预计不同的类型会有不同的分布函数。

Answer 1

至少有两个选项：

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

数值积分

William R. Gibbs 的现代物理学计算中的

：

人们总是可以对[函数]进行数值积分并反转[cdf]
但这通常不是很令人满意，特别是当 pdf 发生变化时
迅速。

您实际上构建了一个表，将范围 [0-1) 转换为目标分布中的适当范围。 然后扔出你常用的（高质量）PRNG 并用表格进行翻译。 它很麻烦，但是清晰、可行并且完全通用。

拒绝：

标准化目标直方图，然后

1. 掷骰子沿范围随机选择一个位置（x）。
2. 再次抛出，如果新的随机数小于该箱中的标准化直方图，则选择该点。 否则转到(1)。

再说一遍，头脑简单，但思路清晰，工作顺利。 对于概率非常低的情况（具有长尾的峰）来说，分布可能会很慢。

---

使用这两种方法，如果不需要阶跃函数直方图，您可以使用分段多项式拟合或样条曲线来近似数据以生成平滑曲线，但可以稍后再做过早的优化。

---

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

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

Answer 2

有关该问题的更多信息将会很有用。 例如，直方图代表什么类型的值？ 它们是分类的（例如颜色、字母）还是连续的（例如高度、时间）？

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

如果直方图是连续数据，您可能会尝试使用混合高斯分布来拟合分布。 也就是说，尝试使用 $\sum_{i=1}^n w_i N(m_i,v_i)$ 拟合直方图，其中 m_i 和 v_i 是均值和方差。 然后，当您想要生成数据时，您首先以与权重 w_i 成比例的概率从 1..n 采样 i，然后像从任何高斯分布一样采样 x ~ n(m_i,v_i)。

无论哪种方式，您可能想了解有关混合模型的更多信息。

Answer 3

所以看来我想要生成给定的概率分布是一个 分位数函数，这是
累积分布函数，如 @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;
} 

---

编辑2：
经过一番研究，我发现甚至可以在 O(N) 时间内完成构建。 通过仔细跟踪，您无需对数组进行排序即可找到大垃圾箱和小垃圾箱。 此处更新了实现

Answer 4

如果您需要提取大量具有离散点加权分布的样本，请查看 类似问题的答案。

但是，如果您需要使用直方图来近似某些连续随机函数，那么您最好的选择可能是 dmckee 的数值积分答案。 或者，您可以使用别名，并将点存储在左侧，并在两点之间选择一个统一的数字。

Answer 5

要从直方图（原始或简化）中进行选择，
Walker的别名方法
快速且简单。

Answer 6

对于正态分布，以下内容可能会有所帮助：

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