Seminar Details
2011-03-08 (15.00) : Democracy in Markov Chains and Its Preservation under Local Perturbations
At Euler building
Organized by Mathematical Engineering
Speaker :
Delvenne, Jean-Charles
Abstract :
A sequence of irreducible Markov chains with increasing state
cardinality is called democratic if the sequence of corresponding
invariant probabilities converges to 0 uniformly. Democracy is a
relevant property which naturally shows up when we deal with distributed
algorithms like consensus or with opinion dynamic models: it says that
each agent measure/opinion is going to play a negligeable role in the
asymptotic behavior of the global system. Simple random walks on
undirected graphs of bounded degree and increasing cardinality are one
of the simplest examples of democratic chains. Similar examples can be
built considering more general time-reversible chains. In this paper we
prove a general result which says that, under some technical
assumptions, perturbing the transition probabilities from a finite
number of vertices of a time-reversible democratic sequence of chains,
democracy is preserved. We want to stress the fact that the local
perturbation in general breaks the time-reversibility of the chains. The
main technical assumption needed in our result is the irreducibility of
the limit Markov chains and we show with an example that this assumption
is indeed necessary.