algorithm - key 选择的均匀随机性详解

Question

考虑这个问题:- Efficiently picking a random element from a chained hash table?

并考虑它的第一个答案。它提出了一种以均匀随机方式选择 key 的方法。但是，我不清楚。第一步将采用 1/m 的概率(即从 m 个桶中随机选择一个桶)
而第二步又可以分为两步:
1) 如果是 k<=p ，则返回 p。
2) 如果 k>p 则循环再次运行。
这样做直到返回 p。
所以一个key被选中的概率是:
(1/m)[(k1/L)+((L-k1)/L)[(1/m)[(k2/L)+((L-k2)/L)[(1/m)[(k3/L)+((L-k3)/L)[......and so on.
现在这怎么能等于 1/n 呢？

Answer 1

这是 rejection-sampling 的一种形式.

备注:

• 看起来你把这两个步骤分开了，只在第二步以某种方式循环(我对你的计算公式的解释)
每次
• 重做所有步骤是算法最重要的方面!
  • 这是拒绝抽样的基本思想:我们从周围的一些密度中抽样，如果所选样本不在我们的抽样范围内，则需要再次抽样(这很不正式；请阅读上面的链接)

为什么采用这种方法:

• 想象一下，有 2 个桶，其中 b0 有 2 个元素，b1 有 4 个 元素
• 第 1 步是统一选择一个桶
  • 但由于 b0 的元素数量与 b1 不同，第 2 步 中的实际抽样需要以某种方式适应信息关于元素的数量(或者我们将使用均匀性)
  • 我们没有这个完整的信息，我们只得到了所有链上的上限L
  • 含义:我们使用rejection-idea从ma​​x-range L中采样；并且如果索引与存储桶兼容则接受。因此，如果所选桶的元素数量是最大桶的一半，则需要 50% 的时间将其中止(从步骤 1 重新开始)。 这就像向所有桶中插入假元素，使元素的数量保持不变。然后采样，检查是否选择了真实元素或假元素，如果命中了假元素，则再次执行此操作。
  • 很容易看出:b0 得到 50% 的选择；等于b1
  • 在 b0 内采样时，该过程将在 50% 的时间内中止，因为k=2，L=4(L 来自b2)
  中元素的大小
  • 在 b1 内采样时，该过程永远不会中止 (k=L)
  • 如果没有中止的机会；我们将选择 b0 的一个选定元素 2 倍 (L/size-within-b0 = L/2) 作为 < strong>b1，因为桶是统一选择的；但要采样的元素数量不同。