Math Professor and Students Take 'Random Walk' Together

Some people like to take random walks through the woods, while others might stroll through their own neighborhood. In the world of math, a random walk is in fact more random than this; it would be the equivalent of flipping a coin to decide which direction you would take with each step.

Recently, Caltech's Omer Tamuz, professor of economics and mathematics, along with two of his graduate students, Joshua Frisch and Pooya Vahidi Ferdowsi, and their colleague Yair Hartman from Ben-Gurion University in Israel, solved a long-standing math problem related to random walks. The solution was published last summer in the journal Annals of Mathematics.

"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," says Tamuz.

"We were very lucky in that this project actually got us the solution we wanted. That's very rare in a math project," says Frisch. "Something like 90 percent of the projects you work on, you are not going to be able to solve. With about 10 percent, you start making progress and work much harder. And even then, you don't always solve those. Part of being a mathematician is getting used to failure. Sometimes you work on something for months and have to give up and go on to the next project."

Mathematicians imagine random walks in spaces with different dimensions and geometries. In the new study, the Caltech team imagined random walks on "groups," which are objects that can have very diverse geometries. For some groups, the random walks will eventually, after much time has elapsed, converge to a specific direction. In those cases, the walks are said to be path dependent, which means that something that happened in the beginning affects the outcome. Or, in other words, something that happens early on the walk influences where it winds up. But for other groups, the direction of the walks does not converge, and their history does not affect their future.

"For a random process, is it true that in the long run, everything washes out and whatever happens will happen regardless of what took place earlier? Or is there a memory of what took place before?" asks Tamuz. "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."

The solution, says Tamuz, had to do with finding a "geometric way of describing an algebraic property of the groups." To understand the gist of this, think of a circle. You can describe the circle geometrically (as the set of all points at a given distance from one point), or you can describe it with an algebraic equation. In the case of the random-walk problem, the mathematicians found a new way of thinking about the connections between the geometric and algebraic properties of the groups they were studying.

"We were actually shocked by how easy it was to solve the problem once we figured out this connection," says Ferdowsi, who explains that though the solution "just flowed out," the team faced a "considerable" delay while he was in his home country of Iran and unable to obtain a visa to come back to Caltech. "In the end, we were delighted to have solved a longstanding open problem in math."

Frisch says that the big realization they had for this math problem actually grew from a previous problem that was much harder. "I had been bashing my head for a few months on it and couldn't make any progress," he says, "But then we had this eureka idea that applied not only to what we were working on then but also to this more recent problem. It feels really good when you realize, 'Oh my god, this is actually going to work.'"

The Annals of Mathematics study, titled, "Choquet-Deny groups and the infinite conjugacy class property," was supported by the National Science Foundation and the Simons Foundation.