Discrete-time random walks and Lévy flights on arbitrary networks: when resetting becomes advantageous?
arXiv:2110.15437 · doi:10.1088/1751-8121/ac72d9
Abstract
The spectral theory of random walks on networks of arbitrary topology can be readily extended to study random walks and Lévy flights subject to resetting on these structures. When a discrete-time process is stochastically brought back from time to time to its starting node, the mean search time needed to reach another node of the network may be significantly decreased. In other cases, however, resetting is detrimental to search. Using the eigenvalues and eigenvectors of the transition matrix defining the process without resetting, we derive a general criterion for finite networks that establishes when there exists a non-zero resetting probability that minimizes the mean first passage time at a target node. Right at optimality, the coefficient of variation of the first passage time is not unity, unlike in continuous time processes with instantaneous resetting, but above 1 and depends on the minimal mean first passage time. The approach is general and applicable to the study of different discrete-time ergodic Markov processes such as Lévy flights, where the long-range dynamics is introduced in terms of the fractional Laplacian of the graph. We apply these results to the study of optimal transport on rings and Cayley trees.
arXiv comment20 pages, 6 figures
References in corpus (41)
- Diffusion with Stochastic Resetting
- Random walks and diffusion on networks
- Stochastic Resetting and Applications
- Diffusion with Optimal Resetting
- First Passage Under Restart
- First order transition for the optimal search time of Lévy flights with resetting
- Optimal stochastic restart renders fluctuations in first passage times universal
- Experimental realization of diffusion with stochastic resetting
- Diffusion under time-dependent resetting
- Run and tumble particle under resetting: a renewal approach
- Optimal mean first-passage time for a Brownian searcher subjected to resetting: experimental and theoretical results
- Diffusion with stochastic resetting at power-law times
- Global mean first-passage times of random walks on complex networks
- Non-equilibrium steady states of stochastic processes with intermittent resetting
- First passage under stochastic resetting in an interval
- Optimal first arrival times in Lévy flights with resetting
- Boosting search by rare events
- Google matrix analysis of directed networks
- Stochastic Search with Poisson and Deterministic Resetting
- Search with home returns provides advantage under high uncertainty
- Monotonous continuous-time random walks with drift and stochastic reset events
- Long-Range Navigation on Complex Networks using Lévy Random Walks
- Péclet number governs transition to acceleratory restart in drift-diffusion
- Landau theory of restart transitions
- Random walks on networks with stochastic resetting
- Random walk with random resetting to the maximum
- Fractional dynamics on networks: Emergence of anomalous diffusion and Lévy flights
- Stochastic resetting with stochastic returns using external trap
- Transport properties and first arrival statistics of random searches with stochastic reset times
- Spectral properties of simple classical and quantum reset processes
- First passage under restart for discrete space and time: application to one dimensional confined lattice random walks
- On subdiffusive continuous time random walks with stochastic resetting
- Sisyphus random walk
- Intermittent resetting potentials
- Diffusive transport on networks with stochastic resetting to multiple nodes
- Comparison of two models of tethered motion
- Mean-performance of sharp restart I: Statistical roadmap
- From classical to quantum walks with stochastic resetting on networks
- First passage of a diffusing particle under stochastic resetting in bounded domains with spherical symmetry
- Random walks with long-range steps generated by functions of Laplacian matrices
- Random Walks on Complex Networks