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 \(\nu_{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