|
|
楼主 |
发表于 2009-9-22 10:33:29
|
显示全部楼层
能够满足任意精度的概率事件发生器
#include<iostream.h>
#include<time.h>
#include<stdlib.h>
#define MinProb 3.05185094759972e-5
bool happened(double probability)//probability 0~1
{
if(probability<0)return false;
if(probability<MinProb)
return rand()==0&&happened(probability/MinProb);
if(rand()<=probability*RAND_MAX)
return true;
return false;
}
MinProb是理论上的最小发生概率，为什么会这样，因为计算机是离散的，它永远只能得到有限范围内的随机离散数。
bool happened(double probability);
是按概率probability发生的随机事件发生器，如当probability=0.5时，将等概率得到真或者假，当为其它值时，将按probability的概率得到真，以1-probability的概率得到假。
如果probability比较大，MinProb是足够精确的，如0.5和0.5000001是有足够精确相等的，它相当于一个大概率加一个小概率，小概率被‘吃’掉了。
而小概率事件单独发生能不能突破MinProb的极限呢？
我昨天睡觉的时候想出来了这样的算法，从理论上是可以无限精确的，即任意小的小概率事件都可以得到。
其实原理非常简单，即独立事件同时发生的概率等于各事件的概率之积。举个例子：
void main()
{
long happen=0;
for(long i=0;i<10000;++i)
if(happened(0.5)&&happened(0.5))++happen;
cout<<happen<<endl;
}
两个概率为1/2的独立事件同时发生的概率是多少呢？1/4，即1/2*1/2，丢两个硬币，组合情况有：正正，正反，反正，反反，所以正正发生的概率是1/4。
所以我可以把小概率事件分成若干较大概率的事件的同时发生来得到。
if(probability<MinProb)
return rand()==0&&happened(probability/MinProb);
rand()==0发生的概率就是MinProb，合起来的概率就是probability，这样的递归是受到&&运算的短路运算而优化了的，如果MinProb的事件不会发生，那更小的事件更加不会发生，也就不会继续递归下去了。我喜欢C。
我的测试程序：
void main()
{
long happen,total;
srand(time(0));
double prob;
cout<<"输入发生概率(0~1):";
while(cin>>prob)
{
cout<<"统计次数:";
cin>>total;
happen=0;
for(long i=0;i<total;++i)
if(happened(prob))happen++;
cout<<"发生了"<<happen<<"次"<<endl
<<"发生概率近似为"<<((double)happen/total)<<endl;
cout<<"输入发生概率(0~1):";
}
}
我有输入：
输入发生概率(0~1):0.0000005
统计次数:100000000
发生了47次
发生概率近似为4.7e-007 |
|
发表于 2009-9-19 16:35:47
