几个与概率有关的问题

发表于

看过《概率面试题精讲》这个视频之后，来总结一下视频中讲过的几个比较重要的问题。

1. random shuffle 问题

问题描述：给定一个字符串，随机返回任意一种打乱顺序之后的字符串，保证每种情况出现的概率相等。下面是一份实现代码：

char *reshuffle(char *str)
{
    for (int i = strlen(str) - 1; i > 0; --i) {
        int j = rand() % (i + 1);
        swap(str[i], str[j]);
    }
    return str;
}

算法证明：只要证明字符串中的任意元素被放到任意位置的概率相等即可。按照我们的算法：每个元素被放到 (n - 1) 位置的概率为 1 / n，被放到 (n - 2) 位置即第一次没被选中而第二次被选中了，概率为：(n - 1) / n * 1 / (n - 1) = 1 / n … 可见：任意元素 m 被放到位置 i 的概率即前面都没选中而进行到第 i 个位置时选中它的概率：(n - 1) / n * (n - 2) / (n - 1) * ... * (i + 1) / (i + 2) * 1 / (i + 1) = 1 / n，算法正确性得证。

2. 构造随机数发生器

问题描述：现在已有一个产生 [0, 7) 随机数发生器 rand7，利用它构造产生 [0, 10) 随机数发生器 rand10。有两种方法：

方法一：先构造 [0, 1] 随机数发生器
int genBit()
{
    int x;
    while ((x = rand7()) == 6) ;
    return x & 0x1;
}

int rand10()
{
    int x;
    do {
        x = 0;
        for (int i = 0; i < 4; ++i)
            x = (x << 1) | genBit();
    } while (x >= 10);
    return x;
}
方法二：利用 7 进制直接求解
int rand10()
{
    int x;
    while ((x = rand7() * 7 + rand7()) >= 40);
    return x % 10;
}

注意：很明显，方法二扔掉的数比方法一要少，循环次数相对比较少，速度应该更快。

3. 水库（Reservoir）采样问题

问题描述：流入若干个整数（总数量未知），要求随机取出 k 个 (k小于总数)。算法描述如下：

(1) 用一个数组 a 保存 k 个数: a[0..k - 1];
(2) 对于第 i 个元素 (i = 0, 1, 2, ...):
    • 若 i < k, 则 a[i] 存放该元素;
    • 否则产生随机数 x = rand() % (i + 1), 若 x < k, 则用 a[x] 存放该元素(扔掉之前的元素).

算法证明：假设目前已经流入 n > k 个元素, 第 i (i < k) 个元素被选中的可能性为：1 * k / (k + 1) * (k + 1) / (k + 2) * ... * (n - 1) / n = k / n；第 i (i >= k) 个元素被选中的可能性为：k / (i + 1) * (i + 1) / (i + 2) * (i + 2) / (i + 3) * ... * (n – 1) / n = k / n，算法正确性得证。

4. 带权采样问题

问题描述：给定 n 种元素，同时给定 n 个权值，按权值比例随机抽样。有三种方法：

方法一：每种元素复制相应的份数，再进行随机抽样（额外开销较大）
方法二：根据元素个数划分整数区间，每个区间对应一种元素（需要二分）

例如：有 3 个 a， 2 个 b， 6 个 c；那么 a 对应 [0, 2]， b 对应 [3, 4]，c 对应 [5, 10]；产生一个 [0, 10] 的随机数，用二分查找确定对应的元素是哪一个，抽取出来。

方法三：效率最高的方法
(1) 以 1 / n 的概率随机选出一种元素 i: 产生 [1, n] 的随机数 x, 根据 x 的值选择是哪种元素;
(2) 以 Pi = (i 的权值 Wi) / (权值和 W) 的概率决定是否保留: 产生 [1, W] 的随机数 x, 若 x <= Wi 则保留.

算法证明：选中任意一个元素的概率为：P = 1 / m * P1 + 1 / m * P2 + ... + 1 / m * Pn = 1 / m，则最后选中 i 的概率为：1 / m * Pi + (1 - P) * 1 / m * Pi + (1 - P) ^ 2 * 1 / m * Pi + ...，显然这个概率正比于 Pi，因此上述算法正是按照权值比例抽取元素的，其正确性得证。

0%