Flips reveal the universal impact of memory on random explorations.

Abstract

Quantifying space exploration is a central question in random walk theory, with direct applications to animal foraging, diffusion-limited reactions, cell motility, and stock markets. The explored domain of memoryless (Markovian) walkers is well understood, but real systems generally exhibit strong memory effects, complicating analysis. We introduce the flip: in one dimension, where the visited territory is <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mo>[</mo> <mrow> <msub><mrow><mi>x</mi></mrow> <mrow><mi>min</mi></mrow> </msub> <mo>,</mo> <msub><mrow><mi>x</mi></mrow> <mrow><mi>max</mi></mrow> </msub> </mrow> <mo>]</mo></mrow> </math> , a flip occurs when, after visiting <math xmlns="http://www.w3.org/1998/Math/MathML"> <msub><mrow><mi>x</mi></mrow> <mrow><mi>max</mi></mrow> </msub> </math> , the walker next discovers <math xmlns="http://www.w3.org/1998/Math/MathML"> <msub><mrow><mi>x</mi></mrow> <mrow><mi>min</mi></mrow> </msub> <mo>-</mo> <mn>1</mn></math> rather than <math xmlns="http://www.w3.org/1998/Math/MathML"> <msub><mrow><mi>x</mi></mrow> <mrow><mi>max</mi></mrow> </msub> <mo>+</mo> <mn>1</mn></math> (and vice-versa). Although it coincides with the classical splitting probability for Markovian systems, we show that the flip probability reveals the universal impact of memory, or history dependence, on exploration: obeying the universal law π_n ∝ 1/n regardless of the dynamics, Markovian or not. We confirm this behavior in simulations of non-Markovian models and in experimental databanks. We then identify the mechanism behind its universality and extend it to higher-dimensional and fractal domains.