作者：彭彭宅男丶 | 来源：互联网 | 2023-08-04 09:47
转自：http:blog.csdn.netfish1094articledetails6886235今天记录下和概率发生器有关的几个算法1.假设我有个{0,1}生成
转自&＃xff1a;http://blog.csdn.net/fish1094/article/details/6886235
今天记录下和概率发生器有关的几个算法
1.假设我有个{0,1}生成器&＃xff0c;生成0的概率为p,生成1的概率为q,如何通过此发生器获得一个均为1/2的{0,1}生成器呢&＃xff1f; 【答】思路&＃xff1a;寻找两个等概率事件。易知连续投掷两次获得01 or 10的概率均为p(1-q) &＃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 因此 我们得到了想要的。 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
京公网安备 11010802041100号