Upper bounds are derived on the total variation distance between the invariant distributions of two stochastic matrices differing on a subset W of rows. Such bounds depend on three parameters: the mixing time and the minimal expected hitting time on
W for the Markov chain associated to one of the matrices; and the escape time from W for the Markov chain associated to the other matrix. These results, obtained through coupling techniques, prove particularly useful in scenarios where W is a small subset of the state space, even if the difference between the two matrices is not small in any norm. Several applications to large-scale network problems are discussed, including robustness of Googles PageRank algorithm, distributed averaging and consensus algorithms, and interacting particle systems.
We study a tractable opinion dynamics model that generates long-run disagreements and persistent opinion fluctuations. Our model involves an inhomogeneous stochastic gossip process of continuous opinion dynamics in a society consisting of two types o
f agents: regular agents, who update their beliefs according to information that they receive from their social neighbors; and stubborn agents, who never update their opinions. When the society contains stubborn agents with different opinions, the belief dynamics never lead to a consensus (among the regular agents). Instead, beliefs in the society fail to converge almost surely, the belief profile keeps on fluctuating in an ergodic fashion, and it converges in law to a non-degenerate random vector. The structure of the network and the location of the stubborn agents within it shape the opinion dynamics. The expected belief vector evolves according to an ordinary differential equation coinciding with the Kolmogorov backward equation of a continuous-time Markov chain with absorbing states corresponding to the stubborn agents and converges to a harmonic vector, with every regular agents value being the weighted average of its neighbors values, and boundary conditions corresponding to the stubborn agents. Expected cross-products of the agents beliefs allow for a similar characterization in terms of coupled Markov chains on the network. We prove that, in large-scale societies which are highly fluid, meaning that the product of the mixing time of the Markov chain on the graph describing the social network and the relative size of the linkages to stubborn agents vanishes as the population size grows large, a condition of emph{homogeneous influence} emerges, whereby the stationary beliefs marginal distributions of most of the regular agents have approximately equal first and second moments.
Scaling limits are analyzed for stochastic continuous opinion dynamics systems, also known as gossip models. In such models, agents update their vector-valued opinion to a convex combination (possibly agent- and opinion-dependent) of their current va
lue and that of another observed agent. It is shown that, in the limit of large agent population size, the empirical opinion density concentrates, at an exponential probability rate, around the solution of a probability-measure-valued ordinary differential equation describing the systems mean-field dynamics. Properties of the associated initial value problem are studied. The asymptotic behavior of the solution is analyzed for bounded-confidence opinion dynamics, and in the presence of an heterogeneous influential environment.
