Probability on Discrete Structures

By: Harry Kesten (Editor), David Aldous (Contribution by), Geoffrey R. Grimmett (Contribution by)

Write A Review

Hardcover | 18 September 2003

At a Glance

Hardcover
364 Pages

Dimensions(cm)
24.13 x 17.15 x 3.18

Hardcover

$169.75

or 4 interest-free payments of $42.44 with

Ships in 5 to 7 business days

Most probability problems involve random variables indexed by space and/or time. These problems almost always have a version in which space and/or time are taken to be discrete. This volume deals with areas in which the discrete version is more natural than the continuous one, perhaps even the only one than can be formulated without complicated constructions and machinery.
The 5 papers of this volume discuss problems in which there has been significant progress in the last few years; they are motivated by, or have been developed in parallel with, statistical physics. They include questions about asymptotic shape for stochastic growth models and for random clusters; existence, location and properties of phase transitions; speed of convergence to equilibrium in Markov chains, and in particular for Markov chains based on models with a phase transition; cut-off phenomena for random walks.
The articles can be read independently of each other. Their unifying theme is that of models built on discrete spaces or graphs. Such models are often easy to formulate. Correspondingly, the book requires comparatively little previous knowledge of the machinery of probability.

Industry Reviews

From the reviews:

"The ... book contains five survey articles which span a very nice part of modern discrete probability theory. ... The world of discrete probability theory seems to be growing at an exponential rate and it is exactly for this reason that such surveys are not only welcome but essential. Each one of these articles is indeed very interesting and both the 'beginner' ... and the expert can learn a tremendous amount. In short, it is a wonderful book and to be recommended." (Jeffrey E. Steif, Combinatorics, Probability and Computing, Vol. 14, 2005)

"This book covers probability problems with random variables whose indices take discrete values. The exposition is very clear and the book provides an introduction to the subject and to the mathematical formalism which is used. Each chapter is on a different topic, and it represents a clear, rather complete review of the state of the art of its own subject." (Guido Gentile, SIAM Review, Vol. 47 (3), 2005)

Shipping

	Standard Shipping	Express Shipping
Metro postcodes:	$9.99	$14.95
Regional postcodes:	$9.99	$14.95
Rural postcodes:	$9.99	$14.95

Orders over $0.00 qualify for free shipping.

How to return your order

At Booktopia, we offer hassle-free returns in accordance with our returns policy. If you wish to return an item, please get in touch with Booktopia Customer Care.

Additional postage charges may be applicable.

Defective items

If there is a problem with any of the items received for your order then the Booktopia Customer Care team is ready to assist you.

For more info please visit our Help Centre.

You Can Find This Book In

Non-Fiction Mathematics Applied Mathematics Stochastics Probability & Statistics Kids & Children's Books Educational Material Mathematics & Numeracy Educational Material

Other Editions and Formats

Paperback

Published: 8th December 2010

View Product

