The Pendulum Arrangement: Maximizing the Escape Time of Heterogeneous Random Walks
arXiv:2007.13232
Abstract
We identify a fundamental phenomenon of heterogeneous one dimensional random walks: the escape (traversal) time is maximized when the heterogeneity in transition probabilities forms a pyramid-like potential barrier. This barrier corresponds to a distinct arrangement of transition probabilities, sometimes referred to as the pendulum arrangement. We reduce this problem to a sum over products, combinatorial optimization problem, proving that this unique structure always maximizes the escape time. This general property may influence studies in epidemiology, biology, and computer science to better understand escape time behavior and construct intruder-resilient networks.
arXiv commentNames ordered alphabetically
References in corpus (11)
- Epidemic spreading in scale-free networks
- Forecast and Control of Epidemics in a Globalized World
- First-passage times in complex scale-invariant media
- Optimal search strategies for hidden targets
- Biased random walks on complex networks: the role of local navigation rules
- First passage time for random walks in heterogeneous networks
- Distance matters: the impact of gene proximity in bacterial gene regulation
- First passage time distribution in heterogeneity controlled kinetics: going beyond the mean first passage time
- Network Cosmology
- Generalized Gambler's Ruin Problem: explicit formulas via Siegumd duality
- First-passage time distribution for random walks on complex networks using inverse Laplace transform and mean-field approximation