拒绝抽样是获得真正均匀分布的随机数的唯一方法吗？

Question

假设我们有一个随机发电机，该发电机在$ [0..R-1] $中输出数字均匀分布，我们需要在$ [0..N-1] $的范围内生成随机数，并具有均匀的分布。

假设 $N < R$ 并且 $N$ 不能整除 $R$；为了得到 真正均匀分布 我们可以使用拒绝抽样 方法：

• 如果 $k$ 是最大整数，使得 $k N < R$
• 在 $[0..R-1]$ 中选择一个随机数 $r$
• 如果 $r < k N$ 则输出 $r \mod N$，否则继续尝试其他随机数 r', r", ...直到满足条件

拒绝采样是获得真正均匀离散分布的唯一方法吗？

如果答案是肯定的，为什么？

笔记：如果 $N > R$ 的想法是相同的：在 $[0..R^m-1] 中生成随机数 $r'$，R^m >= N$，例如 $r' = R(...R(R r_1 + r_2)... )+r_m$ 其中 $r_i$ 是 $[0..R-1]$ 范围内的随机数

Answer 1

是的，否，取决于您所说的“唯一方法”。是的，因为没有保证终止的方法，您可以做的最好的（对于$ n $和$ r $的通用值）是一种算法，它以概率1终止。浪费”尽可能小。

为什么保证终止是不可能的

假设您有确定性的计算引擎（图灵机或船的任何浮动），以及生成$ r $ element set $ [0..R-1] $的随机元素的甲骨文。您的目标是生成$ n $ element set $ [0，n-1] $的元素。引擎的输出仅取决于Oracle返回的值的顺序；它是该潜在无限序列$（R_0，R_1，R_2， ldots）$的函数$ f $。

假设您的引擎最多可以拨打甲骨文。可能会有痕迹将甲骨文称为少于$ m $ times；如果是这样，请致电Oracle额外的时间，以便始终将其完全称为$ M $ times不会更改输出。因此，在没有一般性的情况下，我们假设Oracle被称为$ M $ times。然后，结果$ x $的概率是序列$（r_0， ldots，r_ {m-1}）$的数量，使得$ f（r_0， ldots，r_ {m-1}）= x $。由于Oracle是一个均匀的随机发生器，因此每个序列都均衡，并且具有$ 1/r^m $的概率。因此，每个结果的概率是$ a/r^m $的表格，其中$ a $是$ 0 $和$ r^m $的整数。

如果$ n $为某些$ m $的$ r^m $划分，那么您可以通过调用随机生成器$ m $ times来生成均匀分布（$ n $元素）（这是练习给读者）。否则，这是不可能的：无法获得概率$ 1/n $的结果。请注意，该条件等同于说$ n $的所有主要因素也是$ r $的因素（这比您在问题中写的更允许的因素；例如，您可以在4中选择一个随机元素。 6面的公平死亡，即使4不划分6）。

减少废物

在您的策略中，当$ r ge k ，n $时，您不必立即重新绘制。直观地，$ [k ，n .. r-1] $剩下一些熵，您可以将其保留在混音中。

假设一会儿您实际上将永远生成以下$ n $以下的随机数，并且您一次通过制作$ d $ draws会产生其中的$ u $。如果您对这一分组的一代进行直接的拒绝采样，那么$ d $ draws的废物为$ dfrac {r^d -k k ，n^u} {d} {d} $，即剩余的$ r^d mathbin { mathrm {mod}} n^u $除以绘制数。这可能只有$ gcd（r，n）$。当$ r $和$ n $是企业时，您可以通过挑选足够大的$ d $的大量浪费。对于$ r $和$ n $的一般值，计算更为复杂，因为您需要考虑$ gcd（r，n）$和$ n/ gcd（r，n）$的生成但是，您可以将废物与足够大的小组任意减小。

实际上，即使有相对效率低下的随机数（例如，在密码学中），除非$ n $很小，否则除非简单拒绝采样，否则很少做任何事情。例如，在密码学中，$ r $通常是2个功率，$ n $通常是数百或数千个位，均匀的随机数生成通常是通过在所需范围内的直拒置采样来进行的。

Answer 2

香农的源编码定理表明，从某种意义上说，您需要$ log n/ log r $样本（平均而言）$ [0， ldots，r-1] $来生成随机数的随机数键入$ [0， ldots，n-1] $。更准确地说，香农给出了一种（效率低下的）算法，它给出了第一种类型的$ m $样本，输出$ m（ log n/ log r- epsilon）$ samples $ seccess第二类型，具有很高的可能性。他还表明，输出$ M（ log n/ log r + epsilon）$样本具有很高的可能性。

香农定理还可以在偏斜的输入分布的更一般情况下（可能也偏向输出分布）。在这种情况下，您需要用熵替换对数。尽管定理给出的算法是随机定义的，但在某些情况下，可以将其定义（以较差的性能为代价）。

Answer 3

事实上，不，拒绝抽样远不是唯一的处理方法。不幸的是，考虑到计算机将所有信息存储为位，因此只能操纵信息的随机位，如果 $N$ 的二进制基数发展是无限的，则任何绘制范围 $N$ 的均匀随机变量的算法都将是无限的。

该定理是 Knuth 和 Yao (1976) 的经典结果，他们开发了 DDG 树（离散分布生成树）的框架。

Gilles 公开的方法是一种典型的方法，旨在减少因拒绝而造成的浪费，但当然，如果可以遵循 Knuth 和 Yao 的树生成，那么效率会高得多 - 平均生成 96% 的随机位被保存。

我在下面提供了更多相关信息 C理论帖.