Book contents
- Frontmatter
- Contents
- Preface
- Euclidean geometry of distance regular graphs
- Large sets of Steiner triples
- Searching with lies
- Spin models for link invariants
- Computational Pólya theory
- Mixing of random walks and other diffusions on a graph
- Cayley graphs: eigenvalues, expanders and random walks
- Construction and classification of combinatorial designs
- Modern probabilistic methods in combinatorics
Mixing of random walks and other diffusions on a graph
Published online by Cambridge University Press: 05 May 2010
- Frontmatter
- Contents
- Preface
- Euclidean geometry of distance regular graphs
- Large sets of Steiner triples
- Searching with lies
- Spin models for link invariants
- Computational Pólya theory
- Mixing of random walks and other diffusions on a graph
- Cayley graphs: eigenvalues, expanders and random walks
- Construction and classification of combinatorial designs
- Modern probabilistic methods in combinatorics
Summary
Abstract
We survey results on two diffusion processes on graphs: random walks and chip-firing (closely related to the “abelian sandpile” or “avalanche” model of self-organized criticality in statistical mechanics). Many tools in the study of these processes are common, and results on one can be used to obtain results on the other.
We survey some classical tools in the study of mixing properties of random walks; then we introduce the notion of “access time” between two distributions on the nodes, and show that it has nice properties. Surveying and extending work of Aldous, we discuss several notions of mixing time of a random walk.
Then we describe chip-firing games, and show how these new results on random walks can be used to improve earlier results. We also give a brief illustration how general results on chip-firing games can be applied in the study of avalanches.
Introduction
A number of graph-theoretic models, involving various kinds of diffusion processes, lead to basically one and the same issue of “global connectivity” of the graph. These models include: random walks on graphs, especially their use in sampling algorithms; the “avalanche” or “sandpile” model of catastrophic events, which is mathematically equivalent to “chip-firing” games; load balancing in distributed networks; and, somewhat more distantly but clearly related, multicommodity flows and routing in VLSI. In this paper we survey some recent results on the first two topics, as well as their connections.
Random walks. The study of random walks on finite graphs, a.k.a. finite Markov chains, is one of the classical fields of probability theory.
- Type
- Chapter
- Information
- Surveys in Combinatorics, 1995 , pp. 119 - 154Publisher: Cambridge University PressPrint publication year: 1995
You have
Access
- 26
- Cited by