probability and programming simulation

I'm having some trouble understanding the following result.

I want to know if the following code is开发者_JAVA技巧 actually correct. It stumps me - but that could be due to me misunderstanding the probability involved.

The code should speak for itself, but to clarify the 'real world' simulation represents 2 people flipping a coin. When you lose you pay 1 dollar, when you win you win a dollar. An even sum game!

private static Random rnd = new Random();
public static void main(String[] args) {
   int i=0;
   for (int x = 0; x<1000000; x++) {
      if (rnd.nextBoolean())  i+=1; 
      else  i-=1; 
    }
    System.out.println(i);
 }

When I run this however I get huge swings! Whilst I would expect a large sample like this to converge to 0, I'm seeing +-4000

Not only that but increasing the sample size seems to only make the swings higher.

Am I misusing the random function ? :P

I think you're good. The thing to look at is the ratio of the swing to your sample.

4000 out of 1000000 for example is 0.4%

If you increase the sample size, you should expect that ratio to go down.

The results of your experiment should follow a binomial distribution. If the number of trials is N, and the probability of success p=1/2, then the number of successes N_success (for large enough N) should have a mean of approximately Np, and standard deviation sqrt(N*p*(1-p)).

You're actually tracking K = (N_success - N_fail). So N_success = N/2 + K/2. With 1,000,000 trials and K=4000, we get N_success = 502000. The expected value is 500000, with standard deviation sqrt(250000) = 500. The difference between the observed and expected values of N_success is 2000, or about 4 sigma. That's significant enough to question whether the random number generator is biased. On the other hand, if you're running this test thousands of times, you'd expect a few outliers of this magnitude, and you seem to be seeing both positive and negative values, so in the long run maybe things are OK after all.

You are simulating a one-dimensional random walk. Basically, imagine yourself standing on a line of integers. You begin at point i=0. With equal probability you take a step to the right or the left.

The random walk has a few cool properties and you've touched on my favourite:

• Starting at point i=0, as N gets larger, the probability that you will return to that point approaches 1. As you point out - a zero sum game.
• However, the expected time it will take you to return there tends to infinity. As you notice, you get some very large swings.

Since the average value should be 0 and the variance of N moves is N, then you would expect 95% of your simulations to end in the region: (- 1.96, 1.96)*N^(0.5).