The Random-Cluster Model	p. 73
Models of First-Passage Percolation	p. 125
Relaxation Times of Markov Chains in Statistical Mechanics and Combinatorial Structures	p. 175
Random Walks on Finite Groups	p. 263
Index	p. 347
Introduction	p. 2
A Motivating Example: the Assignment Problem	p. 3
A Stalking Horse: the Partial Matching Problem	p. 4
Organization of the Survey	p. 4
Geometric Graphs and Local Weak Convergence	p. 6
Geometric Graphs	p. 6
<$>{cal G}^ast<$> as a Metric Space	p. 7
Local Weak Convergence	p. 8
The Standard Construction	p. 8
A Prototype: The Limit of Uniform Random Trees	p. 9
Maximal Weight Partial Matching on Random Trees	p. 12
Weighted Matchings of Graphs in General	p. 12
Our Case: Random Trees with Random Edge Weights	p. 12
Two Obvious Guesses: One Right, One Wrong	p. 12
Not Your Grandfather's Recursion	p. 13
A Direct and Intuitive Plan	p. 14
Characterization of the Limit of <$>B(T_n^{small})<$>	p. 16
Characterization of the Limit of <$>B(T_n^{big})<$>	p. 19
The Limit Theorem for Maximum Weight Partial Matchings	p. 21
Closing the Loop: Another Probabilistic Solution of a Fixed-Point Equation	p. 24
From Coupling to Stability - Thence to Convergence	p. 26
Looking Back: Perspective on a Case Study	p. 28
The Mean-Field Model of Distance	p. 29
From Poisson Points in <$>{op R}^{d}<$> to a Simple Distance Model	p. 29
The Poisson Weighted Infinite Tree - or, the PWIT	p. 31
The Cut-off Components of a Weighted Graph and a PWIT	p. 32
The Minimum Spanning Forests of an Infinite Graph	p. 33
The Average Length Per Vertex of the MSF of a PWIT	p. 34
The Connection to Frieze's (3) Theorem	p. 35
Minimal Cost Perfect Matchings	p. 37
A Natural Heuristic - Which Fails for a Good Reason	p. 38
Involution Invariance and the Standard Construction	p. 39
Involution Invariance and the Convergence of MSTs	p. 42
A Heuristic That Works by Focusing on the Unknown	p. 46
A Distributional Identity with a Logistic Solution	p. 47
A Stochastic Process that Constructs a Matching	p. 49
Calculation of a Limiting Constant: <$>pi^{2}/6<$>	p. 52
Passage from a PWIT Matching to a K_n Matching	p. 53
Finally - Living Beyond One's Means	p. 55
Problems in Euclidean Space	p. 56
A Motivating Problem	p. 57
Far Away Places and Their Influence	p. 59
Euclidean Methods and Some Observations in Passing	p. 62
Recurrence of Random Walks in Limits of Planar Graphs	p. 65
Limitations, Challenges, and Perspectives	p. 66
References	p. 69
Introduction	p. 74
Potts and random-cluster processes	p. 77
Random-cluster measures	p. 77
Ising and Potts models	p. 78
Random-cluster and Ising-Potts coupled	p. 80
The limit as <$>q downarrow 0<$>	p. 82
Rank-generating functions	p. 83
Infinite-volume random-cluster measures	p. 84
Stochastic ordering	p. 84
A differential formula	p. 85
Conditional probabilities	p. 85
Infinite-volume weak limits	p. 86
Random-cluster measures on infinite graphs	p. 88
The case q < 1	p. 89
Phase transition, the big picture	p. 91
Infinite open clusters	p. 91
First- and second-order phase transition	p. 92
General results in d (≥ 2) dimensions	p. 95
The subcritical phase, p < p_c(q)	p. 95
The supercritical phase, p > p_c(q)	p. 96
Near the critical point, p ≃ p_c(q)	p. 98
In two dimensions	p. 101
Graphical duality	p. 101
Value of the critical point	p. 103
First-order phase transition	p. 104
SLE limit when q ≤ 4	p. 105
On complete graphs and trees	p. 108
On complete graphs	p. 108
On trees and non-amenable graphs	p. 110
Time-evolutions of random-cluster models	p. 111
Reversible dynamics	p. 111
Coupling from the past	p. 113
Swendsen-Wang dynamics	p. 114
References	p. 116
Introduction	p. 126
The Basic Model and Some Fundamental Questions	p. 126
Notation	p. 128
The Time Constant	p. 129
The Fundamental Processes of Hammersley and Welsh	p. 129
About	p. 131
Minimizing Paths	p. 133
Asymptotic Shape and Shape Fluctuations	p. 134
Shape Theorems for Standard FPP	p. 134
About the Asymptotic Shape for Lattice FPP	p. 138
FPP Based on Poisson Point Processes	p. 140
Upper Bounds on Shape Fluctuations	p. 143
Some Related Longitudinal Fluctuation Exponents	p. 150
Monotonicity	p. 151
Transversal Fluctuations and the Divergence of Shape Fluctuations	p. 154
Transversal Fluctuation Exponents	p. 154
Upper Bounds on <$>xi<$>	p. 155
Lower Bounds on <$>chi<$>	p. 157
Lower Bounds on <$>xi<$>	p. 158
Fluctuations for Other Related Models	p. 160
Infinite Geodesics and Spanning Trees	p. 161
Semi-Infinite Geodesics and Spanning Trees	p. 161
Coalescence and Another Spanning Tree in 2 Dimensions	p. 165
Doubly-Infinite Geodesics	p. 167
Summary of Some Open Problems	p. 168
References	p. 170
Introduction	p. 177
Mixing times for reversible, continuous-time Markov chains	p. 180
Analytic methods	p. 182
Tensorization of the Poincaré and logarithmic Sobolev inequalities	p. 186
Geometric tools	p. 188
Comparison methods	p. 190
Coupling methods and block dynamics	p. 192
Statistical mechanics models in <$>{op Z}^d<$>	p. 194
Notation	p. 194
Grand canonical Gibbs measures	p. 195
Mixing conditions and absence of long-range order	p. 197
Canonical Gibbs measures for lattice gases	p. 201
The ferromagnetic Ising and Potts models	p. 202
FK representation of Potts models	p. 202
Antiferromagnetic models on an arbitrary graph: Potts and hard-core models	p. 204
Model with random interactions	p. 206
Unbounded spin systems	p. 207
Ground states of certain quantum Heisenberg models as classical Gibbs measures	p. 208
Glauber dynamics in <$>{op Z}^d<$>	p. 211
The dynamics in a finite volume	p. 211
The dynamics in an infinite volume	p. 213
Graphical construction	p. 214
Uniform ergodicity and logarithmic Sobolev constant	p. 215
Mixing property versus logarithmic Sobolev constant in <$>{op Z}^d<$>	p. 218
The auxiliary chain and sweeping out relations method	p. 219
The renormalization group approach	p. 220
The martingale method	p. 222
The recursive analysis	p. 225
Rapid mixing for unbounded spin systems	p. 226
Torpid mixing in the phase coexistence region	p. 227
Torpid mixing for the Ising model in <$>Lambda subset {op Z}^{d}<$> with free boundary conditions	p. 227
Interface driven mixing inside one phase	p. 229
Torpid mixing for Potts model in <$>{op Z}^d<$>	p. 231
Glauber dynamics for certain random systems in <$>{op Z}^d<$>	p. 231
Combination of torpid and rapid mixing: the dilute Ising model	p. 231
Relaxation to equilibrium for spin glasses	p. 233
Glauber dynamics for more general structures	p. 234
Glauber dynamics on trees and hyperbolic graphs	p. 235
Glauber dynamics for the hard-core model	p. 236
Cluster algorithms: the Swendsen-Wang dynamics for Potts models	p. 237
Mixing time for conservative dynamics	p. 238
Random transposition, Bernoulli-Laplace and symmetric simple exclusion	p. 239
The asymmetric simple exclusion	p. 240
The Kac model for the Boltzmann equation	p. 245
Adsorbing staircase walks	p. 247
Kawasaki dynamics for lattice gases	p. 248
Diffusive scaling of the mixing time in the one-phase region	p. 249
Torpid mixing in the phase coexistence region	p. 252
References	p. 253
Introduction	p. 264
Background and Notation	p. 267
Finite Markov Chains	p. 267
Invariant Markov Chains on Finite Groups	p. 270
Shuffling Cards and the Cut-off Phenomenon	p. 272
Three Examples of Card Shuffling	p. 272
Exact Computations	p. 274
The Cut-off Phenomenon	p. 277
Probabilistic Methods	p. 281
Coupling	p. 281
Strong Stationary Times	p. 285
Spectrum and Singular Values	p. 289
General Finite Markov Chains	p. 289
The Random Walk Case	p. 292
Lower Bounds	p. 293
Eigenvalue Bounds Using Paths	p. 296
Cayley Graphs	p. 296
The Second Largest Eigenvalue	p. 297
The Lowest Eigenvalue	p. 300
Diameter Bounds, Isoperimetry and Expanders	p. 302
Results Involving Volume Growth Conditions	p. 308
Moderate Growth	p. 308
Nilpotent Groups	p. 311
Nilpotent Groups with many Generators	p. 312
Representation Theory for Finite Groups	p. 315
The General Set-up	p. 315
Abelian Examples	p. 317
Random Random Walks	p. 323
Central Measures and Bi-invariant Walks	p. 325
Characters and Bi-invariance	p. 325
Random Transposition on the Symmetric Group	p. 326
Walks Based on Conjugacy Classes of the Symmetric Group	p. 328
Finite Classical Groups	p. 331
Fourier Analysis for Non-central Measures	p. 334
Comparison Techniques	p. 335
The min-max Characterization of Eigenvalues	p. 335
Comparing Dirichlet Forms Using Paths	p. 336
Comparison for Non-symmetric Walks	p. 339
References	p. 340
Table of Contents provided by Publisher. All Rights Reserved.

