Mas*_*ler 3 language-agnostic random algorithm
假设我有一个例程,当被调用时,将使用RNG并返回True30%的时间或False其他.这很简单.但是,如果我想模拟一下True如果我将该例程调用100亿次,我会得到多少结果呢？
在一个循环中调用它100亿次将花费太长时间.将100亿乘以30%将产生30亿的统计预期结果,但不会涉及实际的随机性.(和几率的结果将是准确 3十亿是不是所有的伟大.)
是否有一个算法来模拟这样一系列随机事件的聚合结果,这样如果它被多次调用,它给出的结果将显示与实际运行它模拟多次的随机序列相同的分布曲线. O(1)时间(即,随着要模拟的系列的长度增加,运行时间不会更长)？
我会说 - 它可以在O(1)中完成!
描述您的情况的二项分布可以(在某些情况下)通过正态分布来近似.它可以当两个来完成n*p,并n*(1-p)有大于5,所以p=0.3它可以为所有来完成n > 17.当n变得越来越大(如数百万)时,近似越来越好.
使用Box-Muller变换可以容易地计算具有正态分布的随机数.您需要做的只是0和1之间的两个随机数.Bed-Muller变换从N(0,1)分布中给出两个随机数,称为标准法线.N(?, ?2)可以使用X = ? + ?Z公式实现,其中Z标准正常.