1
$\begingroup$

I'm wondering why if I increase the number of step in a set of simulation of a random walk on a grid the distance from the origin is higher.

If I can move on the grid in 4 directions, there are 0.5 chance of getting closer to origin and 0.5 of getting farther.

This is a simple javascript example (well, here maybe I made some other errors because the points ends always with a negative x and a positive y, or maybe I just cannot rely on javascript random function in this case)

var steps = 100; //number of steps for each simulation (initially)
var simulations = 100; //number of total simulation
var points = Array.from({length:simulations}, () => ({x:0,y:0})); // init the array of points from the origin

//the 4 possible moves
var moves = [{x:0,y:1},{x:1,y:0},{x:0,y:-1},{x:-1,y:0}];
//ranom util function
var random = (max) => parseInt(Math.random() * max)

for (var s=0;s < simulations;s++) {
    //note the steps are increasing: 100,200,300,...,1000
    for (var i=1;i <= steps * s;i++) {  
        let move = moves[random(4)];
        //console.log(move)
        points[s].x += move.x
        points[s].y += move.y
        //console.log(s, move)
    }
    console.log(`simulation n.${s} total steps: ${steps*s}`, points[s].x, points[s].y, `distance: ${Math.abs(points[s].x) + Math.abs(points[s].y)}` )

}

EDIT: thanks to @GASSA I fixed my code, but watching the results I'm still in doubt: the distance actually is not increased (see the graph below). Not sure what's the problem..

enter image description here

$\endgroup$
  • 1
    $\begingroup$ Also, note that the line var moves = [{x:0,y:1},{x:0,y:1},{x:0,y:-1},{x:-1,y:0}]; is buggy: one of {x:0,y:1} should be {x:1,y:0} instead. $\endgroup$ – Gassa Aug 5 '18 at 22:51
  • $\begingroup$ @Gassa thanks, please see my edit and the graph, it would be nice make this code works like a random walk should behaves :) $\endgroup$ – alfredopacino Aug 6 '18 at 14:17
  • $\begingroup$ To edit: what makes you think the distance does not increase? As per @D.W.'s answer, the distance normally is on the order of sqrt(n). The square root of 10000 is 100, and a distance on the order of a hundred or two is what we seem to see on your graph, as far as scale and resolution permit. $\endgroup$ – Gassa Aug 6 '18 at 20:32
  • $\begingroup$ @Gassa sorry I noticed I plot the data in the dumbest way possible, please see the new graph $\endgroup$ – alfredopacino Aug 6 '18 at 21:39
  • $\begingroup$ It looks fine to me. $\endgroup$ – Gassa Aug 6 '18 at 21:42
3
$\begingroup$

It's easiest to understand with a one-dimensional random walk. After $n$ steps, the typical value for the distance from the origin is proportional to $\sqrt{n}$. Thus, the more steps you take, the greater the typical distance from the origin. For an analysis and explanation, see https://en.wikipedia.org/wiki/Random_walk#One-dimensional_random_walk. The math is well-developed in many standard places, so I'm not going to repeat it here.

$\endgroup$
1
$\begingroup$

A two-dimensional random walk is equivalent to two independent one-dimensional random walks running in parallel. To see this, rotate the plane 45 degrees. The possible steps are all four diagonals, and each one corresponds to both a step in the horizontal direction and a step in the vertical direction.

The horizontal displacement after $n$ steps is the sum of $n$ random $\pm 1$ steps. According to the central limit theorem, its distribution is roughly normal with mean zero and variance $n$. Consequently, the absolute horizontal displacement is of expected order $\sqrt{n}$. The same is true for the absolute vertical displacement, and so for the distance from the origin.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.