Probability Problems

Author Avatar
Xin Wei 8月 24, 2017
  • 在其它设备中阅读本文章

参考:概率面试题精讲_七月算法出品

构造随机数发生器

使用均匀随机数发生器rand7构造rand10随机数发生器

关键是"扔掉"不要的数
使用“七进制”,把`1-7`减去1,产生`0-6`,然后产生两位这样的数对应`0-48`,抛弃其中的`40-48`(因为这其中只有9个数),获得的数取个位数即为`0-9`的均匀分布
```cpp
int rand10() {
    int x;
    while ((x = (rand7() - 1) * 7 + rand7() - 1) >= 40)
        ;
    return x % 10 + 1;
    }
```
关键需要保障产生的中间数是均匀的, `rand2() + rand2() - 1`是不均匀的,因为1和3的概率是1/4而2的概率是1/2

不均匀随机数构造均匀随机数

一个不均匀的随机数,以概率p产生0,概率(1-p)产生1,以此构造均匀随机数发生器

产生两次,需要0和1同时出现,该路是p*(1-p)

int gen() {
    int x, y;
    while ((x = rand()) == (y = rand()))
    ;
    return x;
    }

随机变量的和

变量x和y是[0, a] 和[0, b]上的均匀分布,给一个实数z,求x + y < z的概率

如下图所示求x+y=z下方的面积与矩形面积之比

水库采样

流入若干对象,事先不知道个数,如何随机取出k个

采用数组a保存k个数
对于第i个数:

  1. 若i小于k,则存入a[i]
  2. 若大于等于k,则x = rand()%i若生成的数小于k,则令a[x]保存当前这个数,即当前这个数有1/(i+1)的概率被选中

扩展

  1. k == 1的特殊情况
  2. 若干行大文件随机选一行
  3. 不知道长度的链表随机选一个或若干个结点
  4. 带权采样

随机排列 random_shuffle

用数组a[0, 1, ..., n-1]随机产生全排列

a[i]a[i,...,n-1]交换,自己证明

for (int i = 0; i < n; ++i)
    a[i] = i;
for (int i = 0; i < n; ++i)
    swap(a[i], a[rand() % (n-i) + i]);

带权值采样

  1. 将权值转换成整数,每个值复制权重次数,然后使用水库采样