Flips reveal the universal impact of memory on random explorations Authors: J. Brémont, L. Régnier, A. Barbier–Chebbah, R. Voituriez, O. Bénichou Published: 2025 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 \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$[{x}_{\min },{x}_{\max }]$$\end{document}[xmin,xmax], a flip occurs when, after visiting \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${x}_{\max }$$\end{document}xmax, the walker next discovers \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${x}_{\min }-1$$\end{document}xmin−1 rather than \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${x}_{\max }+1$$\end{document}xmax+1 (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. Introduction Fluctuations and reversals are fundamental features of complex systems. A stock price climbs to a record high—then crashes. A foraging animal searches one side of its habitat—then turns back in search of more food. A computer network handles a surge of data—then buckles under the load. At the heart of these diverse examples, commonly modeled as random walks (RWs)1–4, lies a simple, general question: as a system randomly explores new territory within its phase space, how often does it reverse the direction of its exploration? We introduce the concept of a flip (see Fig. 1) to capture this essential phenomenon. Defined most naturally in one dimension (see below for a generalization to higher dimensions), flips are transitions from a maximum to a minimum, or vice-versa, thus providing a direct measure of persistence in exploration. For Markovian processes, flip probabilities reduce to classical splitting probabilities—a well-understood quantity5,6. But real-world phenomena are rarely memoryless7–13. From foraging patterns to stock market dynamics and intracellular transport, systems often carry the imprint of their past: their future depends not only on their current state but on their entire history.Fig. 1Illustration of the concept of a flip in two physically relevant settings.Top: Foraging analogy of flips. Here, the walker (green crocodile) consumes its nth unit of food, which is red: previously eaten food is in gray. A flip occurs when the next unit eaten is blue, which happens with probability πn. Bottom: flips in a time series. Flips are identified as transitions between maxima and minima: downward flips (from maxima to minima) are marked in blue, and upward flips (from minima to maxima) are marked in red. The gray region shows the visited territory, i.e., values already reached by Xt. Illustration of the concept of a flip in two physically relevant settings. Top: Foraging analogy of flips. Here, the walker (green crocodile) consumes its nth unit of food, which is red: previously eaten food is in gray. A flip occurs when the next unit eaten is blue, which happens with probability πn. Bottom: flips in a time series. Flips are identified as transitions between maxima and minima: downward flips (from maxima to minima) are marked in blue, and upward flips (from minima to maxima) are marked in red. The gray region shows the visited territory, i.e., values already reached by Xt. This brings us to the central question of this article: how does memory, that is, dependence on past history, shape the process of exploration? We address this fundamental problem by developing an analytical framework that allows us to compute the probability πn of a flip when the system has aged, so that the visited territory has size n. Our central result is a remarkably simple and universal scaling law: in one dimension, for RWs that are symmetric, recurrent, and asymptotically scale-invariant, the probability of a flip scales as πn ∝ 1/n, as given in Eq. (1) (see below for the extension to higher dimensions). This universality is particularly striking because it crucially applies to history-dependent, memory-driven dynamics, where one typically expects complex, model-specific behavior14–16. Indeed, the classical splitting probability, which quantifies the chance of crossing from one boundary of a fixed region to another, is known to depend sensitively on microscopic details of the process17. In stark contrast, flips occur when the walker traverses from one edge of its own dynamically explored region to the other. This moving, history-defined domain introduces memory and aging into the observable itself. Paradoxically, we find that this added complexity imposes simplicity: it erases process-specific dependencies and enforces a universal 1/n scaling. That this law emerges within the walker’s self-generated geometry rather than in a fixed domain may explain why it has not been previously identified. The universality of our scaling law, which governs flips in effectively one-dimensional systems as varied as intracellular transport18,19, nucleotide distribution along DNA strands20, and financial indices, is supported by both numerical simulations (Fig. 2) and experimental observations (Fig. 3), underscoring its broad applicability across diverse natural systems. Finally, we demonstrate that our universal law extends beyond one-dimensional exploration, applying also to RWs in fractal media and higher-dimensional spaces. This further highlights the broad generality and far-reaching relevance of the flip-based framework.Fig. 2Flip probability πn for representative examples of non-Markovian RWs.Simulation results are in blue. Rows correspond to distinct classes: the first for class (I), the second for class (II), and the third for class (III). The black line shows the theoretical decay A/n with A given by (1), while the red line depicts the classical splitting probability, decaying as 1/nϕ. The purple dashed line illustrates the naive estimate \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\pi }_{n} \sim \frac{\phi }{n}=\frac{{d}_{{{{\rm{w}}}}}\theta }{n}$$\end{document}πn~ϕn=dwθn, which holds only for class (I). Outside of class (I), this approximation either overestimates the flip probability (as in class (III) or antipersistent fBM, class (II)) or underestimates it (as in persistent fBM, class (II)). Errors in the prefactor A are below 0.1% for the exact results of classes (I) and (III), and around 3.5% for the perturbative result of class (II), for which we use A = e−Cε instead of A = 1 − Cε, ensuring that A remains non-negative; this approach is standard in perturbative theory65, where both expressions agree to first order in ε.Fig. 3Observing the 1/n law for flips in real data.Flip probability πn for each dataset (blue symbols), estimated using the windowing method explained in the Methods section. The black line shows the universal 1/n scaling, determined by a weighted least-squares fit in which the weights correspond to the error bars estimated from sample noise in the windowing procedure (see “Methods”). Panels (a) and (b) refer to single-cell (dermal fibroblasts) displacements in vitro from young and older patients18; (c) presents intracellular motion of amoeba vacuoles19; and (d) shows fluctuations in Ethernet requests2. Panels (e) and (f) correspond to DNA sequences represented as RWs, where each step is + 1 for guanine (G) and − 1 for cytosine (C). Finally, (g), (h), and (i) are financial indices SPX, N225, and Dow Jones, respectively. Flip probability πn for representative examples of non-Markovian RWs. Simulation results are in blue. Rows correspond to distinct classes: the first for class (I), the second for class (II), and the third for class (III). The black line shows the theoretical decay A/n with A given by (1), while the red line depicts the classical splitting probability, decaying as 1/nϕ. The purple dashed line illustrates the naive estimate \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\pi }_{n} \sim \frac{\phi }{n}=\frac{{d}_{{{{\rm{w}}}}}\theta }{n}$$\end{document}πn~ϕn=dwθn, which holds only for class (I). Outside of class (I), this approximation either overestimates the flip probability (as in class (III) or antipersistent fBM, class (II)) or underestimates it (as in persistent fBM, class (II)). Errors in the prefactor A are below 0.1% for the exact results of classes (I) and (III), and around 3.5% for the perturbative result of class (II), for which we use A = e−Cε instead of A = 1 − Cε, ensuring that A remains non-negative; this approach is standard in perturbative theory65, where both expressions agree to first order in ε. Observing the 1/n law for flips in real data. Flip probability πn for each dataset (blue symbols), estimated using the windowing method explained in the Methods section. The black line shows the universal 1/n scaling, determined by a weighted least-squares fit in which the weights correspond to the error bars estimated from sample noise in the windowing procedure (see “Methods”). Panels (a) and (b) refer to single-cell (dermal fibroblasts) displacements in vitro from young and older patients18; (c) presents intracellular motion of amoeba vacuoles19; and (d) shows fluctuations in Ethernet requests2. Panels (e) and (f) correspond to DNA sequences represented as RWs, where each step is + 1 for guanine (G) and − 1 for cytosine (C). Finally, (g), (h), and (i) are financial indices SPX, N225, and Dow Jones, respectively. Results To derive the general properties of flip probabilities, we consider a one-dimensional, symmetric, recurrent RW \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${({X}_{t})}_{t=0,1,\ldots }$$\end{document}(Xt)t=0,1,… in discrete time, starting from X0 = 0. The increments \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${({\eta }_{t})}_{t}$$\end{document}(ηt)t in Xt+1 = Xt + ηt may be correlated, so the RW need not be Markovian. Note that we do not restrict to nearest-neighbor steps: the distribution of ηt may be continuous or discrete, and may or may not have finite moments. Importantly, we assume that Xt converges at long times to a scale-invariant process with walk dimension dw21, meaning that the process \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${({X}_{tT}/{t}^{1/{d}_{{{{\rm{w}}}}}})}_{0\le T\le 1}$$\end{document}(XtT/t1/dw)0≤T≤1 becomes asymptotically independent of t. In particular, \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\langle {X}_{t}^{2}\rangle \propto {t}^{2/{d}_{{{{\rm{w}}}}}}$$\end{document}⟨Xt2⟩∝t2/dw, where dw = 2 for diffusive RWs, dw < 2 for superdiffusive processes such as Lévy walks and dw > 2 for subdiffusive processes such as RWs on fractals22. To quantify exploration, we view the integer lattice \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathbb{Z}}$$\end{document}Z as a collection of sites, deemed visited once crossed by the RW (See (3) for the alternative arrival prescription, which involves holes in the visited region). This crossing prescription ensures that the sequence of visited sites (xn), which we call the “exploration process”, forms an interval. To fix ideas, we consider foraging23,24, where sites represent units of food eaten by the walker upon crossing (see Fig. 1); to quantify asymmetry in the exploration, we color food on positive (resp. negative) sites red (resp. blue). Notably, we distinguish between the Markov property of the trajectory (Xt), in physical time t, and that of the exploration process (xn), indexed by the number of visited sites n. By definition, exploration is Markovian if xn+1 depends only on xn and n, not on the full trajectory before visiting xn. For example, in one dimension, the exploration process of a simple RW is Markovian. By contrast, Lévy flights25 are Markovian at the trajectory level but not in their exploration process, since predicting xn+1 requires knowing whether the walker is still in the middle of a jump when crossing xn. Conversely, continuous-time RWs with heavy-tailed waiting times26, while non-Markovian in physical time, have a Markovian exploration process, because only the number of visited sites n matters, not the time t. See SI for further discussion. We introduce and answer the following questions. When the walker has eaten n units of food, we can assume, by symmetry, that the last unit consumed is red. What is the probability πn that the RW flips, meaning the next unit consumed is blue (Fig. 1)? We propose πn as a novel metric for quantifying random explorations. As underlined in the introduction, for Markovian explorations, determining πn is straightforward, as it reduces to the classical splitting probability qn: the probability that, starting from site k, the walker reaches site − (n − k) before k + 1, independent of the past trajectory. This observable has been widely studied in the RW literature, and its large-n behavior is known explicitly and holds even for non-Markovian RWs: qn ∝ n−ϕ17. Crucially, this decay is process-dependent: the exponent ϕ ≡ dwθ, where θ is the persistence exponent characterizing the algebraic decay Sx(t) ∝ t−θ of the probability that the RW remains below a threshold x > 0 up to time t14. The Sparre-Andersen theorem27, which applies to the case of i.i.d. increments ηt, implies that θ = 1/2 for symmetric Markovian RWs, hence \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${q}_{n}\propto {n}^{-{d}_{w}/2}$$\end{document}qn∝n−dw/2. By contrast, for non-Markovian RWs, no such universality exists, and θ is in general hard to compute14,28,29. Rather than computing qn or θ, we instead condition on the exploration history by introducing the aged observable πn, defined with respect to the number of visited sites n. Our central result is that, although memory of the past trajectory strongly influences exploration, key features such as flip statistics are remarkably simple and universal. Specifically, the probability πn follows the universal scaling law πn ~ A/n, in sharp contrast with the classical, non-aged splitting probability qn, whose decay depends explicitly on ϕ (we write An ~ Bn if An/Bn → 1 as n → ∞). The prefactor A, however, remains process-specific, acting as a fingerprint of the underlying microscopic dynamics. We first determine, relying on a simple scaling analysis, the scaling with n of the probability πn of a flip occurring after n sites have been visited, that is, the probability that the next visited site xn+1 lies on the opposite side of xn. See the discussion leading to Eq. (3) for a more refined argument which provides the physical mechanism responsible for the universal 1/n behavior. First, given the scale-invariant nature of the problem, we expect a power-law decay πn ∝ n−α, where α > 0. After n sites have been visited, an average of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${F}_{n}\equiv \mathop{\sum }_{i=1}^{n}{\pi }_{i}$$\end{document}Fn≡∑i=1nπi flips have occurred. Since the RW is recurrent, we must have Fn → ∞: otherwise, the RW would eventually stop visiting sites on one side. This implies that the exponent α ≤ 1. Let us assume that α < 1. Then Fn ∝ n1−α flips have occurred after n sites have been visited, and, conversely, at the kth flip, k1/(1−α) sites have been visited. Note that the only relevant length is the size of the visited domain. Hence, due to scale invariance, the number of visited sites between the (k + 1)th and kth flips, of the order of (k + 1)1/(1−α) − k1/(1−α) ∝ kα/(1−α), must be proportional to the length k1/(1−α) of the entire visited interval at the kth flip. This implies \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\frac{\alpha }{1-\alpha }=\frac{1}{1-\alpha }$$\end{document}α1−α=11−α, which contradicts α < 1. This finally yields that α = 1, and thus the general behavior πn ~ A/n holds for all recurrent, symmetric, asymptotically scale-invariant RWs, whether Markovian or not. More precisely, our analysis shows that \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${F}_{n}\propto \ln n$$\end{document}Fn∝lnn, meaning the number of sites visited at the kth flip is exponential with k and thus heavily contribute to the time between two flips. This is consistent with the proportionality between the number of newly and previously visited sites. Remarkably, the universal 1/n decay emerges independently of microscopic details, while the prefactor A is model-dependent. In contrast to the scaling argument yielding the 1/n decay, determining A requires technical, process-specific calculations, outlined in the Supplementary Information (SI). To provide a comprehensive framework, we classify memory in scale-invariant processes into three broad classes30, covering the principal types of memory-driven dynamics that are most prominently studied and recognized as physically relevant in the literature. See the Methods section for the explicit description of these processes. First, we define class (I) as RWs for which the exploration process (xn) renews at flips: once a flip occurs at xn, the process loses all memory of the trajectory that led there. Beyond RWs with Markovian exploration, which trivially fit this definition, such as the one-dimensional simple RW, the continuous-time RW31,32, and the saturating self-interacting RW (SATW)29,33,34, we show in SI that this class also encompasses key examples exhibiting non-Markovian exploration, including Lévy walks and flights25,35, the Random Acceleration Process (RAP)36,37, and short-range correlated dynamics such as the run-and-tumble particle38. For RWs outside class I, the exploration process shows more complex history-dependent behavior, directly inherited from the memory effects of the underlying RW (Xt). Such memory effects may be imposed directly, via slowly decaying correlation functions, or arise dynamically from the walk itself. The former type is exemplified by Gaussian processes, which are completely determined by the knowledge of the two-point correlation functions. Restricting ourselves to the case of stationary increments, the only such process is fractional Brownian Motion (fBM)39. This defines class (II). For this class, explicit results are given to first order in \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\varepsilon \equiv {d}_{{{{\rm{w}}}}}^{-1}-1/2$$\end{document}ε≡dw−1−1/2, representing the deviation from Markovian behavior. We note that ε serves as a meaningful expansion parameter only for class (II) processes and has no direct interpretation outside this class of RWs. The latter type of memory, dynamically generated by the process, is illustrated here by class (III). It is a subclass of non-Gaussian processes and encompasses all non-saturating, self-repelling RWs, which leave behind footprints and interact with them. This class includes the true self-avoiding walk (TSAW), the seminal self-interacting RW40. While most relevant examples of scale-invariant RWs in physics are covered by this classification, a notable exception concerns non-Markovian RWs with preferential reattachment13,41–43. When scale-invariant, such processes also satisfy the universal scaling πn ∝ 1/n (see SI). For each class, we have determined (see SI) the full asymptotics of πn:1\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\pi }_{n} \sim \frac{A}{n},\ A=\left\{\begin{array}{ll}\phi \hfill \quad &(\,{\mbox{I}})\hfill \\ 1-C\varepsilon+{{{\mathcal{O}}}}({\varepsilon }^{2})\hfill \quad &(\,{\mbox{II}})\hfill \\ 4/{\pi }^{2}\hfill \quad &(\,{\mbox{III}}),\end{array}\right.$$\end{document}πn~An,A=ϕ(I)1−Cε+O(ε2)(II)4/π2(III),where \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$C=4\left(12\log ({{{\mathcal{G}}}})-\gamma -\frac{7}{3}\log (2)\right)\approx 3.16198$$\end{document}C=412log(G)−γ−73log(2)≈3.16198, and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\gamma,{{{\mathcal{G}}}}$$\end{document}γ,G are the Euler and Glaisher constants44. Our central result (1) calls for several comments. (i) The 1/n scaling of πn is both remarkably simple and completely universal, holding for all symmetric, asymptotically self-similar RWs. In particular, the elementary case of the simple RW, with dw = 1/θ = 2, is recovered from (1), as it belongs to class (I) with ϕ = 1 and to class (II) with ε = 0. Note that this is the only example of a symmetric Markov process with Markovian exploration, which is consistent with both qn ∝ 1/n and πn ∝ 1/n. (ii) As outlined in the introduction, the quantity πn is an aged generalization of the classical splitting probability qn, which is defined for an RW starting at the boundary of a fixed interval of size n. In contrast, πn is defined for an RW at the edge of its dynamically evolving visited territory. The process-dependent scaling qn ∝ 1/nϕ contrasts sharply with the universal scaling πn ∝ 1/n. This highlights the substantial and universal impact of the past trajectory on the exploration process. Note that ϕ can be either larger or smaller than 1, so that πn can decay more slowly or more rapidly than the non-aged splitting probability (see Fig. 2 below). (iii) Lévy walks and flights Jt offer a particularly notable example, as our crossing prescription renders their exploration process non-Markovian; See (3) for the arrival convention. Note that with our crossing convention, the exploration process for Lévy walks and Lévy flights is identical, since physical time t is irrelevant in their definition. Now, after visiting—or, in our convention, crossing—its nth site xn, Jt can either stop its jump within the interval [xn, xn + 1], with probability sn, or continue its jump, crossing sites beyond xn + 1. The flip probability is thus given by πn = snqn + (1 − sn) × 0, as Jt cannot flip if it continues its jump. Since sn ∝ nϕ−1 45, substituting into πn = snqn reproduces our general scaling relation πn ∝ 1/n. This inertial-like memory, characteristic of Lévy walks, is fundamentally distinct from the memory present in other non-Markovian RWs, making it all the more remarkable that the 1/n scaling holds universally across memory types. (iv) The process-dependent prefactor A serves as a fingerprint of the underlying dynamics, as it quantifies the intrinsic tendency of the process to reverse its direction of exploration. For example, in class (II) processes, ε > 0 corresponds to persistent fBM, and Eq. (1) yields A < 1, indicating that the RW is less likely to flip than in the simple Markovian case for which A = 1. Conversely, ε < 0 corresponds to antipersistent fBM, for which the tendency to flip increases. While this physical interpretation is straightforward for class (II), it is less so for class (III) processes, where A < 1 even though self-repelling RWs are not obviously more persistent than the simple RW. The prefactor A can be determined straightforwardly under the assumption that flips effectively reset the memory of the exploration process (class (I)), but this naive assumption fails for classes (II) and (III), for which the determination of A requires nontrivial computations, given in SI. In practice, we propose that A offers a valuable and numerically accessible diagnostic tool for distinguishing memory classes, especially when combined with traditional observables such as mean-square displacement or survival probabilities: A captures memory effects that cannot be inferred from these classical metrics alone, except in class (I). For instance, the TSAW (class III), and the fBM with \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${d}_{{{{\rm{w}}}}}=\frac{3}{2}$$\end{document}dw=32 (class II), both share the same walk dimension40 and persistence exponent \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\theta=\frac{1}{3}$$\end{document}θ=13 28,46,47. Yet, according to (1), their values of A differ by a factor ≈ 1.5. This underscores the unique information encoded in A and, more broadly, by flip statistics, as revealed by our approach. Numerical and experimental validation We now validate our theoretical prediction (1) on paradigmatic non-Markovian models, which illustrate classes (I)-(III) defined above and are defined in the Methods section. The flip probability πn is estimated from a large ensemble of simulated trajectories. For each trajectory, the nth visited site xn is defined as the nth running extremum: this ensures that numerically simulated, finite time trajectories visit sufficiently many sites. Crucially, owing to scale invariance, this prescription is strictly equivalent to the integer-crossing definition of visitation introduced earlier. A flip is recorded whenever xn and xn−1 have opposite signs, and averaging over all trajectories yields the numerical estimate of πn. Overall, we find excellent quantitative agreement between our theoretical predictions and numerical simulations (see Fig. 2). The diversity of the models demonstrates the robustness and universality of our theoretical predictions, further highlighting the practical relevance of our findings in various scientific domains. We now demonstrate the experimental relevance of our results by analyzing effectively one-dimensional datasets of very diverse origins. Crucially, the 1/n scaling law holds even when (i) the mechanisms underlying non-Markovian behavior are unknown, and (ii) in the single-trajectory setting, where averaging over many independent realizations is not possible. This situation is typical of most real-world observations, making the emergence of such a universal law particularly striking (see “Methods” for details). We begin with one-dimensional projections of biological tracers at different scales, which serve as natural realizations of the exploration setting. (a) and (b) concern displacements in vitro of single human cells18; (c) displays intracellular motion of amoeba vacuoles19; and (d) depicts fluctuations in the number of requests in an Ethernet network48. We also analyze time series that exhibit long-range memory, such as (e) and (f) DNA sequences (Pyrimidines/Purines HUMBMYH7 and HUMTCRADCV), represented as RWs where each step is + 1 for guanine (G) and − 1 for cytosine (C)20. This mapping reveals key features of genomic organization, such as GC skew, which highlights replication origins and termini49–51. Flips in the RW trajectory mark transitions between G-rich and C-rich regions, offering a model-free indicator of genomic asymmetry. Finally, (g), (h) and (i) show financial indices SPX, N225 and Dow Jones, where flips correspond to market drawdown events— declines in the market from a recent peak to a subsequent trough52— and corrections. Figure 3 demonstrates the quantitative agreement between diverse real-world datasets and the predicted 1/n scaling law. As an illustration, consider financial markets. Within our framework, a drawdown event can be identified with a flip, so Eq. (1) implies that the probability of such events decreases inversely with the market’s exploration history (i.e., the number of distinct levels visited). Note that after the logarithmic transform described in the Methods section, n indeed counts distinct log-indices rather than the size of the visited interval; equivalently, it is the number of running extrema in the time series—either new maxima or new minima. Finally, flips provide a simple, model-agnostic probe of random exploration in real systems. The 1/n law captures a robust statistical regularity of reversal events that depends only on the exploration history n and can be extracted directly from a single raw time series by counting running extrema, without knowledge of the system’s internal dynamics. As a complement to traditional metrics (e.g., mean-square displacement, survival probabilities), flips offer an inherently path-dependent, geometry-based perspective. In line with our focus on universality, we do not interpret the numerically fitted prefactor in Fig. 3. The prefactor A is an ensemble-level quantity that emerges from averages over many trajectories; in single-trajectory data, any estimate of A is inevitably dependent on the measurement protocol (see “Methods”). We note that a systematic study of A based on true ensemble averages of experimental trajectories would be highly valuable for distinguishing underlying dynamical mechanisms; this lies beyond the single-trajectory focus of the experimental analyses presented in this work. By contrast, the universal πn ∝ 1/n scaling remains the robust, protocol-independent feature we test (see SI for a detailed robustness analysis). Flips in higher dimensions Importantly, we underline that our findings are not limited to the one-dimensional setting, and extend to all symmetric, asymptotically scale-invariant and compact (i.e., recurrent) RWs, implying that holes in the explored region occupy a vanishing fraction of the domain in the long-time limit. They include the physically important cases of RWs on deterministic or random fractals53, such as critical percolation clusters, which is a minimal model of transport in a crowded environment54. In this extended setting, a flip occurs when the walker, after visiting its nth site xn, returns to the origin before discovering xn+1 (see Fig. 4). This mimics a foraging scenario, where the origin acts as a nest and flips mark returns home between outward excursions. While differing in form from the original 1d definition, this notion preserves its essence: flips are excursions into previously explored territory before further expansion. In fact, our derivation below shows in particular that for d = 1, both definitions lead to the same 1/n scaling law, albeit with different prefactors (see SI for a numerical comparison). Moreover, the choice of the origin as reference is arbitrary: any site within the bulk of the visited domain can serve as a reference and yields the same 1/n scaling. Notably, for d > 1, all RWs, whether Markovian or not at the trajectory level, have a non-Markovian exploration process. Indeed, for a fixed number of visited sites fixed to n, the geometry of the explored region remains random (see Fig. 4), and thus this hidden variable influences future exploration. Remarkably, we find that our scaling result (1) still holds in this extended setting. For compact Markovian RWs, the distribution of discovery times τn—the time between the visits of xn and xn+1—has recently been established to follow the asymptotic form452\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$P({\tau }_{n}=\tau ) \sim \frac{1}{{n}^{1+1/\mu }}\,\psi \left(\frac{\tau }{{n}^{1/\mu }}\right),$$\end{document}P(τn=τ)~1n1+1/μψτn1/μ,where μ ≡ df/dw < 1, ψ is a model-dependent scaling function, and df is the fractal dimension of the medium. Numerical evidence shows that this scaling form also holds for non-Markovian compact RWs45, thereby supporting the robustness of the mechanism. The visited region Vn is essentially hole-free for compact RWs and spans a linear size \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$R\propto {n}^{1/{d}_{{{{\rm{f}}}}}}$$\end{document}R∝n1/df. A flip occurs when visiting xn+1 if the walker, starting at xn close to the boundary ∂Vn, returns to the origin before crossing ∂Vn. This requires that the discovery time τn be larger than the typical time to reach the origin from xn, i.e., \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\tau }_{n}\gtrsim {R}^{{d}_{w}}={n}^{1/\mu }$$\end{document}τn≳Rdw=n1/μ. After this time, the walker returns to the origin before crossing the boundary with probability \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${p}_{n}^{0} \sim 1$$\end{document}pn0~1 for compact RWs. Therefore, the flip probability scales as:3\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\pi }_{n}^{{{{\rm{compact}}}}}\propto \left(\int_{{n}^{1/\mu }}^{\infty }P({\tau }_{n}=\tau )\,d\tau \right)\times {p}_{n}^{0}\propto \frac{1}{n},$$\end{document}πncompact∝∫n1/μ∞P(τn=τ)dτ×pn0∝1n,with the last ∝ sign being a consequence of (2). In turn, this provides the physical mechanism responsible for the universal 1/n behavior.Fig. 4Definition of flips in a higher-dimensional medium.This example shows an RW on a critical percolation cluster. Gray balls indicate sites that have already been visited, while red balls mark unexplored sites. The large blue ball represents the origin of the walk, which acts as an infinite reservoir of blue balls. The walker (green crocodile) has just consumed a red ball. Similarly to the one-dimensional case, a flip occurs if the walker consumes a blue ball before eating another red one. Definition of flips in a higher-dimensional medium. This example shows an RW on a critical percolation cluster. Gray balls indicate sites that have already been visited, while red balls mark unexplored sites. The large blue ball represents the origin of the walk, which acts as an infinite reservoir of blue balls. The walker (green crocodile) has just consumed a red ball. Similarly to the one-dimensional case, a flip occurs if the walker consumes a blue ball before eating another red one. In marginally recurrent RWs, exemplified by the 2d simple RW, the 1/n scaling holds up to logarithmic corrections. In the SI, we derive the lower bound:4\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\pi }_{n}^{{{{\rm{marginal}}}}}\gtrsim \frac{1}{n\log n}.$$\end{document}πnmarginal≳1nlogn.Finally, in non-compact (transient) cases, such as the 3d simple RW, the vast majority of sites are never visited, since the probability of ever returning to a previously visited site is strictly less than one. With so much unexplored space available, one might expect excursions within the already visited domain before reaching a new site to be exponentially rare. Yet, the flip probability still exhibits algebraic decay:5\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\pi }_{n}^{{{{\rm{transient}}}}}\gtrsim \frac{1}{{n}^{\mu }},\quad \mu=\frac{{d}_{{{{\rm{f}}}}}}{{d}_{{{{\rm{w}}}}}} > 1.$$\end{document}πntransient≳1nμ,μ=dfdw>1.The universal scaling law (3) and the accuracy of the lower bounds (4), (5) are confirmed numerically Fig. 5.Fig. 5Scaling of the flip probability πn beyond hole-free 1d exploration.We analyze the flip probability for RWs in dimension df > 1, and for 1d Lévy walks with the arrival prescription, where long jumps leave holes in the visited domain. Simulation results are in blue. The first row shows compact RWs, including non-Markovian RWs on deterministic fractals (here, self-attracted SATW with ϕ = 2 (see SI) on the Sierpiński gasket), Markovian RWs on random fractals (e.g., simple RW on a critical percolation cluster), and one-dimensional compact Lévy Walks with arrival convention (β > 1). For all these, the flip probability follows the universal scaling πn ∝ 1/n (3). The second row illustrates marginally recurrent walks–the 2D simple RW and the critical 1d Lévy Walk with β = 1–which exhibit slower decay, \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\pi }_{n}\gtrsim 1/(n\log n)$$\end{document}πn≳1/(nlogn) (4). The third row corresponds to transient walks, including 3D and 4D simple RWs and transient 1d Lévy Walks (β < 1), for which the flip probability decays as πn ≳ 1/nμ (5). Scaling of the flip probability πn beyond hole-free 1d exploration. We analyze the flip probability for RWs in dimension df > 1, and for 1d Lévy walks with the arrival prescription, where long jumps leave holes in the visited domain. Simulation results are in blue. The first row shows compact RWs, including non-Markovian RWs on deterministic fractals (here, self-attracted SATW with ϕ = 2 (see SI) on the Sierpiński gasket), Markovian RWs on random fractals (e.g., simple RW on a critical percolation cluster), and one-dimensional compact Lévy Walks with arrival convention (β > 1). For all these, the flip probability follows the universal scaling πn ∝ 1/n (3). The second row illustrates marginally recurrent walks–the 2D simple RW and the critical 1d Lévy Walk with β = 1–which exhibit slower decay, \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\pi }_{n}\gtrsim 1/(n\log n)$$\end{document}πn≳1/(nlogn) (4). The third row corresponds to transient walks, including 3D and 4D simple RWs and transient 1d Lévy Walks (β < 1), for which the flip probability decays as πn ≳ 1/nμ (5). Discussion In conclusion, we have uncovered a universal scaling law for the probability πn of a flip: πn ∝ 1/n. This simple yet unexpected result holds across a wide range of stochastic processes and real-world systems, from intracellular transport to genomic sequences and financial markets. It highlights the universal impact of past history on random explorations, whether Markovian or not. Our findings overturn the common view that memory or non-Markovianity inevitably leads to complexity and model-specific behavior. Instead, flips expose a simple, universal structure that governs exploration. Two key insights follow. First, flips constitute a fundamental statistical feature that transcends microscopic details of the underlying dynamics. Second, conditioning on the number n of distinct sites visited—rather than on physical time t—induces universal behavior. While traditional observables in non-Markovian dynamics depend intricately on the full trajectory, reframing the problem in terms of exploration history simplifies the picture dramatically. The number of visited sites emerges as a natural “clock” for exploration, one that absorbs memory effects and exposes a deeper geometric invariance. Beyond providing a new observable with universal statistics, our results open a broader perspective by identifying flips as the fundamental units of random exploration. Methods Definitions of paradigmatic non-Markovian processes (I-i) Lévy walks55,56 are jump processes with step lengths l drawn from a power-law distribution p(l) ∝ l−β−1, with β > 0. Unlike Lévy flights, where jumps occur instantaneously, Lévy walks proceed at a finite speed. This finite propagation speed, combined with the fat-tailed step distribution when β < 2, induces non-Markovian statistics at the trajectory level, and has been observed in diverse natural systems, from bacterial motion35 to human mobility57. Notably, Lévy walks and Lévy flights exhibit the same exploration process (xn), whose definition ignores physical time t. Flips are thus identical to those of Lévy flights, which are scale-invariant and hence satisfy πn ∝ 1/n. Hence, the lack of strict scale invariance in Lévy walks58 does not affect our result. In the arrival convention, the exploration of one-dimensional Lévy flights and walks is compact for β > 1, marginally compact for β = 1, and transient for β < 1. (I-ii) Random Acceleration Process (RAP) is one of the simplest non-Markovian processes37. It corresponds to integrated Brownian motion, \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${X}_{t}=\int_{0}^{t}{B}_{u}\,{{{\rm{d}}}}u$$\end{document}Xt=∫0tBudu, where the position results from integrating a Brownian velocity. This model is fundamental in describing systems where momentum or inertia leads to long-range speed correlations. (II) Fractional Brownian Motion (fBM)39 is a Gaussian process with stationary increments obeying \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\langle {({X}_{t}-{X}_{s})}^{2}\rangle=| t-s{| }^{2H}$$\end{document}⟨(Xt−Xs)2⟩=∣t−s∣2H, where \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$0 < H={d}_{w}^{-1} < 1$$\end{document}0