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.

Optimal Redesign of Markov Chains with Prescribed Repulsive Distribution

Oliva G.
2019-01-01

Abstract

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.
2019
978-1-5386-1395-5
File in questo prodotto:
File Dimensione Formato  
Optimal_Redesign_of_Markov_Chains_with_Prescribed_Repulsive_Distribution.pdf

non disponibili

Licenza: Non specificato
Dimensione 593.24 kB
Formato Adobe PDF
593.24 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/20.500.12610/74508
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? ND
social impact