Random Walks

Brownian Motion describes the movement of small particles in suspension in liquids. This motion is observed to be in a zig-zag path due to the collisions of the molecules in the liquid with the small particles, each collision impacting momentum on the small particles.

Random walks can be generated on the computer using pseudo-random numbers. An easy way to generate a random walk is to do so on a square lattice. The model is that of a walker who starts at an arbitrary location on a two dimensional lattice with equal spacing in both directions, 1 and 2. At that intersection the random walker decides to go north, east, south or west at random with an equal probability for each outcome. Once decided to go in a specific direction the random walker takes one step in the given direction. This one step takes him to the adjacent site. Then the random walker takes subsequent steps following the same algorithm. The program random_walk.c implements this procedure.

The basic block of random_walk.c is a function to generate the random decision for the walker step. The intrinsic C function, rand() , generates a random integer between 0 and a maximum value MAX_RND. A simple scaling brings the random into a double C variable between 0 and 1. Assuming uniformity in the distribution of the numbers a simple structure of if statements allows to decide if the random number falls in the interval [0.0, 0.25] [0.25, 0.50], [0.50, 0.75] or [0.75, 1.00]. Depending on the value of the random number generated by rand() a number 0, 1, 2 or 3 is thus returned from the function. This allows the algorithm to decide which way the random walker will take his step.

Random_walk.c can generate various random walks as specified by the parameter -w # on the command line. These walks are based on the same sequence of random numbers generated by rand() except for the fact of using different groups of numbers from the sequence. Therefore the random walks are all very different. These are best illustrated via the graphic techniques described in the next section.

Note that the random walks generated by random_walk.c appear to have different lengths. That is, the last step takes the random walker at different distances from the origin of the walk at position [0,0] on the lattice. This is perfectly normal given that the walks are totally at random.

A random walk can also be generated via steps of non-uniform lengths. For instance, more randomness can be introduced in the walk if the random walker is to decide the length of the step to take as well as its direction. For instance, the random walker at the given location could take a step based on random numbers with Gaussian distribution to provide the length of the step and a random choice between the directions north, east, south or west. The latter can also be generalized to a random angle between $0$ and $2 \pi$. This will generate random walks of very different topology than the random walk on a lattice.