CODEWITHSUNDEEP
javaalgorithmrandomrandom-walk
Sraw
Sraw

Reputation: 20264

What causes Java version Random walk doesn't converge to expected value?

Basically, I implemented a Random walk program in Java. And I know the distance should converge to l * (n ^ 0.5)(l is the step length, n is the total steps). If let l equals to 1, then d = n ^ 0.5 or in other words: d = sqrt(n).

But, strangly, although I cannot find any error in my code, it just converges to unexpected value. For example, given l = 1, n = 100, d should converge to 10, but actually it converges to 8.86 after 1000000 times experiments.

Here is my code:

public class RandomWalk {
    private int x = 0;
    private int y = 0;

    private final Random random = new Random();

    private void move(int dx, int dy) {
        x += dx;
        y += dy;
    }

    private void randomWalk(int m) {
        for (int i = 0; i < m; i++)
            randomMove();
    }

    private void randomMove() {
        boolean xOry = random.nextBoolean();
        boolean plusOrminus = random.nextBoolean();
        int delta = plusOrminus ? 1 : -1;
        int dx = xOry ? delta : 0, dy = xOry ? 0 : delta;
        move(dx, dy);
    }

    public double distance() {
        return Math.sqrt(Math.pow(x, 2) + Math.pow(y, 2));
    }

    public static double randomWalkMulti(int m, int n) {
        double totalDistance = 0;
        for (int i = 0; i < n; i++){
            RandomWalk walk = new RandomWalk();
            walk.randomWalk(m);
            totalDistance += walk.distance();
        }
        return totalDistance/n ;
    }
}

I've thought some possiblities. First I think it may be caused by that the generated boolean by random has bias. Second I think it may be caused by float precision lost. But as this is just a very simple use case, I don't think these two situations are possible.

Could any one tell me why it doesn't work as expected?

Upvotes: 0

Views: 141

Answers (1)

ruakh
ruakh

Reputation: 183602

I don't think it's true that the distance should average out to √n. According to https://math.stackexchange.com/questions/103142/expected-value-of-random-walk, the square of the distance should average out to n, but that's not the same thing (since the average of the square roots of a set of numbers is not the same as the square root of their average).

Upvotes: 1

Related Questions