math - 生成桶大小的指数分布

Question

给定一系列传入的项目，我想将每个项目分配到一个桶中。该桶可以是新的(以前从未使用过的，有无限供应的)或它可以是现有的存储桶。如果我查看包含一个项目的存储桶数量、包含两个项目的数量、包含三个项目的数量等，我希望这些存储桶计数遵循指数分布。我希望我说的是正确的——如果 80% 的桶有 1 个项目，那么 16% 的桶应该有 2 个，3.2% 的桶应该有 3 个，等等。一般来说，大小为 k 的桶的数量应该是 1/p大小为 k-1 的桶的数量一样多，并且大小为 1 的桶的分数应为 (1-p)，以使数学计算正确。

如果我提前知道元素的数量，那就很容易了:我会知道每种尺寸有多少个桶，所以我可以根据需要将元素堆放在每种尺寸的多个桶中。或者，如果我只是生成桶大小，即使我事先不知道总数，也会很容易:每个新桶的大小为 1 的概率 (1-p)，大小为 (1-p)p 的概率2、(1-p)p^2 尺寸 3、(1-p)p^3 尺寸 4 等

但是我正在处理项目，因此当我放入一个项目时，我需要选择一个存储桶:要么是现有的，要么是新的。如果我制作一个新的桶，那么我会多得到一个尺寸为 1 的桶。但是，如果我选择现有的一个尺寸为 k 的桶，那么我会多得到一个尺寸为 k+1 的桶，以及少一个尺寸 k。那么选择大小为 k 的桶的概率应该是多少(其中 k 可以为零以指示创建一个新桶)？它与 p 有何关系？

我这样做是为了生成测试数据，我只知道每个桶的平均项目数(结果是 1.5)，事先不知道项目数，并且认为桶大小的指数分布对于我的情况来说是现实的。我可能让它变得比需要的更复杂，但我很惊讶，因为我认为这会很容易。

也许是这样，但我只是错过了一些东西。 (而且我也不知道如何用 Google 搜索它。)

Answer 1

指数分布支持整个正实数；您的分布支持正整数(它是离散概率分布)，称为 geometric distribution 。 ^{( W )} [概率通常用参数 1−(你的 p) 来表示，但这是一个微不足道的细节。]

实际上，当您只知道平均值时，选择几何分布是一个不错的选择:

Among all discrete probability distributions supported on {1, 2, 3, ... } with given expected value μ, the geometric distribution X with parameter p = 1/μ is the one with the largest entropy.

你的问题很有趣(如何在给定大小分布的情况下增量填充桶)，我不知道最好的答案，但假设有足够多的项目，以下愚蠢的算法将起作用:

While there are items left:
    Pick a "bucket size" k according to the desired distribution
    /* E.g., for the geometric distribution with mean 1.5, 
       you could toss a coin with bias 0.667 until you get a head,
       then you'll get k=1 for 66.7% of the time, k=2 for 22.2%, k=3 for 7.4% etc., 
       with k being 1.5 on average (in expectation) */
    Put the next k items into one (new) bucket.

请注意，您不需要知道项目的数量。假设数量足够大，问题(例如分布的方差和最后的“剩余”)就不那么重要了。