Taking a random walk using maths is harder than you think

MATHEMATICIANS from the California Institute of Technology have solved an age-old problem related to ‘random walks’, a mathematical process that traces a path based on random decisions at various junctions. If you’ve played a procedurally generated video game such as Minecraft or Stardew Valley, you’ve encountered a random walk in the form of a dungeon or terrain. Biologists use random walks to model how animals move and behave, and physicists use them to describe how particles behave.

In a random walk, the ‘walker’ can move in any direction at any point, so there’s an assumption that the 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, ‘realising’ they’ve taken a detour before reverting back to what is expected – mathematicians say this behaviour is ‘path-dependent’. Other walks, however, seem to ignore their histories. They just go rogue, persisting as outliers and converging with other random walks that had much different histories.

The team from Caltech – plus a colleague from BenGurion University in Israel – investigated and explained these two differing behaviours in a ‘remarkable’ rush one evening, according to lead author Omer Tamuz. The key was blending probability theory and ergodic theory (the study of statistical properties in dynamical systems) in an approach that combined spatial analysis with likelihood. 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 such as a video game using random-walk theory, you can code in a limitation 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 happens 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 behaviours. They found that those renegade random walks that intersect with the path-dependent walks fall within a certain criterion, based in vector geometry.

But different dimensions and scenarios lend different properties to the random walks. On a flat, 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 says. ‘In some sense, there’s no reversion to the mean.’ There are other geometries 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 little more patience. ‘Imagine I do a random walk that started from some very faraway point,’ Tamuz says. ‘Can you tell that I started this random walk very 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, consider all of the paths you could have taken to return to your farm from the town centre, or perhaps the fishing pier. The journey might look different each time, but in the end, you always make it home.