How Far Does a Wandering Ant Get?

One ant

Walk ten ants to 100 steps with the widget above.

• a.What was the closest an ant ended to home? The farthest?
• b.Did any ant ever go straight out, 100 squares away?
• c.Watch Farthest while an ant walks. Is it often much more than where the ant ends?

A hundred ants

One ant is a matter of luck. A hundred ants show the pattern. Here they all leave the nest together, each walking on its own.

• a.After 25 steps, about how far are the ants from home on average? After 100? After 400?
• b.100 steps is four times 25, and 400 is four times 100. What happens to the average distance each time?

Distance, in a straight line

The ant ends some number of squares across from the nest and some number up or down. Its distance from the nest is the straight line between them. By Pythagoras’ theorem, if the ant is 9 squares across and 1 up, the distance is the square root of 9 × 9 + 1 × 1 = 82, which is about 9.1. (A square root is the number that, times itself, gives the number you started with: 9.1 × 9.1 is about 82.) (Proofs: How many ways can you prove Pythagoras’ theorem?)

It is often easier to work with distance squared, the distance times itself: across × across + up × up, here 82.

Why the steps cancel

A walk where each step is chosen by chance is called a random walk. Think first of an ant on a narrow path, where each step goes forward or back. Say it is 5 squares out. Its next step takes it to 6 or to 4, each half the time. Distance squared goes from 25 to 36 or to 16, and the average of those is (36 + 16) ÷ 2 = 26: one more than 25.

That works wherever the ant is. From 7 squares out, (8 × 8 + 6 × 6) ÷ 2 = 50, one more than 7 × 7 = 49. Out on squared paper it is the same: each step changes only the across or only the up-and-down, by one square, so on average each step adds exactly 1 to the distance squared. Some steps add more and some take away, but on average, one.

So after 100 steps, distance squared is 100 on average, and a typical distance is the square root of 100, which is 10. After 400 steps, distance squared is 400 on average, and a typical distance is 20. That is the rule hiding in the widget: a typical distance is the square root of the number of steps. Four times the steps gives twice the distance, and a hundred times the steps only ten times the distance.

(The plain average of the distances comes out a little under the square root, about 9 for 100 steps, because a few far-out ants push distance squared up more than distance. It still doubles for four times the steps.)

With blocks: the ant’s walk

The turtle can wander too. Each time round the loop, this program picks a number from 1 to 4 for the way to go. The turtle starts facing right. To step, it turns right by way × 90 degrees (90, 180, 270 or 360), moves, and turns back, so it faces right again before the next step: way 1 is a step down, 2 left, 3 up and 4 right. The four if blocks count where the ant is: x across and y up.

In Python (from Grade 8)

Step 1: one ant

The ant’s way is a number from 0 to 3, picked by random.randint(0, 3). The two lists say how each way changes the column and the row (rows count downward, so up is −1, as in What does an ant do with two simple rules?). math.sqrt gives a square root, and abs a number without its minus sign.

import mathimport random STEP_X = [0, 1, 0, -1]     # up, right, down, leftSTEP_Y = [-1, 0, 1, 0]     # rows count downward, so up is -1 random.seed(3)x = 0                      # the nest is at column 0, row 0y = 0for step in range(100):    way = random.randint(0, 3)    x = x + STEP_X[way]    y = y + STEP_Y[way] distance = math.sqrt(x * x + y * y)print('After 100 steps the ant is at column', x, 'row', y)print('Steps home along the squares:', abs(x) + abs(y))print('Straight-line distance:', round(distance, 1), 'squares')

After 100 steps the ant is at column -9 row 1Steps home along the squares: 10Straight-line distance: 9.1 squares

random.seed(3) makes Python pick the same “random” numbers every time it runs, so your run matches this one. Take the line out (or change the 3) for a new walk each time.

Step 2: a thousand ants

One walk is luck. Put the walk in a function, walk(steps), that gives back where the ant ends, and send out a thousand ants.

import mathimport random STEP_X = [0, 1, 0, -1]STEP_Y = [-1, 0, 1, 0] def walk(steps):    # one ant walks from the nest; gives back where it ends    x = 0    y = 0    for step in range(steps):        way = random.randint(0, 3)        x = x + STEP_X[way]        y = y + STEP_Y[way]    return [x, y] random.seed(1)total = 0total_squared = 0near = 0farthest = 0for ant in range(1000):    end = walk(100)    squared = end[0] * end[0] + end[1] * end[1]    distance = math.sqrt(squared)    total = total + distance    total_squared = total_squared + squared    if distance <= 10:        near = near + 1    if distance > farthest:        farthest = distance print('Average distance:', round(total / 1000, 1), 'squares')print('Ants 10 squares or less from the nest:', near, 'of 1000')print('The farthest ant:', round(farthest, 1), 'squares')print('Average distance squared:', round(total_squared / 1000))

Average distance: 8.8 squaresAnts 10 squares or less from the nest: 641 of 1000The farthest ant: 25.6 squaresAverage distance squared: 99

Step 3: four times the steps

Now the same thousand ants, for walks of 25, 100 and 400 steps.

