Scientists uncover universal features of 'first passage under restart'

(Phys.org)—Discovering the ways in which many seemingly diverse phenomena are related is one of the overarching goals of scientific inquiry, since universality often allows an insight in one area to be extended to many other areas.

Working along these lines, researchers in a new study have developed a general framework for the "first passage under restart" model, which describes a wide range of statistical phenomena in physics, chemistry, biology, finance, and other fields. By identifying an optimal strategy and showing that it cannot be outperformed by any other strategy, the researchers have taken steps toward improving the performance of many diverse processes with a wide range of applications, such as efficient computer coding, biochemical reactions in cells, and wildlife foraging.

The researchers, Arnab Pal at Technion-Israel Institute of Technology and Shlomi Reuveni at Harvard Medical School, have published a paper on their development of a general theoretical framework for first passage under restart in a recent issue of Physical Review Letters.

"We have developed a theoretical framework for first passage under restart," Pal told Phys.org. "The framework is extremely general and offers applications to a wide and diverse class of problems in computer science, computational physics, biophysics, non-equilibrium statistical physics, and more."

First passage under restart is a variation of the "first passage time" framework, which was originally developed in the context of non-equilibrium systems and used, for instance, to study the time it takes for a particle with random motion to reach a certain location. More generally, the first passage time is the time taken for any random variable to reach a certain threshold value. It is especially useful for accounting for the inherently probabilistic nature of statistical processes, such as neuron firing, fluorescence quenching, or stock market activity.

More recently, researchers have investigated what happens when a process is stopped and started again from its initial starting point. Studies have shown that restart can have advantages for certain problems that "get off to a bad start"—for example, a search algorithm that randomly scans for a solution to a problem, but starts off searching along a path that goes in the wrong direction. Restart could then help rescue a futile search by starting it anew. More generally, restart could help in a situation when it is unclear if the process will end quickly or only after a long period of time.

While first passage under restart has been used to describe a wide variety of processes, part of the problem with this variety is that currently there is no general, unifying approach that could be applied regardless of the particular details of the process or restart mechanism.

By developing a general framework for first passage processes under restart, Pal and Reuveni have addressed this problem. Using this framework, they then identified an optimal strategy, called sharp restart, that outperforms all possible restart strategies in terms of attaining the shortest average first passage time.

As the researchers explain, sharp restart is very simple in essence: simply stop the process and start it anew after some fixed amount of time, with the exact amount of time depending on the problem. The results have a wide variety of potential applications.

"In foraging theory, one studies the movement of animals searching for food, mates and shelter in the wild, and it's quite fascinating to see how animals try to optimize their foraging activities," Pal said. "First passage under restart can then be used as an idealized description for some of these activities. One possible, yet unexplored, direction in which this could be taken is the study of prehistoric migration patterns of human groups searching for new and more accommodating territories.

"Another application is in the development of more efficient search strategies that may aid in finding lost objects, or help construct rescue operations for crashed airplanes or lost submarines. Search processes also naturally appear in the context of biochemical reactions when one molecule searches for a reactive target site, and first passage under restart could also be used to describe enzymatic reactions."

Currently, one drawback of the sharp restart strategy is that it may be hard to implement using molecules due to the high energetic cost. In the future, the researchers plan to further analyze this problem to come up with nearly optimal restart strategies that perform almost as well but consume less energy. These strategies could become especially important in living cells or in man-made molecular devices.

"Restart is routinely used to expedite the completion of randomized computer algorithms, but its importance in physical, chemical, and biological processes is just starting to be realized," Pal said. "We intend to explore restart in these contexts and are particularly interested to find out if biological systems have found a way to also take advantage of restart and the benefits it can offer."

© 2017 Phys.org