Popular Mechanics - USA (2020-09 & 2020-10)

Deep Math

5

walker will eventually revert to the mean and end up
near its place of origin (because it’s less likely that
chance would urge the walker in a single, focused
direction over and over). Some random walks seem
to behave with this assumption in mind, “realizing”
they’ve taken a detour before reverting back to what
is expected—mathematicians say this behavior is
“path-dependent.” Other walks, however, seem to
ignore their histories. They just go rogue, persist-
ing as outliers and converging with other random
walks that had much different histories.
The team from Caltech—plus a colleague from
Ben-Gurion University in Israel—investigated
and explained these two differing behaviors in a
“remarkable” rush one evening, according to lead
author Omer Tamuz. The key was blending prob-
ability theory and ergodic theory (the study of
statistical properties in dynamical systems) in an
approach that combined spatial analysis with like-
lihood. In other words, the team had to figure out
how a walk’s history affected the chance it would
take any given next step in the walk.
When you program something like a video game
using random-walk theory, you can code in a limita-
tion to make sure the outlier paths don’t encounter
the more history-considerate, mean-adhering
paths (otherwise, there would be no meaningful
in-game consequences for wildly unusual “walks”
taken by the game). But true random walks don’t
have those limitations, so Tamuz asks: “What hap-
pens at the beginning of the random process [that]
has an effect that lasts forever?”
The Caltech team discovered you can combine
ideas from algebra and geometry to investigate
the differences in walk behaviors. They found that
those renegade random walks that intersect with
the path-dependent walks fall within a certain cri-
terion, based in vector geometry.
But different dimensions and scenarios lend dif-
ferent properties to the random walks. On a f lat,
one-dimensional number line counting from zero
in either direction, random walks are much more
likely to revert to the mean. It makes sense: A five-
step walk that can only go left or right at random
is more likely to stay close to home than to go five
straight steps to the right.
When the walk takes place in a two-dimensional
coordinate grid, with four directions to choose
from, it still reverts to the mean. “I’ll revert to the
point where I started again and again,” Tamuz

explains. “I’m guaranteed to return to the point

where I started.”

But in three dimensions, everything changes.

“There, you don’t keep on coming back to where

you started,” Tamuz said. “In some sense, there’s

no reversion to the mean.” There are other geome-

tries where random walks have even more complex

properties, like a graph called a tree that’s used

extensively in programming.

Ultimately, the researchers found that no matter

how wayward a random walk is in the early steps, it

will almost always correct itself over time and come

back to the mean. On some walks, it just takes a lit-

tle more patience. “Imagine I do a random walk that

started from some very faraway point,” Tamuz said.

“Can you tell that I started this random walk ver y far

away? At ‘time 1’ you can tell. But can you tell after

‘time 1 billion’? It all eventually looks the same.”

So the next time you play Stardew Valley, con-

sider all of the paths you could have taken to return

to your farm from the town center, or perhaps the

fishing pier. The journey might look different each

time, but in the end, you always make it home.

Imagine you are sitting in a

circle of n + 1 friends, and

positions are labeled 0, 1, ...

n, and so on. The B in Fig. 1

represents a pizza box held

by person 0, who can pass

the pizza to the person on

their left or right with equal

probability. That person

randomly passes the pizza

to their left or right, and so

on. After a given number of

passes, everyone in an arc

of the circle has touched the

pizza, and everyone outside

the arc has not. The arc

grows until all but one person

has touched the pizza—and

they are the winner. Where in

the circle should you position

yourself to maximize the

probability that you win?

—Courtney Linder You should sit as far ER: ANSW

away from person 0 as possible.

That spot can be represented

as n/2 or (n+1)/2, depending on

whether n is even or odd.

Source: Mathematics for Computer Science/MIT OpenCourseWare

Take a Random Walk

0 1 2 3..

.

.

B

.

.

.

n — 1

n

Figure 1

24 September/October 2020