import mathimport random STEP_X = [0, 1, 0, -1]STEP_Y = [-1, 0, 1, 0] def walk(steps):    # one ant walks from the nest; gives back where it ends    x = 0    y = 0    for step in range(steps):        way = random.randint(0, 3)        x = x + STEP_X[way]        y = y + STEP_Y[way]    return [x, y] random.seed(1)for steps in [25, 100, 400]:    total = 0    total_squared = 0    for ant in range(1000):        end = walk(steps)        squared = end[0] * end[0] + end[1] * end[1]        total = total + math.sqrt(squared)        total_squared = total_squared + squared    print(steps, 'steps: average distance', round(total / 1000, 1),          '  average distance squared', round(total_squared / 1000))

25 steps: average distance 4.6   average distance squared 27100 steps: average distance 8.8   average distance squared 97400 steps: average distance 17.7   average distance squared 395

Step 4: a drop of ink

Even in perfectly still water, a drop of ink spreads out slowly: each tiny bit of it is knocked about at random by the water molecules around it, a random walk. (Most of the swirling you see in a glass is the water itself moving.) This program follows 500 bits of ink from one spot and takes a picture every 25 steps. show_frames is part of the page’s own pixels module: it shows the pictures as a film. (On your own computer you would draw them with a library such as Pillow.)

import randomfrom pixels import show_frames STEP_X = [0, 1, 0, -1]STEP_Y = [-1, 0, 1, 0]SIZE = 81                  # the picture: 81 squares across,MID = 40                   # with the drop in the middle square random.seed(4)drops = []for i in range(500):    drops.append([0, 0])   # 500 bits of ink, all at the middle frames = []for step in range(1, 401):    for d in drops:        way = random.randint(0, 3)        d[0] = d[0] + STEP_X[way]        d[1] = d[1] + STEP_Y[way]    if step % 25 == 0:     # every 25 steps, a picture        picture = []        for row in range(SIZE):            picture.append([0] * SIZE)        for d in drops:            col = d[0] + MID            row = d[1] + MID            if 0 <= col < SIZE and 0 <= row < SIZE:                picture[row][col] = 1        frames.append(picture) outside = 0for d in drops:    if abs(d[0]) > MID or abs(d[1]) > MID:        outside = outside + 1print(len(frames), 'pictures, one every 25 steps')print('After 400 steps,', outside, 'of 500 bits of ink are off the picture')show_frames(frames, ['white', 'navy'])

16 pictures, one every 25 stepsAfter 400 steps, 3 of 500 bits of ink are off the picture

Picture

Press Run, then Play under the picture. The cloud grows quickly at first, then more and more slowly: the 4th picture (100 steps) is about half as wide as the 16th (400 steps).

• A thousand ants of 100 steps ended on average 8.8 squares from home, and 641 of them within 10 squares. The farthest of all was only 25.6 squares away.
• The average distance squared came out at 27, 97 and 395 for walks of 25, 100 and 400 steps: almost exactly the number of steps, as the rule in How it works says.
• So the distance doubled (4.6, 8.8, 17.7) each time the steps were multiplied by four. A typical distance is the square root of the number of steps.

That square root is why spreading by random knocks, called diffusion, is quick over tiny distances and hopelessly slow over big ones: ten times as far takes a hundred times as long. It is why you stir sugar into tea, and why your body needs blood: oxygen alone would take months to diffuse to the middle of your body. Try it in Grade 7 Science’s Life Process:

The desert ant goes home. The desert ant Cataglyphis fortis, on the flat salt pans of Tunisia, searches for food along a winding path, then runs home in a straight line. The biologists Martin Müller and Rüdiger Wehner showed in 1988 that it keeps track, as it goes, of where it is compared with its nest. Your Step 1 program does the same: it needs only x and y, not the path. Challenge ★ works out the way home in blocks.

An open question. A self-avoiding walk never steps on a square it has visited before, like a snake that can’t cross itself. How far does it get after 100 steps? Nobody has found a formula for how many such walks there are on squared paper, and mathematicians are still working on exactly how fast they spread.

★ The way home (blocks)

The ant tells you its six steps, one at a time. The program counts x and y. Finish it so that it says how many steps the ant needs to walk home along the squares (and nothing else). Then press Test.

★★ The first time home (Python, from Grade 8)

An ant’s walk is a string of letters, 'U', 'D', 'L' and 'R' (up, down, left, right). Write first_return(moves) that gives back the step at which the ant first stands on its nest again, or 0 if it never does.

def first_return(moves):    # moves is a string such as 'URDL'    return 0 print(first_return('URDL'))

★★★ Every walk at once (Python, from Grade 8)

A walk of 2 steps can go 4 × 4 = 16 ways, each as likely. Write average_square(n) that tries every possible walk of n steps and gives back the average of distance squared over all of them, exactly, with no random numbers at all.

def average_square(n):    # every walk of n steps; the average of x*x + y*y    return 0 print(average_square(2))

• Grade 7, Variables and Choices: the random number block, and the turtle with variables.
• Grade 8, Decisions and Loops in Python: for loops that repeat a step many times.
• Grade 8, Functions: functions like walk that give back an answer.
• What does an ant do with two simple rules? An ant with no chance in it at all, whose two rules still make something nobody can predict.
• Why do snakes and ladders games take so long? Another game of chance, played thousands of times by a program.