Perturbation and Inverse Problems of Stochastic Matrices
Joost Berkhout, Bernd Heidergott, Paul Van Dooren · SIAM Journal on Matrix Analysis and Applications · 2024
Abstract. It is a classical task in perturbation analysis to find norm bounds on the effect of a perturbation [Formula: see text] of a stochastic matrix [Formula: see text] to its stationary distribution, i.e., to the unique normalized left Perron eigenvector. A common assumption is to consider [Formula: see text] 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 [Formula: see text] of the minimum norm such that [Formula: see text] 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.