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.
Stability of Wardrop equilibria is analyzed for dynamical transportation networks in which the drivers route choices are influenced by information at multiple temporal and spatial scales. The considered model involves a continuum of indistinguishable
drivers commuting between a common origin/destination pair in an acyclic transportation network. The drivers route choices are affected by their, relatively infrequent, perturbed best responses to global information about the current network congestion levels, as well as their instantaneous local observation of the immediate surroundings as they transit through the network. A novel model is proposed for the drivers route choice behavior, exhibiting local consistency with their preference toward globally less congested paths as well as myopic decisions in favor of locally less congested paths. The simultaneous evolution of the traffic congestion on the network and of the aggregate path preference is modeled by a system of coupled ordinary differential equations. The main result shows that, if the frequency of updates of path preferences is sufficiently small as compared to the frequency of the traffic flow dynamics, then the state of the transportation network ultimately approaches a neighborhood of the Wardrop equilibrium. The presented results may be read as a further evidence in support of Wardrops postulate of equilibrium, showing robustness of it with respect to non-persistent perturbations. The proposed analysis combines techniques from singular perturbation theory, evolutionary game theory, and cooperative dynamical systems.
A single-letter characterization is provided for the capacity region of finite-state multiple-access channels, when the channel state process is an independent and identically distributed sequence, the transmitters have access to partial (quantized)
state information, and complete channel state information is available at the receiver. The partial channel state information is assumed to be asymmetric at the encoders. As a main contribution, a tight converse coding theorem is presented. The difficulties associated with the case when the channel state has memory are discussed and connections to decentralized stochastic control theory are presented.
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.
The error exponent of Markov channels with feedback is studied in the variable-length block-coding setting. Burnashevs classic result is extended and a single letter characterization for the reliability function of finite-state Markov channels is pre
sented, under the assumption that the channel state is causally observed both at the transmitter and at the receiver side. Tools from stochastic control theory are used in order to treat channels with intersymbol interference. In particular the convex analytical approach to Markov decision processes is adopted to handle problems with stopping time horizons arising from variable-length coding schemes.
