Home | Current | Past volumes | About | Login | Notify | Contact | Search
 Probability Surveys > Vol. 9 (2012) open journal systems 

A lecture on the averaging process

David Aldous, University of California, Berkeley
Daniel Lanoue, University of California, Berkeley

To interpret interacting particle system style models as social dynamics, suppose each pair {i,j} of individuals in a finite population meet at random times of arbitrary specified rates νij, and update their states according to some specified rule. The averaging process has real-valued states and the rule: upon meeting, the values $X_i(t-), X_j(t-)$ are replaced by $\frac{1}{2}(X_i(t-)+X_j(t-)), \frac{1}{2}(X_i(t-)+X_j(t-))$. It is curious this simple process has not been studied very systematically. We provide an expository account of basic facts and open problems.

AMS 2000 subject classifications: Primary 60K35; secondary 60K99.

Keywords: Duality, interacting particle systems, rate of convergence, spectral gap, voter model.

Creative Common LOGO

Full Text: PDF

Aldous, David, Lanoue, Daniel, A lecture on the averaging process, Probability Surveys, 9, (2012), 90-102 (electronic). DOI: 10.1214/11-PS184.


[1]    Acemoglu, D., Como, G., Fagnini, F. and Ozdaglar, A. (2011). Opinion fluctuations and disagreement in social networks. http://arxiv.org/abs/1009.2653

[2]    Aldous, D. (2011). Finite Markov Information-Exchange Procesess. Lecture Notes from Spring 2011. http://www.stat.berkeley.edu/~aldous/260-FMIE/Lectures/index.html.

[3]     Aldous, D. and Fill, J. Reversible Markov Chains and Random Walks on Graphs. http://www.stat.berkeley.edu/~aldous/RWG/book.html

[4]    Ben-Naim, E., Krapivsky, P.L. and Redner, S. (2003). Bifurcations and patterns in compromise processes. Phys. D 183 190–204.

[5]    Diaconis, P. and Saloff-Coste, L. (1996). Logarithmic Sobolev inequalities for finite Markov chains. Ann. Appl. Probab. 6 695–750. MR1410112

[6]    Häggström, O. (2011). A pairwise averaging procedure with application to consensus formation in the Deffuant model. http://www.math.chalmers.se/~olleh/averaging.pdf.

[7]    Lanchier, N. (2011). The critical value of the bounded confidence Deffuant model equals one half. http://stat.asu.edu/~lanchier/articles/2011h_lanchier.pdf.

[8]    Levin, D. A., Peres, Y. and Wilmer, E. L. (2009), Markov Chains and Mixing Times. Amer. Math. Soc., Providence, RI. MR2466937

[9]    Liggett, T. M. (1985). Interacting Particle Systems. Springer-Verlag, New York. MR776231

[10]    Montenegro, R. and Tetali, P. (2006). Mathematical aspects of mixing times in Markov chains. Found. Trends Theor. Comput. Sci. 1 1–121. MR2341319

[11]    Olshevsky, A. and Tsitsiklis, J. N. (2009). Convergence speed in distributed consensus and averaging. SIAM J. Control Optim. 48 33–55. MR2480125

[12]    Shah, D. (2008). Gossip algorithms. Foundations and Trends in Networking 3 1–125.

Home | Current | Past volumes | About | Login | Notify | Contact | Search

Probability Surveys. ISSN: 1549-5787