Interactive Educational Modules in
Scientific Computing

Random Walk

In a random walk on a two-dimensional grid of points, successive steps are randomly chosen in the north, south, east, and west directions with uniform distribution. This module illustrates how such random walks can be used to approximate the solution to Laplace's equation, uxx + uyy = 0, on a two-dimensional domain with Dirichlet boundary conditions. Placing a grid over the domain, an approximate solution value at any desired grid point can be computed as follows. Use the grid point as starting point for a series of random walks, continuing each walk until it hits the boundary. The approximate solution value is then given by the average of the boundary values over all points where the walks terminate, which may include multiple hits of the same boundary point. This module illustrates the method just described to solve Laplace's equation on the unit square.

The user selects the spacing of the square grid by choosing the number of interior grid points along each dimension. Next the user selects the boundary conditions by defining the solution value at each of the corners of the unit square. The boundary conditions are then given by linear interpolation of the values at the corners. For u(0, 0) = a, u(1, 0) = b, u(0, 1) = c, and u(1, 1) = d, the exact solution to the Laplace equation with these boundary conditions is u(x, y) = (a + dbc) x y + (ba) x + (ca) y + a.

Interior grid points are displayed as small gray dots. By clicking one of these dots, the user chooses a grid point at which to calculate the numerical solution. This point, displayed as a slightly larger black dot, will be the starting point for the random walks. Next the user clicks Random Walk. The resulting random walk is displayed as a series of line segments moving around the grid until a boundary is reached, at which point the entire path taken by the random walk is shown, and the approximate solution value is updated to incorporate into the average the boundary value at the end of the walk. The exact solution value, calculated from the equation above, is displayed for comparison.

To reduce the time needed to obtain a reasonably accurate approximate solution value, the user can choose to take ten random walks at a time. In this mode, the random walks are calculated behind the scenes, and the module displays only a summary of the entire path for each random walk.

Boundary grid points are displayed throughout as colored dots. The color of the boundary point shows how many random walks have ended at that point thus far. The scale below the graph indicates the number of walks corresponding to the color of a boundary point. The color scale changes dynamically as the maximum number of walks ending at a boundary point increases.

Reference: Michael T. Heath, Scientific Computing, An Introductory Survey, 2nd edition, McGraw-Hill, New York, 2002. See Computer Problem 13.14 on page 521.

Developers: Evan VanderZee and Michael Heath