Optimal non-Markovian search strategies with n-step memory

Abstract

Stochastic search processes are ubiquitous in nature and are expected to become more efficient when equipped with a memory, where the searcher has been before. A natural realization of a search process with long-lasting memory is a migrating cell that is repelled from the diffusive chemotactic signal that it secrets on its way, denoted as auto-chemotactic searcher. To analyze the efficiency of this class of non-Markovian search processes we present a general formalism that allows to compute the mean first passage time (MFPT) for a given set of conditional transition probabilities for non-Markovian random walks on a lattice. We show that the optimal choice of the $n$-step transition probabilities decreases the MFPT systematically and substantially with an increasing number of steps. It turns out that the optimal search strategies can be reduced to simple cycles defined by a small parameter set and that mirror-asymmetric walks are more efficient. For the auto-chemotactic searcher we show that an optimal coupling between the searcher and the chemical reduces the MFPT to 1/3 of the one for a Markovian random walk.

References in corpus (20)

• Intermittent search strategies
• First-passage times in complex scale-invariant media
• First Passage Under Restart
• Optimal search strategies for hidden targets
• Chemotaxis and auto-chemotaxis of self-propelling artificial droplet swimmers
• Dynamic clustering and chemotactic collapse of self-phoretic active particles
• First-passage times for random walks in bounded domains
• First passages in bounded domains: When is the mean first passage time meaningful?
• Mean first-passage times of non-Markovian random walkers in confinement
• Phoretic Motion of Spheroidal Particles Due To Self-Generated Solute Gradients
• First passage time distribution in heterogeneity controlled kinetics: going beyond the mean first passage time
• Search with home returns provides advantage under high uncertainty
• Optimizing persistent random searches
• Effective dynamics of microorganisms that interact with their own trail
• Strong-coupling dynamics of a multi-cellular chemotactic system
• Dynamics of a microorganism moving by chemotaxis in its own secretion
• First Passage Time Densities in Non-Markovian Models with Subthreshold Oscillations
• Self-trapping self-repelling random walks
• Exact expressions of mean first-passage times and splitting probabilities for random walks in bounded rectangular domains
• Chemotaxis emerges as the optimal solution to cooperative search games

Cited by in corpus (20)

• Splitting Probabilities of Jump Processes
• Phase transition in non-Markovian animal exploration model with preferential returns
• Random walks with stochastic resetting in complex networks: a discrete time approach
• Fast rare events in exit times distributions of jump processes
• Entropy estimators for Markovian sequences: A comparative analysis
• Learning how to find targets in the micro-world: The case of intermittent active Brownian particles
• Controlling Uncertainty of Empirical First-Passage Times in the Small-Sample Regime
• Optimal foraging strategies can be learned
• Population heterogeneity in the fractional master equation, ensemble self-reinforcement and strong memory effects
• Noise-induced network topologies
• Loss of Percolation Transition in the Presence of Simple Tracer-Media Interactions
• From Maximum of Intervisit Times to Starving Random Walks
• Leftward, Rightward and Complete Exit Time Distributions of Jump Processes
• Entropy of Sharp Restart
• Optimal Searcher Distribution for Parallel Random Target Searches
• Stochastic Resetting Mitigates Latent Gradient Bias of SGD from Label Noise
• Multi-target search in bounded and heterogeneous environments: a lattice random walk perspective
• An improved estimator of Shannon entropy with applications to systems with memory
• Universal Linear Response of First-Passage Kinetics: A Framework for Prediction and Inference
• Self-interacting processes via Doob conditioning