作者：百变睛灵_345 | 来源：互联网 | 2024-11-08 14:23
假设我们拥有一台以概率\(p\)生成0和以概率\(q\)生成1的{0,1}随机生成器，如何利用这台生成器构建一个能够均匀生成12个0或1的新生成器？解决方案的核心在于设计一种方法，使得新生成器在生成序列时能够保持均匀分布。具体而言，可以通过多次调用原始生成器，并采用适当的组合策略来实现这一目标。例如，可以使用二进制编码和拒绝采样技术，确保最终生成的12位序列具有等概率分布。这种方法不仅能够保证生成结果的均匀性，还能够在计算效率上达到较高的水平。
1.假设我有个{0,1}生成器&＃xff0c;生成0的概率为p,生成1的概率为q,如何通过此发生器获得一个均为1/2的{0,1}生成器呢&＃xff1f;
【答】思路&＃xff1a;寻找两个等概率事件。易知连续投掷两次获得01或者10的概率均为p(1-p) &＃61;Y&＃xff0c;因此如果我们连续生成两个数&＃xff0c;如果获得00或者11概率为U&＃61;p^2&＃43;(1-p)^2&＃xff0c;则继续再获取两个数&＃xff0c;直到获取到10或者01为止。概率为(1&＃43;U&＃43;U^2&＃43;U^3&＃43;...)*Y 求极限为Y*(1/(1-U))&＃61;0.5
因此 我们得到了想要的&＃xff0c;我们可以认为最终得到10的为事件0&＃xff0c;最终得到01的为事件1&＃xff0c;这样子就达到目的了。
2.假设我有一个随机数生成器范围为{1,2,3,4,5} 如何获得一个等概率的{0&＃xff0c;1}生成器
【答】思路&＃xff1a;同样采取上题的思路构造两个等概率事件&＃xff1a;事件A: 不停生成数 直至生成的数A<3 事件B 不停生成数直至生成数A>3 同样可以证明这个两个事件发生概率都是0.5
3. 假设我有一个随机数生成器范围为{1,2,3,4,5} 如何获得一个{1-n}的等概率随机生成器
【答】思路&＃xff1a;
&＃xff08;1&＃xff09;首先我们获得一个{0,1}等概率生成器
&＃xff08;2&＃xff09;我们获得一个XXX的随机二进制序列表示范围(0,1,2,...,2^k-1)。其中2^(K-1)<&＃61;n<2^k
&＃xff08;3&＃xff09;定义n个事件 其中M事件为:如果XXX属于{n&＃43;1,2^k-1}则再生成一个XXX的随机序列属于{0,1,2,..,n} 其中XXX&＃61;M的概率为1/n
扩展解法&＃xff1a;已 知一随机发生器&＃xff0c;产生0的概率是p&＃xff0c;产生1的概率是1-p&＃xff0c;现在要你构造一个发生器&＃xff0c;使得它构造0和1的概率均为1/2&＃xff1b;构造一个发生器&＃xff0c;使得它构造1、 2、3的概率均为1/3&＃xff1b;...&＃xff0c;构造一个发生器&＃xff0c;使得它构造1、2、3、...n的概率均为1/n&＃xff0c;要求复杂度最低。
首先是1/2的情况&＃xff0c;我们一次性生成两个数值&＃xff0c;如果是00或者11丢弃&＃xff0c;否则留下&＃xff0c;01为1&＃xff0c;10为0&＃xff0c;他们的概率都是p*(1-p)是相等的&＃xff0c;所以等概率了。
然 后是1/n的情况了&＃xff0c;我们以5为例&＃xff0c;此时我们取x&＃61;2&＃xff0c;因为C(2x,x)&＃61;C(4,2)&＃61;6是比5大的最小的x&＃xff0c;此时我们就是一次性生成4位二进制&＃xff0c;把 1出现个数不是2的都丢弃&＃xff0c;这时候剩下六个:0011,0101,0110,1001,1010,1100&＃xff0c;取最小的5个&＃xff0c;即丢弃1100&＃xff0c;那么我们对于 前5个分别编号1到5&＃xff0c;这时候他们的概率都是p*p*(1-p)*(1-p)相等了。
关键是找那个最小的x&＃xff0c;使得C(2x,x)>&＃61;n这样能提升查找效率
PS&＃xff1a;C(2x,x)的意思是生成2x位的二进制数&＃xff0c;其中x位为1&＃xff0c;x位为0&＃xff0c;那么这样的数的概率都为p^x * (1-p)^x,在这样的数种取最小的前n个数即可.....
京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有 