密钥选择的均匀随机性详解
Elaboration on the uniform randomness of selection of a key
考虑这个问题：-
Efficiently picking a random element from a chained hash table?
并考虑这是第一个答案。它提出了一种以均匀随机方式 select 密钥的方法。但是，我不清楚。第一步将采用 1/m 的概率（即从 m 个桶中随机 select 一个桶）
而第二步又可以分为两步：
1) 如果k<=p，则返回p。
2) 如果 k>p 则循环再次运行。
这样做直到返回 p。
所以一个键被 selected 的概率是：
(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？
这是rejection-sampling的一种形式。
备注：
- 看起来你把这两个步骤分开了，只在第二步循环（我对你的计算公式的解释）
- 每次都重做所有步骤是算法最重要的方面！
- 这是拒绝采样的基本思想：我们正在从一些周围的密度中采样并且需要再次采样，如果selected样本不在我们的样本范围内（那非常非正式；阅读以上 link)
为什么采用这种方法：
- 想象一下，有 2 个桶，其中 b0 有 2 个元素，b1 有 4 个元素
- 步骤 1 是 select 一个桶 均匀地
- 但是因为b0与b1的元素数量不同，实际采样在step 2 需要以某种方式适应有关元素数量的信息（或者我们将使用均匀性）
- 我们没有这个完整的信息，我们只得到了所有链上的上限L
- 含义：我们使用rejection-idea从max-range L中采样；如果索引与存储桶兼容，接受。因此，如果 selected 桶的元素数量是最大桶的一半，则需要 50% 的时间将其中止（从步骤 1 重新开始）。 这就像在所有桶中插入假元素，使元素的数量保持不变。然后采样，检查 selected 是真元素还是假元素，如果命中了假元素，再做一次.
- 很容易看出：b0 50% 的时间被选中；等于 b1
- 在 b0 内采样时，进程将 中止 50% 的时间，因为 k=2， L=4（L来自b2中元素的大小）
- 在 b1 内采样时，进程永远不会中止 (k=L)
- 如果没有中止的机会；我们将 select selected 元素 b0 (
L / size-within-b0 = L/2) 的两倍 (L / size-within-b0 = L/2)来自 b1，因为桶是统一 selected；但是要采样的元素数量不同。
考虑这个问题：- Efficiently picking a random element from a chained hash table?
并考虑这是第一个答案。它提出了一种以均匀随机方式 select 密钥的方法。但是，我不清楚。第一步将采用 1/m 的概率（即从 m 个桶中随机 select 一个桶）
而第二步又可以分为两步：
1) 如果k<=p，则返回p。
2) 如果 k>p 则循环再次运行。
这样做直到返回 p。
所以一个键被 selected 的概率是：
(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？
这是rejection-sampling的一种形式。
备注：
- 看起来你把这两个步骤分开了，只在第二步循环（我对你的计算公式的解释）
- 每次都重做所有步骤是算法最重要的方面！
- 这是拒绝采样的基本思想：我们正在从一些周围的密度中采样并且需要再次采样，如果selected样本不在我们的样本范围内（那非常非正式；阅读以上 link)
为什么采用这种方法：
- 想象一下，有 2 个桶，其中 b0 有 2 个元素，b1 有 4 个元素
- 步骤 1 是 select 一个桶 均匀地
- 但是因为b0与b1的元素数量不同，实际采样在step 2 需要以某种方式适应有关元素数量的信息（或者我们将使用均匀性）
- 我们没有这个完整的信息，我们只得到了所有链上的上限L
- 含义：我们使用rejection-idea从max-range L中采样；如果索引与存储桶兼容，接受。因此，如果 selected 桶的元素数量是最大桶的一半，则需要 50% 的时间将其中止（从步骤 1 重新开始）。 这就像在所有桶中插入假元素，使元素的数量保持不变。然后采样，检查 selected 是真元素还是假元素，如果命中了假元素，再做一次.
- 很容易看出：b0 50% 的时间被选中；等于 b1
- 在 b0 内采样时，进程将 中止 50% 的时间，因为 k=2， L=4（L来自b2中元素的大小）
- 在 b1 内采样时，进程永远不会中止 (k=L)
- 如果没有中止的机会；我们将 select selected 元素 b0 (
L / size-within-b0 = L/2) 的两倍 (L / size-within-b0 = L/2)来自 b1，因为桶是统一 selected；但是要采样的元素数量不同。