2007-09-28
随机化
慢慢开始有感觉数学对写程序有很多影响.真后悔上上学期的离散数学和概率老是逃课!!
拜读了云风老大的"泊松分布"联想到要有较好的数学和概率基础才能搞出所谓的随机化算法.
搞一个例子吧:
泊松分布一般适用于发生一次的概率很小事件.例如:一门很容易的考试,结果还是有一两个不及格(失礼了,小弟曾经是其中一个.),还有比如购买彩票等等事件,中奖概率很小的事件.假如中奖概率为14000000:1,假设抽取的号码是随机的而且独立的,如果一个人购买彩票越多,中奖概率增加,但两个人买一样多的彩票,概率不会增加,因为是事件独立的.
当中奖人数的期望为2时的彩票中奖者分布如下所示:
中奖彩票数 0 1 2 3 4 5
概率 0.135 0.271 0.272 0.180 0.090 0.036
为了产生一个泊松分布且期望为a的随机无符号数,可以采用重复产生区间(0,1)中均匀分布的随机数直至乘积小于或等于e^(-a),(引用一本国外有关教材采用的策略)在程序代码中把均匀分布的随机数的对数相加,直至所产生的和小于或等于-a.
代码如下:
package kitsion.util;
/*Random number clas, using a 31-bit
线性同余数算法产生均匀分布(linear congruential generator)
*/
public class Random2
{
private static final int A = 48271;
private static final int M = 2147483647; //=2^31-1,素数
private static final int Q = M/A;
private static final int R = M%A;
private int state;
/*
*Construct this Random object with initial state obtained from system clock.
*/
public Random2()
{
this((int)(System.currentTimeMillis() % Integer.MAX_VALUE));
}
/*
*Construct this Random object with specified initial state.
*@param initialValue the initial value
*/
public Random2(int initialValue)
{
if(initialValue < 0)
initialValue += M;
state = initialValue;
if(state <= 0)
state = 1;
}
/*
*Return a preudorandom int, and change the initial state.
*/
public int nextInt()
{
int tmpState = A * (state % Q) - R * (state / Q);
if(tmpState >= 0)
state = tmpState;
else
state = tmpState + M;
return state;
}
/*
*Return a pseudorandom double in the open range0..1
*and change the internal state
*@return the pseudorandom double
*/
public double nextDouble()
{
return (double)nextInt() / M;
}
/*
*Return an int using a Poisson distribution, and change the internal state.
*@param expectedValue the mean of the distribute
*@return the pseudorandom int.(柏松分布,由均匀分布产生非均匀分布)
*/
public int nextPoisson(double expectedValue)
{
double limit = -expectedValue;
double product = Math.log(nextDouble());
int count;
for(count = 0; product>limit; count++)
product += Math.log(nextDouble());
return count;
}
/*
*Method to swap to elements in an array.
*@param a an array of objects
*@param index1 the index of the first object.
*@param index2 the index of the second object
*/
private static final <AnyType> void swapReferences(AnyType[] a, int index1, int index2)
{
AnyType tmp = a[index1];
a[index1] = a[index2];
a[index2] = tmp;
}
//Test program
public static void main(String[] args)
{
Random2 r = new Random2();
for(int i = 0; i < 20; i++)
{
System.out.println(r.nextInt());
}
int[] dist = new int[10000];
final int SAMPLES = 1000000;
for(int i = 0; i < SAMPLES; i++)
dist[r.nextPoisson(2)]++;
for(int i = 0; i < 10; i++)
System.out.println(i + "中奖概率: " + dist[i] / (double)SAMPLES);
}
}
运行结果:
1379218482
2114803975
920033433
972024383
218788490
1962108491
320201773
1019977024
2100834382
903674888
1602680784
2053224936
555609312
2041315816
1216095188
665329203
488017128
1326661745
1326739355
778084371
0中奖概率: 0.13589
1中奖概率: 0.270387
2中奖概率: 0.270704
3中奖概率: 0.18035
4中奖概率: 0.090164
5中奖概率: 0.036003
6中奖概率: 0.011939
7中奖概率: 0.003439
8中奖概率: 8.86E-4
9中奖概率: 1.95E-4
拜读了云风老大的"泊松分布"联想到要有较好的数学和概率基础才能搞出所谓的随机化算法.
搞一个例子吧:
泊松分布一般适用于发生一次的概率很小事件.例如:一门很容易的考试,结果还是有一两个不及格(失礼了,小弟曾经是其中一个.),还有比如购买彩票等等事件,中奖概率很小的事件.假如中奖概率为14000000:1,假设抽取的号码是随机的而且独立的,如果一个人购买彩票越多,中奖概率增加,但两个人买一样多的彩票,概率不会增加,因为是事件独立的.
当中奖人数的期望为2时的彩票中奖者分布如下所示:
中奖彩票数 0 1 2 3 4 5
概率 0.135 0.271 0.272 0.180 0.090 0.036
为了产生一个泊松分布且期望为a的随机无符号数,可以采用重复产生区间(0,1)中均匀分布的随机数直至乘积小于或等于e^(-a),(引用一本国外有关教材采用的策略)在程序代码中把均匀分布的随机数的对数相加,直至所产生的和小于或等于-a.
代码如下:
package kitsion.util;
/*Random number clas, using a 31-bit
线性同余数算法产生均匀分布(linear congruential generator)
*/
public class Random2
{
private static final int A = 48271;
private static final int M = 2147483647; //=2^31-1,素数
private static final int Q = M/A;
private static final int R = M%A;
private int state;
/*
*Construct this Random object with initial state obtained from system clock.
*/
public Random2()
{
this((int)(System.currentTimeMillis() % Integer.MAX_VALUE));
}
/*
*Construct this Random object with specified initial state.
*@param initialValue the initial value
*/
public Random2(int initialValue)
{
if(initialValue < 0)
initialValue += M;
state = initialValue;
if(state <= 0)
state = 1;
}
/*
*Return a preudorandom int, and change the initial state.
*/
public int nextInt()
{
int tmpState = A * (state % Q) - R * (state / Q);
if(tmpState >= 0)
state = tmpState;
else
state = tmpState + M;
return state;
}
/*
*Return a pseudorandom double in the open range0..1
*and change the internal state
*@return the pseudorandom double
*/
public double nextDouble()
{
return (double)nextInt() / M;
}
/*
*Return an int using a Poisson distribution, and change the internal state.
*@param expectedValue the mean of the distribute
*@return the pseudorandom int.(柏松分布,由均匀分布产生非均匀分布)
*/
public int nextPoisson(double expectedValue)
{
double limit = -expectedValue;
double product = Math.log(nextDouble());
int count;
for(count = 0; product>limit; count++)
product += Math.log(nextDouble());
return count;
}
/*
*Method to swap to elements in an array.
*@param a an array of objects
*@param index1 the index of the first object.
*@param index2 the index of the second object
*/
private static final <AnyType> void swapReferences(AnyType[] a, int index1, int index2)
{
AnyType tmp = a[index1];
a[index1] = a[index2];
a[index2] = tmp;
}
//Test program
public static void main(String[] args)
{
Random2 r = new Random2();
for(int i = 0; i < 20; i++)
{
System.out.println(r.nextInt());
}
int[] dist = new int[10000];
final int SAMPLES = 1000000;
for(int i = 0; i < SAMPLES; i++)
dist[r.nextPoisson(2)]++;
for(int i = 0; i < 10; i++)
System.out.println(i + "中奖概率: " + dist[i] / (double)SAMPLES);
}
}
运行结果:
1379218482
2114803975
920033433
972024383
218788490
1962108491
320201773
1019977024
2100834382
903674888
1602680784
2053224936
555609312
2041315816
1216095188
665329203
488017128
1326661745
1326739355
778084371
0中奖概率: 0.13589
1中奖概率: 0.270387
2中奖概率: 0.270704
3中奖概率: 0.18035
4中奖概率: 0.090164
5中奖概率: 0.036003
6中奖概率: 0.011939
7中奖概率: 0.003439
8中奖概率: 8.86E-4
9中奖概率: 1.95E-4
评论排行榜