Optimal Redesign of Markov Chains with Prescribed Repulsive Distribution

Optimization over Markov chains is a popular topic, since Markov chains can be used to model several important systems, such as telecommunications, railways or dams. However, most of the existing literature focuses on steady states and limiting distributions, while in some contexts it might be beneficial to design Markov chains with repulsive distributions, i.e., distributions that, once achieved, cause a large probability transition in the system. This, as typically done in Critical Infrastructure systems, corresponds to having resilient Markov chains that 'spring back' after reaching potentially dangerous or unsafe configurations. In this paper we formulate a problem where we aim at redesigning a Markov chain in order from one side to maximize the repulsiveness of a prescribed distribution and from another side to minimize the redesign effort. In more detail, we formulate the problem as an optimization problem, and we provide a necessary and sufficient local optimality condition and a sufficient global optimality condition. We conclude the paper with simulations aimed at numerically demonstrating the theoretical findings in the paper.