The Pendulum Arrangement: Maximizing the Escape Time of Heterogeneous Random Walks

2020/07/26 by Asaf Cassel, Shie Mannor, Cassel, Asaf +3
Biochemistry, Genetics and Molecular Biology · Physics and Astronomy · #Combinatorics (math.CO) #Complex Network Analysis Techniques #Data Analysis #Diffusion and Search Dynamics #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #FOS: Physical sciences #Opinion Dynamics and Social Influence #Optimization and Control (math.OC) #Probability (math.PR) #Statistics and Probability (physics.data-an)

paper · pdf · doi:10.48550/arxiv.2007.13232

openalex publication_date 2020/07/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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.

Related

• Random walks on hyperplane arrangements and stopping times
• Optimal strong stationary times for random walks on the chambers of a\n hyperplane arrangement
• Rate of Escape of the Mixer Chain
• Random Walks on Complex Networks
• On Self-Avoiding Walks across n-Dimensional Dice and Combinatorial Optimization: An Introduction