首页 > 代码库 > 概率问题

概率问题

2024-07-18 16:46:54   219人阅读

  • 由非等概率Rand生成随机序列

题目：已知随机函数rand(),以p的概率产生0，以1-p的概率产生1，现在要求设计一个新的随机函数Rand(), 使其以1/n的等概率产生1~n之间的任意一个数

1、该问题可以先生成一个等概率0、1生成器。由于以p的概率产生0，以1-p的概率产生1，所以00、01、10、11的生成概率分别是p^2、p(1-p)、p(1-p)和(1-p)^2，我们发现生成01和10的概率是一样的，所以我们可以标记这两个序列构造0、1等概率生成器

int gen(){    int i1 = rand();    int i2 = rand();    if(i1==0 && i2==1)        return 1;    else if(i1==1 && i2==0)        return 0;    else        return gen();    return -1;}

2、然后计算n的二进制表示的位数 k = logn + 1;

3、填充比特位

int Rand(）{    int result = 0;    for(int i = 0 ; i < k ; ++i){        if(gen() == 1)            result |= (1<<i);    }    if(result > n)        return Rand();    return result;}
  • 等概率采样问题

题目：从数据流中等概率的采样k个数字

先取前k个数字，然后后面的数字以等概率和前面的交换

证明：
采用归纳方法，假设前n个数字等概率的采样k个数字，那么每个数字被采样的概率为k/n,现在新来一个数字，变成了n+1个数字，那么每个数字被采样的概率变位k/(n+1),我们要证明这个现在假定存在n个数字，来了第n+1个数字，那么第n+1个数字被选择的概率是k/(n+1),那么我们推算其他的数字被选择的概率也是k/(n+1)P(other) = p(other|第n+1个选择)*p(第n+1个选择) + p(other|第n+1个不选择)*p(第n+1个不选择)                      =  k/n*(1-1/k)*k/(n+1) + k/n*(n+1-k)/(n+1)                      = k*(k-1) / (n *(n+1) ) + k*(n+1-k) / (n*(n+1))                      = k*n/(n *(n+1))                      = k/(n+1)得证。其余数字被选择的概率依然也是 k/(n+1)
  • Reservoir Sampling算法

计算机程序设计艺术中提到了这个算法

 Init : a reservoir with the size： k             for   i= k+1 to N                M=random(1, i);                if( M < k)                    SWAP the Mth value and ith value            end for

证明：

假设当前是i+1, 按照我们的规定，i+1这个元素被选中的概率是k/i+1那么我们现在只需要证明前i个元素出现的概率应该也是k/i+1    对这个问题可以用归纳法来证明：k < i <=N     1.当i=k+1的时候，第k+1个元素被选择的概率明显为k/(k+1), 此时前k个元素出现的概率为 k/(k+1), 结论成立。     2.假设当 j=i 的时候结论成立，此时以 k/i 的概率来选择第i个元素，前i-1个元素出现的概率都为k/i。        证明当j=i+1的情况：       即需要证明当以 k/i+1 的概率来选择第i+1个元素的时候，此时任一前i个元素出现的概率都为k/(i+1).     前i个元素出现的概率有2部分组成        ①在第i+1次选择前得出现在蓄水池中        ②得保证第i+1次选择的时候不被替换掉     由2知道在第i+1次选择前，任一前i个元素出现的概率都为k/i     考虑被替换的概率：       首先要被替换得第 i+1 个元素被选中概率为 k/i+1，其次是因为随机替换的池子中k个元素中任意一个，所以被替换的概率是 1/k，    故前i个元素中任一被替换的概率 = k/(i+1) * 1/k = 1/i+1     则没有被替换的概率为:   1 - 1/(i+1) = i/i+1     得到前i个元素出现在蓄水池的概率为 k/i * i/(i+1) = k/i+1 故证明成立

 


联系
我们