Math#random ain't so random?

问题:

I am finding something odd happening with my program.

This program basically is used for component clicking, as it is a concept to test randomness.

As you can see, it is printing correctly, as it should have a tendency to click towards the middle, which is does perfect.

Problem is, it seems biased.

import java.applet.Applet;
import java.awt.Point;
import java.io.File;
import java.io.FileWriter;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.awt.*;

public class Testing extends Applet {

/**
 * 
 */
private static final long serialVersionUID = -2441995094105327849L;

public void init() {
    setSize(WIDTH, HEIGHT);
    img = createImage(WIDTH, HEIGHT);
    g = img.getGraphics();
    paint(g);
    setVisible(true);
    g.setColor(new Color(0, 0, 0));
    g.fillRect(0, 0, WIDTH, HEIGHT);
    g.setColor(new Color(55, 55, 55, 55));
    main();
}

public final static int WIDTH = 400, HEIGHT = 400;
public static int[] widths = new int[WIDTH], heights = new int[HEIGHT];
public static ArrayList<String> set = new ArrayList<String>();
public Image img;
public Graphics g;

public void paint(Graphics g) {
    g.drawImage(img, 0, 0, null);
}

public void update(Graphics g) {
    paint(g);
}

public void main() {
    int count101 = 0;
    int count100 = 0;
    int count99 = 0;
    try {
        PrintWriter pw = new PrintWriter(new FileWriter(
                new File("Data.dat")));
        Point center = new Point(WIDTH / 2, HEIGHT / 2);

        int runs = 10000000;

        for (int i = 0; i < runs; i++) {
            int x = center.x
                    - (int) ((Math.random() - Math.random())
                            * Math.random() * center.x);
            int y = center.y
                    - (int) ((Math.random() - Math.random())
                            * Math.random() * center.y);
            widths[x]++;
            heights[y]++;
            repaint();
            g.fillRect(x, y, 1, 1);
            if((x & y) == 101){
                count101++;
            }
            if((x & y) == 100){
                count100++;
            }
            if((x & y) == 99){
                count99++;
            }
        }
        System.out.println(count101);
        System.out.println(count100);
        System.out.println(count99);
        repaint();
        pw.flush();
        pw.close();
    } catch (IOException e) {
        e.printStackTrace();
    }
}
}

This constantly prints biased results.

It prints the following:

3640
10918
3741

This is considerably biased because it follows a trend for the most part, following a linear increase with all the other values, but once it reaches the 100 mark it decides that it is going to drop the bomb and pick it 6% more then every other.

Anyone know any reasoning for this?

Oh, by the way, I do have a txt file containing every result printed out with repetition of 10,000,000 times with percentages etc, it is quite long so I won't post, but I do have the info.

回答1:

It is neither Java Math.rand() nor pseudo random generation problem. This is causing the weird (but expected) behaviour:

Math.random() - Math.random()

The sum (and subtraction) of two uniformly distributed random variables do not result in uniformly distributed variable. As far as I remember they result in triangular distribution:

See: Distribution of mean of two standard uniform variables.

This is what you are seeing - a perfect illustration of 2-dimensional random variable with triangular distribution. Moreover, if you keep adding uniformly distributed random variables you will eventually get normal distribution.

To achieve uniform distribution all you have to do is replace awkward:

int x = center.x
                - (int) ((Math.random() - Math.random())
                        * Math.random() * center.x);

with simple:

int x = (int) (Math.random() * center.x * 2);

Your code (without multiplication) generates random variable with possible values from 0 to center.x * 2 and with expected value at center.x. So far so good. But the distribution is trangular which means the probability density is not equal in that range.

Multiplication of two random variables (out of which one is no longer uniformly distributed) has even more complex distribution, but certainly not uniform.

The latter code snippet generates a simple, uniformly distributed variables with probability density function equal in the whole space.

Side note

In your program it is an obvious math mistake, but pseudo-random generator can in fact generate "non-random" patterns in space. Have a look at Strange Attractors and TCP/IP Sequence Number Analysis, image from that article:

3d-space http://lcamtuf.coredump.cx/oldtcp/tcpseq/data.jpg

回答2:

Instead of using Math.random(), use java.util.Random. First, seed the random generator with the current time:

Random randGenerator = new java.util.Random(System.currentTimeMillis());

then generate one random after another.

randGenerator.nextDouble();

回答3:

Seeding the random in this case doesn't do much as it already uses System.nanoTime() to seed itself:

public Random() { this(++seedUniquifier + System.nanoTime()); }
private static volatile long seedUniquifier = 8682522807148012L;

The Math.random() method re-uses the same Random over and over, and uses the default constructor to build it.

The issue is that you're doing calculations on two random numbers which changes distribution.