Mar 30, 2020
3 mins, 22 secs
Researchers used algebra and geometry together to solve an old random walk problem.Random walk ideas have informed everything from biology to video games.This team identified a key geometry idea that unites some random walks and sets others apart.Mathematicians from the California Institute of Technology have solved an old problem related to a mathematical process called a random walk.
The team, which also worked with a colleague from Israel’s Ben-Gurion University, solved the problem in a rush after having a realization one evening. Lead author Omer Tamuz studies both economics and mathematics, using probability theory and ergodic theory as the link—a progressive and blended approach that this year’s Abel Prize-winning mathematicians helped to trailblaze.
Five eight-step random walks from a central point. Some paths appear shorter than eight steps where the route has doubled back on itself.
Tamuz said in a Caltech statement that he’d explained a potential breakthrough to his students one day, then found out the next day they’d gone ahead and solved it.
"I remember talking to the students about a realization we had regarding this problem, and then the next morning I found out they had stayed up late into the night and figured it out," Tamuz said. The breakthrough, and the problem it helped the team of researchers to unravel, is again based on seeing a connection between disparate modes of thinking.
The random walk is a colloquial term for a way to create a path based on random decisions at junctions. If you’ve played a procedurally generated video game, including major examples like Minecraft and Stardew Valley as well as cult favorites like Spelunky and Dwarf Fortress, you’ve encountered a random walk in the form of a dungeon or terrain made this way in the programming.
25 Great Games Like Minecraft
The idea and principles of random walk theory are used across many disciplines. Biologists can use random walks to model how animals move and behave. Physicists use it to describe and model how particles behave. And learning how to implement versions of it has been an ongoing project for computer scientists. Some random walks appear to behave according to where they’ve already been, which is called being path dependent. Others seem to ignore their “pasts” and end up converging with other paths with different histories.
It’s this difference where Tamuz and his colleagues Joshua Frisch, Yair Hartman, and Pooya Vahidi Ferdowsi explored and found a solution. As Tamuz said in the statement:
"Say you have two societies, and one of them makes some technological advancement while the other suffers a natural disaster. Are these differences going to persist forever, or will they eventually disappear and we'll forget that once there was an advantage? In random walks, it has been long known that there are groups that have these memories while in other groups the memories are erased. But it was not really clear which groups have this property and which don't—that is, what makes a group have memory? This is what we figured out."In other words, why do some random walks revert to the mean and others do not? When you program using random walks ideas, you can simply code in a limitation or parameter to make sure paths do or don’t converge. In the pure theory, the problem is much harder to explain.
Can You Solve This Viral Triangle Brain Teaser?
The Simple Math Problem That Fooled Einstein
How to Solve the Infuriating Viral Math Problem
The secret this team discovered is to combine algebra ideas and geometry ideas together when describing the random walks, and use that connection to investigate. The researchers found that random walks that meet a certain criterion based in vector geometry are the ones that converge with everything else.
“In the end, we were delighted to have solved a longstanding open problem in math," Ferdowsi said in the statement.