当前位置：首页 → 问答吧 → 一道概率面试题（百度）

一道概率面试题（百度）

时间：2010-08-30

来源：互联网

已知一随机发生器，产生0的概率是p，产生1的概率是1-p，现在要你构造一个发生器，使得它构造0和1的概率均为1/2；构造一个发生器，使得它构造1、2、3的概率均为1/3；...，构造一个发生器，使得它构造1、2、3、...n的概率均为1/n，要求复杂度最低；

没啥思路。

作者: ecjtubaowp 发布时间: 2010-08-30

首先是1/2的情况，我们一次性生成两个数值，如果是00或者11丢弃，否则留下，01为1，10为0，他们的概率都是p*(1-p)是相等的，所以等概率了

作者: daybreakcx 发布时间: 2010-08-30

本帖最后由 goldenfort 于 2010-08-30 16:32 编辑

让这个发生器，  发生2 次数：

有以下可能结果（ 0， 0）（ 0， 1）（ 1，0）（1，1）

如果产生  （0， 1）就算为0，如果产生（1，0）就算为1。  如果产生的是其它的，就放弃，重新发生。

3，。。。。。。n 的结果，可以类似产生

假设 p>=0.5,    以三为例子。

发生3回，  我们只取  有一回 1， 2回 0的情形。  如果 1，发生在第一回，算1，  发生在第2回，算 2，第三回，算3.

4-n 可以类推。

作者: goldenfort 发布时间: 2010-08-30

然后是1/n的情况了，我们以5为例，此时我们取x=2，因为C(2x,x)=C(4,2)=6是比5大的最小的x，此时我们就是一次性生成4位二进制，把1出现个数不是2的都丢弃，这时候剩下六个:0011,0101,0110,1001,1010,1100，取最小的5个，即丢弃1100，那么我们对于前5个分别编号1到5，这时候他们的概率都是p*p*(1-p)*(1-p)相等了

关键是找那个最小的x，使得C(2x,x)>=n这样能提升查找效率

作者: daybreakcx 发布时间: 2010-08-30

我不知道“构造一个发生器”是什么意思？

作者: ecjtubaowp 发布时间: 2010-08-30

就是每次调用你你都生成一个1到n之间的数值，使得你生成这些数值出现都等概率

作者: daybreakcx 发布时间: 2010-08-30

哦，就是像弄一个随机函数的样子，是吧。

作者: ecjtubaowp 发布时间: 2010-08-30

对，至少我是这么理解的

作者: daybreakcx 发布时间: 2010-08-30

回复 daybreakcx

这种问题，等价于有 n个球，其中 n/2 个是白球， n-n/2个是黑球。

要将这n个球排列起来，问有几种不同的排列方式。

假设有 k个排列方式，则可以用n产生出〈=k的等概率随机发生器

作者: goldenfort 发布时间: 2010-08-30