Menu
I'm having a problem with average distance in this exercise. It should be close to the sqrt of N steps, but it's lower. Can you help me to find out where is my mistake?
2D random walk. A two dimensional random walk simulates the behavior of a particle moving in a grid of points. At each step, the random walker moves north, south, east, or west with probability 1/4, independently of previous moves. Determine how far away (on average) the random walker is from the starting point after N steps. (Theoretical answer: on the order of sqrt(N).)
public class RandomWalk{
public static void main(String[] args){
int N = Integer.parseInt(args[0]);
double nextStep = 0;
double averageDistance = 0;
int COUNT = 1000;
for (int j = 0; j < COUNT; j++){
int moveWest = 0;
int moveEast = 0;
int moveSouth = 0;
int moveNorth = 0;
double distance = 0;
for (int i = 0; i < N; i++){
nextStep = Math.random()*4;
if (nextStep <= 1) ++moveWest;
else if (nextStep <= 2) ++moveEast;
else if (nextStep <= 3) ++moveSouth;
else if (nextStep <= 4)++moveNorth;
}
moveEast = moveEast - moveWest;
moveNorth = moveNorth - moveSouth;
distance = Math.sqrt((moveEast * moveEast) + (moveNorth * moveNorth));
averageDistance += distance;
System.out.println("Walker is " + distance + "\t steps away of from the starting point");
//System.out.println("Sqrt of N is " + Math.sqrt(N));
}
System.out.println("Average distance is " + averageDistance/COUNT + " steps away of from the starting point");
}
}
608
Random Walk--2-Dimensional steps are therefore required. Amazingly, it has been proven that on a two-dimensional lattice, a random walk has unity probability of reaching any point (including the starting point) as the number of steps approaches infinity.
The random walk is simple if Xk = ±1, with P(Xk = 1) = p and P(Xk = −1) = 1−p = q. Imagine a particle performing a random walk on the integer points of the real line, where it in each step moves to one of its neighboring points; see Figure 1. Remark 1. You can also study random walks in higher dimensions.
In a simple random walk, the location can only jump to neighboring sites of the lattice, forming a lattice path. In a simple symmetric random walk on a locally finite lattice, the probabilities of the location jumping to each one of its immediate neighbors are the same.
A simple model of a random walk is as follows: Start with a random number of either -1 or 1. Randomly select a -1 or 1 and add it to the observation from the previous time step. Repeat step 2 for as long as you like.
I ran a few tests on your code with aforementioned change of ranges <0,1),<1,2),<2,3), <3,4) making them even.
And you do it like that:
if (nextStep < 1) ++moveWest;
else if (nextStep < 2) ++moveEast;
else if (nextStep < 3) ++moveSouth;
else if (nextStep < 4)++moveNorth;
Notice <= becoming <.
100000 trials of 100 steps each gave those resutls:
Average distance is 8.873435509749317 steps away of from the starting point
W=2498906
E=2501447
N=2500022
S=2499625
, where W,E,N,S are summed steps for given direction during all the trials. They look fine.
Running such a test case for a couple of times reveals that there is no preferable direction. You might use other methods to get random numbers, but that would be testing generators, not your case. Your code looks ok from my point of view.
Sentence from the problem statement also gives you a clue:Theoretical answer: on the order of sqrt(N).
116
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
