algorithm - 如何生成统一的随机整数分区？

Question

谷歌搜索揭示了很多关于生成整数 n 到 m 部分的所有可能分区的信息，但我没有找到任何关于将 n 均匀分布的随机分区采样到 m 部分的信息。

Answer 1

这篇文章的标题有点误导。默认情况下，随机整数分区是不受限制的，这意味着它可以有任意大小的任意数量的部分。具体问的问题是将n划分为m部分，是一种限制整数划分。

为了生成不受限制的整数分区，Fristedt 在一篇名为 The Structure of Random Partitions of Large Integer (1993) 的论文中提出了一种非常快速且简单的算法。算法如下:

1. 设置 x = exp(-pi/sqrt(6n) )。
2. 生成独立的随机变量 Z(1), Z(2), ..., Z(n)，其中 Z(i) 服从参数 1-x^i 的几何分布。
3. IF sum i*Z(i) = n，其中对所有 i=1,2,...,n 求和，然后停止。
   否则，重复 2。

一旦算法停止，那么 Z(1) 是 1 的数量，Z(2) 是 2 的数量，依此类推，在所选分区中均匀随机。接受随机选择的一组 Z 的概率渐近为 1/(94n^3)^(1/4)，这意味着人们期望在接受单个 Z 之前运行该算法 O(n^(3/4)) 次样本。

我花时间解释这个算法的原因是因为它直接适用于将 n 分割成恰好 m 个部分的问题。首先，观察

将n分成恰好m个部分的个数等于n最大部分等于m个的分区个数。

然后我们可以直接应用 Fristedt 算法，但不是生成 Z(1), Z(2), ..., Z(n)，而是生成 Z(1), Z(2), ... , Z(m-1), Z(m)+1(这里的+1保证最大的部分恰好是m，1+Z(m)在Z(m)的条件下等于Z(m)的分布>=1) 并设置所有其他 Z(m+1), Z(m+2), ... 等于 0。然后一旦我们在步骤 3 中获得目标和，我们也保证有一个无偏样本。要将 n 恰好划分为 m 个部分，只需取生成的划分的共轭即可。

与 Nijenhuis 和 Wilf 的递归方法相比，它的优势在于除了存储随机变量 Z(1)、Z(2) 等外，没有内存要求。此外，x 的值可以是任何值在 0 和 1 之间，这个算法仍然是无偏的!然而，选择一个好的 x 值可以使算法更快，尽管步骤 1 中的选择对于不受限制的整数分区来说几乎是最优的。

如果 n 真的很大，Fristedt 的算法耗时太长(表法也不行)，那么还有其他的选择，但会稍微复杂一些；看我的论文https://sites.google.com/site/stephendesalvo/home/papers有关概率分而治之及其应用的更多信息。