Perturbation and Inverse Problems of Stochastic Matrices

It is a classical task in perturbation analysis to find norm bounds on the effect of a perturbation Δ of a stochastic matrix G 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 G+Δ 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.