The book examines in some depth two important classes of point
processes, determinantal processes and “Gaussian zeros”,
i.e., zeros of random analytic functions with Gaussian
coefficients. These processes share a property of
“point-repulsion”, where distinct points are less likely
to fall close to each other than in processes, such as the Poisson
process, that arise from independent sampling. Nevertheless, the
treatment in the book emphasizes the use of independence: for random
power series, the independence of coefficients is key; for
determinantal processes, the number of points in a domain is a sum of
independent indicators, and this yields a satisfying explanation of
the central limit theorem (CLT) for this point count. Another unifying
theme of the book is invariance of considered point processes under
natural transformation groups.
The book strives for balance between general theory and concrete examples.
On the one hand, it presents a primer on modern techniques on the
interface of probability and analysis. On the other hand, a wealth of
determinantal processes of intrinsic interest are analyzed; these arise
from random spanning trees and eigenvalues of random matrices, as well as
from special power series with determinantal zeros.
The material in the book formed the basis of a graduate course given at
the IAS-Park City Summer School in 2007; the only background knowledge
assumed can be acquired in first-year graduate courses in analysis and
probability.
Graduate students and research mathematicians interested in random processes and their relations to complex analysis.
This book is an introduction to the modern theory of Markov chains,
whose goal is to determine the rate of convergence to the stationary
distribution, as a function of state space size and geometry. This
topic has important connections to combinatorics, statistical physics,
and theoretical computer science. Many of the techniques presented
originate in these disciplines.
The central tools for estimating convergence times, including
coupling, strong stationary times, and spectral methods, are
developed. The authors discuss many examples, including card shuffling and the
Ising model, from statistical mechanics, and present the connection of
random walks to electrical networks and apply it to estimate hitting
and cover times.
The first edition has been used in courses in mathematics and
computer science departments of numerous universities. The second
edition features three new chapters (on monotone chains, the exclusion
process, and stationary times) and also includes smaller additions and
corrections throughout. Updated notes at the end of each chapter
inform the reader of recent research developments.
Undergraduate and graduate students interested in the modern theory of Markov chains.
Mixing times are an active research topic within many fields from statistical physics to the theory of algorithms, as well as having intrinsic interest within mathematical probability and exploiting discrete analogs of important geometry concepts. The first edition became an instant classic, being accessible to advanced undergraduates and yet bringing readers close to current research frontiers. This second edition adds chapters on monotone chains, the exclusion process and hitting time parameters. Having both exercises and citations to important research papers it makes an outstanding basis for either a lecture course or self-study.
-- David Aldous, University of California, Berkeley
Mixing time is the key to Markov chain Monte Carlo, the queen of approximation techniques. With new chapters on monotone chains, exclusion processes, and set-hitting, Markov Chains and Mixing Times is more comprehensive and thus more indispensable than ever. Prepare for an eye-opening mathematical tour!
-- Peter Winkler, Dartmouth College
The study of finite Markov chains has recently attracted increasing interest from a variety of researchers. This is the second edition of a very valuable book on the subject. The main focus is on the mixing time of Markov chains, but there is a lot of additional material.
In this edition, the authors have taken the opportunity to add new material and bring the reader up to date on the latest research. I have used the first edition in a graduate course and I look forward to using this edition for the same purpose in the near future.
-- Alan Frieze, Carnegie Mellon University
Markov Chains and Mixing Times is a magical book, managing to be both friendly and deep. It gently introduces probabilistic techniques so that an outsider can follow. At the same time, it is the first book covering the geometric theory of Markov chains and has much that will be new to experts. It is certainly THE book that I will use to teach from. I recommend it to all comers, an amazing achievement.
-- Persi Diaconis, Mary V. Sunseri Professor of Statistics and Mathematics, Stanford University
In this book, [the authors] rapidly take a well-prepared undergraduate to the frontiers of research. Short, focused chapters with clear logical dependencies allow readers to use the book in multiple ways.
-- CHOICE Magazine
Now available in Second Edition:
MBK/107
This book is an introduction to the modern approach to the
theory of Markov chains. The main goal of this approach is to
determine the rate of convergence of a Markov chain to the stationary
distribution as a function of the size and geometry of the state
space. The authors develop the key tools for estimating convergence
times, including coupling, strong stationary times, and spectral
methods. Whenever possible, probabilistic methods are emphasized. The
book includes many examples and provides brief introductions to some
central models of statistical mechanics. Also provided are accounts
of random walks on networks, including hitting and cover times, and
analyses of several methods of shuffling cards. As a prerequisite,
the authors assume a modest understanding of probability theory and
linear algebra at an undergraduate level. Markov Chains and Mixing
Times is meant to bring the excitement of this active area of
research to a wide audience.
Markov Chains and Mixing Times is a magical book, managing to be both friendly and deep. It gently introduces probabilistic techniques so that an outsider can follow. At the same time, it is the first book covering the geometric theory of Markov chains and has much that will be new to experts. It is certainly THE book that I will use to teach from. I recommend it to all comers, an amazing achievement.
-- Persi Diaconis, Mary V. Sunseri Professor of Statistics and Mathematics, Stanford University
A superb introduction to Markov chains which treats riffle shuffling and stationary times...
-- Sami Assaf, University of Southern California, Persi Diaconis, Stanford University, and Kannan Soundararajan, Stanford University, in their paper "Riffle Shuffles with Biased Cuts"
In this book, [the authors] rapidly take a well-prepared undergraduate to the frontiers of research. Short, focused chapters with clear logical dependencies allow readers to use the book in multiple ways.
-- CHOICE Magazine
This book is a beautiful introduction to Markov chains and the analysis of their convergence towards a stationary distribution. Personally, I enjoyed very much the lucid and clear writing style of the exposition in combination with full mathematical rigor and the fascinating relations of the theory of Markov chains to several other mathematical areas.
-- Zentralblatt MATH
Throughout the book, the authors generously provide concrete examples that motivate theory and illustrate ideas. I expect this superb book to be widely used in graduate courses around the world, and to become a standard reference.
-- Mathematical Reviews
We live in a highly connected world with multiple self-interested
agents interacting and myriad opportunities for conflict and
cooperation. The goal of game theory is to understand these
opportunities.
This book presents a rigorous introduction to the mathematics of
game theory without losing sight of the joy of the subject. This is
done by focusing on theoretical highlights (e.g., at least six Nobel
Prize winning results are developed from scratch) and by presenting
exciting connections of game theory to other fields such as computer
science (algorithmic game theory), economics (auctions and matching
markets), social choice (voting theory), biology (signaling and
evolutionary stability), and learning theory. Both classical topics,
such as zero-sum games, and modern topics, such as sponsored search
auctions, are covered. Along the way, beautiful mathematical tools
used in game theory are introduced, including convexity, fixed-point
theorems, and probabilistic arguments.
The book is appropriate for a first course in game theory at either
the undergraduate or graduate level, whether in mathematics,
economics, computer science, or statistics. The
importance of game-theoretic thinking transcends the academic
setting—for every action we take, we must consider not only its
direct effects, but also how it influences the incentives of
others.
Undergraduate and graduate students and professors interested in game theory and decision making.
This is an attractive candidate as a text for a mathematically rigorous course in game theory at the upper undergraduate or elementary graduate level. It offers an appealing and versatile selection of topics (including some modern ones), clear and well-motivated exposition, a good selection of examples, and a nicely-chosen selection of exercises (some but not all of which have solutions in the back of the book). People who teach, or simply have an interest in game theory, will certainly find this book worth a look.
-- Mark Hunacek, MAA Reviews
Game theory's influence is felt in a wide range of disciplines, and the authors deliver masterfully on the challenge of presenting both the breadth and coherence of its underlying world-view. The book achieves a remarkable synthesis, introducing the reader to the blend of economic insight, mathematical elegance, scientific impact, and counter-intuitive punch that characterizes game theory as a field.
-- Jon Kleinberg, Cornell University, 2006 Nevanlinna Prize winner
A game theory textbook by people who love … games! It covers many classic as well as recent topics of game theory. Its rigorous treatment, interspersed with illuminating examples, makes it a challenging pleasure to read.
-- Sergiu Hart, The Hebrew University of Jerusalem
This beautifully written book introduces the reader to the rich and flourishing subject of game theory. From an exhaustive account of basics of the classical theory to a wide range of modern themes—including auctions, matching markets, sequential decision making—the book presents a great variety of topics in a rigorous yet entertaining manner. The authors guide the reader through the intricacies of game theory with an exquisite mathematical elegance. For anyone interested in the topic, experts and beginners alike, this book is a must.
-- Gábor Lugosi, Pompeu Fabra University, Barcelona, Spain
It is great to have a comprehensive game theory textbook including so many modern topics.
-- Éva Tardos, Cornell University
The Swendsen-Wang dynamics is a Markov chain widely used by
physicists to sample from the Boltzmann-Gibbs distribution of the
Ising model. Cooper, Dyer, Frieze and Rue proved that on the complete
graph \(K_n\) the mixing time of the chain is at most
\(O(\sqrt{n})\) for all non-critical temperatures.
In this paper the authors show that the mixing time is
\(\Theta(1)\) in high temperatures, \(\Theta(\log n)\)
in low temperatures and \(\Theta(n^{1/4})\) at
criticality. They also provide an upper bound of \(O(\log n)\)
for Swendsen-Wang dynamics for the \(q\)-state ferromagnetic
Potts model on any tree of \(n\) vertices.