1

从n的所有分区集合中随机选择的整数分区的共轭也是均匀随机样本吗?我的结果表明是的,这是令人鼓舞的,因为它可以快速生成长度为 s 的 n 的随机分区,但我无法解释为什么应该或不应该这样做。

顺便说一句,我的结果基于 1.) 为特定长度 (s) 的小 n (<70) 生成所有分区 2.) 将每个分区的方差计算为宏状态描述符和 3.) 比较内核整个可行集(长度为 s 的 n 的所有分区)与小随机样本(即 <500 个随机生成的长度匹配 s 或共轭长度匹配 s 的 n 分区)的方差的密度曲线。随机样本的核密度曲线与整个可行集的曲线非常匹配(即所有匹配的 n 个分区)。这直观地说明了随机样本(其中大多数是共轭分区)捕获了基于 n 和 s 的可行集的分区之间的方差分布。我只是无法解释为什么它应该像看起来那样工作;

注意:产生随机样本的许多其他程序会产生明显有偏差的样本(即形状不同且高度不重叠的核密度曲线)。

4

1 回答 1

1

是的。共轭是双射运算,因此每个分区都映射到一个唯一的共轭,而该共轭又映射回原始分区。因此,随机选择均匀分区的共轭不会引入任何偏差。

我不认为这可以帮助您随机生成固定长度的分区 - 您可能应该调整 Nijenhuis & Wilf 的算法以正确执行此操作。这应该不是很难做到,因为 n 到 k 部分的分区数可以很容易地计算出来,而随机生成算法实际上只依赖于此。

Knuth 在 TAOCP 第 4A 卷的第 7.2.4.1 节中包含了一个关于生成随机分区的练习 (47)。这将是一个有效的算法以随机均匀地生成固定长度分区的一个很好的起点。

于 2012-05-04T15:24:43.270 回答