讨论下算法导论第5章一道概率题

win_hate

原帖由 tyc611 于 2008-7-12 11:51 发表

我曾经和同学讨论过用random(0, 1)来产生目标数的二进制位，但问题在于，当目标数不是2^n时无法做到等概率

扩大范围，丢掉不合格的就可以了。

win_hate

比如一个机器，等概率吐出 1,2,3,4

如果把输出的 4 全丢掉，则 1,2,3 是等概率的。

tyc611

原帖由 win_hate 于 2008-7-12 11:58 发表
比如一个机器，等概率吐出 1,2,3,4

如果把输出的 4 全丢掉，则 1,2,3 是等概率的。

问题是去年不合格的后，需要重新产生，此时还会等概率吗？我再好好想想

tyc611

原帖由 win_hate 于 2008-7-12 11:58 发表
比如一个机器，等概率吐出 1,2,3,4

如果把输出的 4 全丢掉，则 1,2,3 是等概率的。

把合法子集和非法子集看作一个整体，这样看来确实是等概率的

zylthinking

原帖由 win_hate 于 2008-7-12 11:36 发表


看不懂，后面累加的含义是什么？

累加是奇数的情况下的处理， 因为要估计到严格的概率相等, 偶数可以根据random(0, 1)返回值进入区间的前半部分或后半部分， 但如果区间不能均分， 则这个办法不能用， 否则不能保证严格的等概率。 所以只能使用多个random(0, 1)相加达到这个效果： 这个效率比较低， 所以在偶数区间的情况下， 就不会使用了

zylthinking

原帖由 tyc611 于 2008-7-12 11:49 发表

1. 你的random(b)应该产生[0, b]，因此，b % 2的判断是错误的（因为这里有b + 1个数）
2. 后面的循环产生的b + 1个数的每个数的概率是不均等的。举个简单的例子：产生0和b的概率为(1/2)^b，而不是期望的1/(b ...

第一个算是小问题， 只是个思路而已， 也没那么精确。
第二个问题我是我错了， 汗

[ 本帖最后由 zylthinking 于 2008-7-12 22:55 编辑 ]

tyc611

原帖由 zylthinking 于 2008-7-12 22:26 发表


第一个算是小问题， 只是个思路而已， 也没那么精确。
第二个问题我有点不理解， 产生0的可能性怎么就应该是(1/2)^b呢， 从[0, b]中产生一个任意数的概率应该就是 1/(b + 1), 相当于从b+1个鸡蛋里面随手挑 ...

你产生的数实质上是这种形式：n = n1 + n2 + .... + nb的形式，其中ni ＝{0, 1}，概率分别为1/2
产生总的样本数为2^b；产生的数0只有一个样本（ni = 0 for all i form 1 to b），而产生的数1有b个样本（分别为ni = 1 when i = k, ni = 0 when i != k, where 1 <= k <= b），所以产生数0和1的概率是不相等的。其它数的概率类似。

[ 本帖最后由 tyc611 于 2008-7-12 22:47 编辑 ]

zylthinking

原帖由 tyc611 于 2008-7-12 22:43 发表

你产生的数实质上是这种形式：n = n1 + n2 + .... + nb的形式，其中ni ＝{0, 1}，概率分别为1/2
产生总的样本数为2^b；产生的数0只有一个样本（ni = 0 for all i form 1 to b），而产生的数1有b个样本（分别 ...

3x, 我理解了

silverzi

为什么不用浮点？

void_while

丢弃是不行的,丢弃的情况下返回什么呢?