skiplist的C实现中的一个概率论问题

Question

这些天我正在查看 Algorithms in C, Parts 1-4 中的 skiplist 代码，当向 skiplist 中插入一个新值时比我想象的要复杂。在插入过程中，代码应确保新值以 1/2^i 的概率插入到级别 i 中，并通过以下代码实现：

static int Rand()
{
    int i, j = 0;
    uint32_t t = rand();
    for (i = 1, j = 2; i < lg_n_max; i ++, j += j)
        if (t > RANDMAX / j)
            break;
    if (i > lg_n)
        lg_n = i;
    return i;
}

我不知道Rand函数是如何保证这一点的，你能为我解释一下吗，谢谢。

Answer 1

据推测 RANDMAX 是 RAND_MAX。

忽略舍入问题，rand 的 return 值有一半高于 RAND_MAX / 2，因此有一半时间循环以 i = 1 退出。

如果循环继续，它会将 i 更新为 2，将 j 更新为 4。然后剩余的一半 return 值（总数的 3/4）高于 RAND_MAX / 4，因此，四分之一的时间，循环以 i = 2.

退出

进一步的迭代以相同的方式继续，每次迭代退出时 return 值的一部分是前一次的一半，直到达到 lg_n_max 限制。

因此，忽略舍入问题和最终限制，例程 returns 1 一半时间，2 四分之一时间，3 八分之一时间，依此类推。

lg_n 未在例程中定义。它似乎是迄今为止该例程创造的最大价值的记录。return。

Answer 2

非常感谢Eric Postpischil的回答，我明白了如何保证概率。我有一个更容易理解的答案： t是0和RANDMAX之间的随机值，我们假设循环会运行 2次。在第一个循环中，t的值小于RANDMAX/2^1，表示t的值落在0到RANDMAX/2之间的概率，这是 1/2。在第二个循环中，记住t的值在(0, RANDMAX/2^i)的范围内，t的值小于RANDMAX/2^2，意味着[=11的值=]落在0到RANDMAX/2^2之间，这个概率也是1/2，因为(0, RANDMAX/2^2)的范围只有1/2的范围在第一个循环中，第一个循环显示 t 的值在 (0, RANDMAX/2^1) 的范围内。并且注意到第二次循环的概率是条件概率，它是基于第一次循环的概率，所以第二次循环的概率是1/2*1/2=1/4.
简而言之，每次循环都会使最后一次循环的概率* 1/2。

skiplist的C实现中的一个概率论问题

A probability theory problem in skiplist's C implement

c

algorithm

probability

skip-lists