随机化

慢慢开始有感觉数学对写程序有很多影响.真后悔上上学期的离散数学和概率老是逃课!!
拜读了云风老大的"泊松分布"联想到要有较好的数学和概率基础才能搞出所谓的随机化算法.
搞一个例子吧:
泊松分布一般适用于发生一次的概率很小事件.例如:一门很容易的考试,结果还是有一两个不及格(失礼了,小弟曾经是其中一个.),还有比如购买彩票等等事件,中奖概率很小的事件.假如中奖概率为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