Assigning Stationary Distributions to Sparse Stochastic Matrices

The target stationary distribution problem (TSDP) is the following: given an irreducible stochastic matrix G and a target stationary distribution μ, construct a minimum norm perturbation, Δ, such that G = G+Δ is also stochastic and has the prescribed target stationary distribution, μ. In this paper, we revisit the TSDP under a constraint on the support of Δ, that is, on the set of non-zero entries of Δ. This is particularly meaningful in practice since one cannot typically modify all entries of G. We first show how to construct a feasible solution G that has essentially the same support as the matrix G. Then we show how to compute globally optimal and sparse solutions using the component-wise ₁ norm and linear optimization. We propose an efficient implementation that relies on a column-generation approach which allows us to solve sparse problems of size up to 10⁵ × 10⁵ in a few minutes. We illustrate the proposed algorithms with several numerical experiments.