One-dimensional random walk

Introduction

The program simulates a random walk in one dimension. A walker starts at the origin and takes N steps. At each step the walker goes to the right with probability p and to the left with probability (1 - p). Each step is the same length and independent of the previous steps. What is the displacement of the walker after N steps? Because of the many random choices of the walker, the final position of the walker varies each time the simulation is done. Are some displacements more likely than others?

    We can determine the answer to this question by performing a large number of trials, where each trial consists of a N step walk. At the end of each trial, the displacement x of the walker from the origin is recorded. We then construct a histogram for the number of times that the displacement x is recorded for a given number of trials. The probability that the walker will be a distance x from the origin after N steps is proportional to the corresponding value of the histogram.

Algorithm

The program constructs a histogram by performing a large number of trials. At the end of each trial, the appropriate histogram entry is incremented, that is H(x) = H(x) + 1. Note that the horizontal axis ranges from x = -N to N. The default probability is p = 1/2, which represents an equal probability of going to the right or to the left, and generates a symmetric distribution. The number of steps N in one walk can also be changed.

Problems

  1. How does the histogram change, if at all, as the number of trials increases for fixed N?
  2. Describe the qualitative changes of the histogram for increasing values of N.
  3. What is the most probable value of x for p = 1/2 and N = 16 and N = 32?
  4. What is the approximate width of the distribution for p = 1/2 and N = 16? Define the width visually. One way to do so is to determine the value of x at which the value of the histogram is one-half of its maximum value. How does the width change as a function of N for fixed p?

Java Classes

Updated 21 December 2009.