random walks, Sierpinski Triangle

Precalculus II

Class Notes, 04/27/99

Using the computer program RNDWALK we investigate the median number of steps required to move distances of 10, 15, 20, 25 and 30 units from the original position.

Each median is based on 10 trials.
Each 'step' consists of a randomly chosen 1-unit forward or backward move (e.g., chosen by a coin flip), and a randomly chosen 1-unit step to the right or left.

The results are shown below.

We attempt to linearize the results using the transformations y -> log(y) and y -> `sqrt(y).

The log transformation clearly does not linearize the data, since the constant distance increment of 5 results in a steadily decreasing increment for log(y).
The `sqrt(y) transformation, on the other hand, yields practically constant differences and is an excellent candidate for the linearizing function.

Graphing `sqrt(y) vs. x we obtain the line `sqrt(y) = .73 x, which we solve for y to get y = .53 x^2.

We translate this as saying that the number of steps is .53 times the square of the median distance.
Equivalently we say that the median distance appears to be about 1.4 times the square root of the number of steps.

The text tells us that the distance should be

dist = L * `sqrt(N), where L is the length of a move.

This is consistent with our data, where the length of a move was `sqrt(2) (1 step forward or backward, 1 step right or left--the step is thus the hypotenuse of a right triangle with legs of 1).

Making N steps of length `sqrt(2), we would move median distance dist = L * `sqrt(N) = `sqrt(2) * `sqrt(N) = 1.4 `sqrt(N).

An alternative interpretation of our data is that we made two moves for each step, so that the actual number of 1-unit moves in N steps would be 2 N.

Making 2N moves each of length 1 would result in median distance dist = L * `sqrt(number of moves) = 1 * `sqrt( 2 N ) = `sqrt(2) * `sqrt(N) = 1.4 `sqrt(N).

Either interpretation is consistent with our model dist = 1.4 `sqrt ( number of steps).

The data below gives the distances moved in each of four trials, for each of N = 200, 400, 600, ..., 1600 steps, each step consisting of two moves.

The Chaos Game starts with three points A, B and C, and a random starting point.

For the first 'move' we randomly choose one of the points A, B or C and move halfway to this point. In the example below, the first point was P0 and the point B was chosen, so the next point P1 is halfway from P0 to B.

For each subsequent move we randomly choose A, B or C and move halfway to that point.

For the second move in the figure below the point C was chosen, so we moved halfway from P1 to C, ending up at P2.
For the third move the point A was chosen, so P3 was halfway from P2 to A.

The choice of A, B and C is completely random at every step. It often happens that the same point is chosen for two or more consecutive moves.

It might seem that this process will just end up filling in the triangle defined by A, B and C. However, the result is a very clear and distinct pattern.

The pattern in fact repeats again and again at smaller and smaller scales.
This pattern is a fractal, called the Sierpinski Triangle.