On Survival Time in Robust Optimization over Time for Discrete Search Spaces

Robust Optimization Over Time (ROOT) addresses dynamic optimization problems where the goal is not to track the transient optimum but to identify solutions that remain effective across multiple future environments. Despite recent algorithmic advances, the theoretical foundations of ROOT remain limited, particularly regarding survival-time formulations in discrete search spaces. This paper bridges this gap by analyzing expected survival time in combinatorial ROOT under stochastic k-bit-flip dynamics. Using drift analysis and martingale techniques, we derive order-matching analytical bounds and phase transitions for dynamic OneMax, capturing gradual fitness degradation. For dynamic LeadingOnes, which models catastrophic structural failure, we prove that survival time follows an exact geometric distribution. Monte Carlo simulations empirically validate these analytical models. Ultimately, these results connect ROOT with classical runtime analysis, formalizing the mechanisms governing solution durability and providing a rigorous mathematical foundation for survival-aware heuristics in combinatorial environments.