Walking on a Grid

21. Galactic Gridlock

Walking on a Grid

It's easy to extend the random walk model to two dimensions. Take steps to the north, south, east, or west, randomly choosing the direction of each step with equal probability. Instead of flipping a coin, you could toss a four-sided (tetrahedral) die.

A tetrahedral die has four sides.

You can imagine this walk going from vertex to vertex on an infinite checkerboard. If such a walk continues for long enough, the walker is certain to touch every vertex and also to make a return visit to the starting point.

Example of a two-dimensional random walk on a square grid, shown step by step.

TRY IT!

Record a random walk in two dimensions.

You will need:

• sheet of graph paper (or draw your own grid with pencil, paper, and a ruler)
• die (you can use a regular six-sided die and ignore two of the numbers when they come up, but a tetrahedral die is cooler, because you need only four sides, one for each of the four directions)
• pencil

What to do:

1. Mark a vertex somewhere hear the middle of your grid as your starting point. Each roll of the die will determine the direction you take—right, left, up, or down—to one of the four vertices closest to your starting point.
2. Roll the die to determine your direction: If you roll a 1, step up; a 2, step right; a 3, step down; a 4, step left. If you use a six-sided die and roll a 5 or 6, ignore it and roll again.
3. Draw your route on the grid as you travel. This is not a self-avoiding random walk, so you are allowed to return to a vertex you have already visited.
4. Observe your path. Does it suggest any sort of pattern? If you take enough random steps, you will eventually return to your starting point. In fact, an infinitely long random walk will visit every point on the grid an infinite number of times!
5. Repeat steps 2 and 3, but this time take a self-avoiding random walk. In other words, if the direction determined by rolling your die would take you to a vertex you have already visited, stay put and roll again. How does the route of your self-avoiding path compare with your first path? Could you get stuck in a dead end with no place to move?

Example of a two-dimensional self-avoiding random walk.

Answers:

In a regular (not self-avoiding) random walk your path is darkest around the starting point because the close-in vertices are the ones you end up visiting more frequently. It looks sort of like a road map, where roads and other landmarks are most dense in a city, and fan out around the city's edges.

In a self-avoiding random walk your route may form a similar pattern, but you could get trapped at a point where the only possible move is to a place where you have already been.

NEXT: Wandering in Space