Perturbation and Inverse Problems of Stochastic Matrices
(2024) SIAM Journal on Matrix Analysis and Applications — Vol. 45, n° 1, p. 553-584 (2024)
Files
BerkhoutHV23.pdf
Open Access - Adobe PDF
- 324.16 KB
Details
- Authors
Berkhout, Joost 
Heidergott, Bernd Van Dooren, Paul
- Abstract
- It is a classical task in perturbation analysis to find norm bounds on the effect of a perturbation of a stochastic matrix to its stationary distribution, i.e., to the unique normalized left Perron eigenvector. A common assumption is to consider to be given and to find bounds on its impact, but in this paper, we rather focus on an inverse optimization problem called the target stationary distribution problem (TSDP). The starting point is a target stationary distribution, and we search for a perturbation of the minimum norm such that remains stochastic and has the desired target stationary distribution. It is shown that TSDP has relevant applications in the design of, for example, road networks, social networks, hyperlink networks, and queuing systems. The key to our approach is that we work with rank-1 perturbations. Building on those results for rank-1 perturbations, we provide heuristics for the TSDP that construct arbitrary rank perturbations as sums of appropriately constructed rank-1 perturbations.
- Affiliations
Citations
Berkhout, J., Heidergott, B., & Van Dooren, P. (2024). Perturbation and Inverse Problems of Stochastic Matrices. SIAM Journal on Matrix Analysis and Applications, 45(1), 553-584. https://doi.org/10.1137/22m1489162 (Original work published 2024)