Majority dynamics on trees and the dynamic cavity method

Details Majority dynamics on trees and the dynamic cavity method Majority dynamics on trees and the dynamic cavity method

2009-07-02

arxiv.org/abs/0907.0449v2

Annals of Applied Probability 2011, Vol. 21, No. 5, 1694-1748

Mathematics

Probability

Published in at http://dx.doi.org/10.1214/10-AAP729 the Annals of Applied Probability (http://www.imstat.org/aap/) by the Inst

Scientific paper

10.1214/10-AAP729

A voter sits on each vertex of an infinite tree of degree $k$, and has to decide between two alternative opinions. At each time step, each voter switches to the opinion of the majority of her neighbors. We analyze this majority process when opinions are initialized to independent and identically distributed random variables. In particular, we bound the threshold value of the initial bias such that the process converges to consensus. In order to prove an upper bound, we characterize the process of a single node in the large $k$-limit. This approach is inspired by the theory of mean field spin-glass and can potentially be generalized to a wider class of models. We also derive a lower bound that is nontrivial for small, odd values of $k$.

Affiliated with

Also associated with

No associations

Rating

Majority dynamics on trees and the dynamic cavity method does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Majority dynamics on trees and the dynamic cavity method, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Majority dynamics on trees and the dynamic cavity method will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-730852