随机均匀抽奖

未分类

1 术语定义

随机均匀：每个抽奖参与者被抽中的概率是一样的。也就是如果有$n$个参与者，奖项有$m$个，那么每个人的中奖概率都是$\frac{m}{n}$。

$G(n)$随机数生成器：每次运行$G(n)$随机数生成器，都会等概率随机返回一个$[0,n)$内的一个整数。不妨假设$n>1, n \in N^+$。

哈希表：可以以均摊$O(1)$的时间复杂度进行增删查改的数据结构。

2 前言

团建的时候总监提到他在面试的时候经常问面试者的一个问题：有一个$G(2^{16})$随机数生成器，需要在$300000$个人中随机均匀抽出$100000$个人，怎么做？

这个确实是一个老生常谈的面试题了，下面描述两种满足需求的算法。

3 两种算法

在描述抽奖算法之前，先描述一个重要的推论。

3.1 随机数生成器是本质相同的

这个推论的意思是，所有$G(n)$随机数生成器都可以在有限次数内等价转换成其他的随机数生成器$G(m)$。下面给出转换过程和证明：

过程：

设$k$是最小的满足$n^k \ge m$的正整数。
1. 运行$k$次$G(n)$，可以得到一个$[0,n^k)$内的随机整数$x$。
2. 如果$x \ge \lfloor \frac{n^k}{m} \rfloor \times m$，那么重新返回步骤1，否则进入步骤3。
3. 输出$x\%m$作为$G(m)$随机数生成器的输出。

证明：

1. 正确性显然，略去。
2. 步骤2跳回步骤1的概率为$P(n,m)=\frac{n^k\% m}{n^k}=\frac{n^k\%m}{\lfloor \frac{n^k}{m} \rfloor \times m + n^k \% m}<\frac{n^k\%m}{m + n^k \% m}<\frac{n^k\%m}{n^k \% m + n^k \% m}<\frac{1}{2}$，故步骤1的运行次数期望$E(n,m)<2$，那么$G(n)$随机数生成器可以在期望$2k$次运行后得到一个$G(m)$随机数生成器。

3.2 RandomShuffle

基本每种编程语言中都会给一个shuffle接口，用于随机打乱数组的元素。其中一种可能的C++ std::random_shuffle实现是：

template<class RandomIt>
void random_shuffle(RandomIt be, RandomIt en) {
    int n = en - be;
    for (int i = 0; i < n; i++) {
        using std::swap;
        swap(be[i], be[G(i + 1)]);
    }
}

那么一个简单的抽奖算法便是先对整个参与者序列进行random_shuffle，shuffle后每个参与者出现在每个位置的概率都是一样的。然后再按任意方式选出任意个中奖者即可，这样可以保证每个参与者中奖的概率是一样的。下面用数学归纳法证明这个random_shuffle的过程是随机均匀的：
1. $n=1$时，正确性显然。
2. 容易发现$n$个参与者的shuffle和$n+1$个参与者的shuffle的差异只有一步：后者在前者的基础上进行最后一次交换。那么假设$n$个参与者进行shuffle后结果是随机均匀的（也就是每个参与者出现在每个位置的概率都是$\frac{1}{n}$），进行第$n+1$次交换后，显然第$n+1$个参与者在每个位置出现的概率都是$\frac{1}{n+1}$，对前$n$个参与者来说如何呢？对这些参与者来说，被交换到第$n+1$个位置的概率是$\frac{1}{n+1}$，保留在原位（第$n$次交换过后的位置）的概率是$\frac{n}{n+1}$，在$1 - n$任意位置的概率是一样，那么可以得出前$n$个参与者在第$n+1$次交换过后出现在$1 - n+1$任意位置的概率都是$\frac{1}{n+1}$。
3. 根据数学归纳法，命题得证。

虽然这个算法可以被证明可以进行随机均匀抽奖，但是不管需要抽几个人，都需要$O(n)$次交换，有没有更快的算法？当然是有的，下面介绍一个基于哈希表的随机均匀抽奖算法。

3.3 基于哈希表的快速随机均匀抽奖算法

talk is cleap, show the code:

// random pick m items from n candidates
std::vector<int> RandomPick(int n, int m) {
    std::vector<int> result;
    std::unordered_map<int, int> hashmap;
    auto Get = [&hash_map](int k) {
        auto iter = hashmap.find(k);
        return iter == hashmap.end() ? k : iter->second;
    };
    for (int i = 0; i < m; i++, n--) {
        int rnd = G(n);
        result.push_back(Get(rnd));
        hashmap[rnd] = Get(n - 1);
    }
    return result;
}

这个算法其实更贴合现实生活中抽奖的流程。目标是从$n$个参与者中随机均匀抽出$m$个中奖者，那么先随机抽出1个中奖者，随后将其移出候选池，继续随机抽，直到抽完$m$个。所以上述代码的精髓在第12行，没看懂的读者可以细细品味。

算法的正确性已经十分显然，只要学过中学的初等概率，就可以容易证明，所以此处略去。交换次数也容易证明是$O(m)$次。

4 总结

根据以上算法，可以解答前言中的面试题了。首先是随机数生成器的转换，然后是具体的随机交换过程。下次面试遇到这个问题，你知道怎么秀面试官一脸了吗？

注1：以上代码均即兴编写，未经过严谨的运行测试或对输出的假设检验，如有读者发现谬误，烦请指正，万分感谢。

注2：以上推演和证明均本人所写，囿于本人水平，行文可能有不足之处，如有读者发现谬误，也烦请指正，便于本人改进，万分感谢。