Robustness of large-scale stochastic matrices to localized perturbations

Many linear dynamics over networks can be related by duality to the evolution of a Markov chain with state space coinciding with the node set of the network. Examples include opinion dynamics over social networks as well as distributed averaging algorithms for estimation or control. When the transition probability matrix P associated to the Markov chain is irreducible, a key quantity is its invariant probability distribution π = P´π. In this work, we study how π is affected by, possibly non-reversible or non-irreducible, perturbations of P. In particular, we are interested in perturbations which are localized on a small fraction of nodes but are not necessarily small in any induced norm. While classical perturbation results based on matrix analysis can not be applied in this context, we present various bounds on the effect on π of changes of P obtained using coupling and other probabilistic techniques. Such results allow one to find sufficient conditions for the l₁-distance between π and its perturbed version to vanish in the large-scale limit, depending on the mixing time and one additional local property of the original chain P.