Probability on Discrete Structures

At a Glance

Hardcover

Industry Reviews

Shipping

How to return your order

Defective items

You Can Find This Book In

Other Editions and Formats

Paperback

More in Probability & Statistics

Nonparametric Statistics on Stratified Spaces and Their Applications in Object Data Analysis

Implementing R for Statistics

Sampling Theory and Practice

Probability and Statistics for Science and Engineering

Practical Statistics

New Perspectives in Statistical Modeling

Mathematical and Statistical Methods for Actuarial Sciences

Mathematical and Statistical Methods for Actuarial Sciences

Applied Multivariate Statistical Analysis

Foundations of Statistics

Data Assimilation

Methods, Modeling and Applications

Practical Generative Ai

From Concept to Deployment, Building and Deploying Ethical Ai-powered Solutions

Introduction to Medical Statistics

4th edition

Research Methods and Statistics in Psychology

8th Edition

Rationality

What It Is, Why It Seems Scarce, Why It Matters

The Practice of Statistics in the Life Sciences

4th Edition - Digital Update

Mathematical Statistics with Applications

7th Edition

Statistics for The Behavioral Sciences

10th Edition

How the World Really Works

A Scientist's Guide to Our Past, Present, and Future

Business Statistics

11th Edition - A Decision Making Approach, Global Edition

Fooled By Randomness

The Hidden Role of Chance in Life and in the Markets

Hands-On Programming with R

Write Your Own Functions and Simulations

Psychology Statistics For Dummies

For Dummies

Mathematics for Machine Learning

This product is categorised by