Note. From now on (May 2011) this is an archival page, i.e. will not be modified. In particular the lecture notes may have errors and certainly have much omitted relevant work. See the page FMIE processes (under construction) for any more recent lectures or papers.

## STAT 260, Spring 2011: David Aldous

STAT 260, with catalog description Topics in Probability and Statistics, is intended to have a different subject each semester. My topic is (to invent a name) Finite Markov Information-Exchange Processes. The general set-up, outlined below, is directly or indirectly related to models treated in literally thousands of papers over the last ten years, in fields such as statistical physics and interacting particle systems; epidemic theory; broadcast algorithms on graphs; ad hoc networks; social learning theory.

### The general set-up: FMIE processes

There are n "agents". Each agent has some "information" at time t. Each pair (ij) meets at random times of rate \nu_{ij}, at which times they can update their information according to some rule.

So it's a two-level modeling framework. The bottom level is the "geometry", specified by the rate matrix (\nu_{ij}), of how agents meet. The top level is the "content" of whatever phenomenon we are trying to model.

Existing literature tends to focus on specific geometries, building up from simple to more complex interaction rules. A future research focus would be to attempt a more thorough analysis of simple interaction rules used with general geometries, analogous to the standard theory of finite Markov chains. Much of the present course will involve looking at existing literature which might be meaningfully translated into the FMIE context. In particular one can take algorithmic questions, interpretable as concerning spread of information", which have been studied in the traditional n-vertex graph context, and reconsider them in the FMIE context.

## Slides from lectures

Lectures are a mixture of slides and blackboard work.

### Student talks

Nominally 25-minute talks, but you can over-run if there are only 2 that day.

Wednesday 20 April

Monday 25 April

• Jack Reilly: More about the rank-based game. (course project).
• Miki Racz: Combining voter and exclusion dynamics.
• Anupam Prakash: COMPUTING SYMMETRIC FUNCTIONS ON MEMORY BOUNDED SOCIAL NETWORKS.

Wednesday 27 April

Wednesday 4 May

### Papers

Here is an unorganized list of possibly relevant papers.

### Similar courses elsewhere

Here are some other courses on the broad "information and networks" theme which have interesting material accessible online. These courses tend to cover a much broader range of topics at a less sophisticated mathematical level.

(Kleinberg; Cornell) The Structure of Information Networks
(Leskovec; Stanford) Social and Information Network Analysis
(Saberi; Stanford) Information Networks
(Kearns; U. Penn) Social networks and algorithmic game theory

More advanced and specialized than the above is
(Mossel; Berkeley) Social Choice and Networks.

Our course does not focus on models of network formation, which is a major topic of other courses; see e.g. my old course Random graphs and complex networks.