Probability on discrete structures

>> Google Books

所蔵情報QRコード

Probability on discrete structures / Harry Kesten (editor)

資料種別:: 図書
出版情報:: Berlin ; Tokyo : Springer, c2004
形態:: vi, 351 p. ; 25 cm
シリーズ名:: Encyclopaedia of mathematical sciences / editor-in-chief, R.V. Gamkrelidze ; v. 110 . Probability theory ; 1 <BA01321819>
著者名:: Kesten, Harry, 1931- <DA00848127>
ISBN:: 9783540008453 [3540008454]
書誌ID:: BA63803987

子書誌情報

フルテキスト

所蔵情報

他の版・巻

書誌詳細

注記:

Includes bibliographical references and index

主題:

Combinatorial probabilities; Markov processes; Random graphs

言語:

英語

目次情報:

The Random-Cluster Model / Geoffrey Grimmett

Models of First-Passage Percolation / C. Douglas Howard

Relaxation Times of Markov Chains in Statistical Mechanics and Combinatorial Structures / Fabio Martinelli

Random Walks on Finite Groups / Laurent Saloff-Coste

Index

Introduction / 1：

A Motivating Example: the Assignment Problem / 1.1：

A Stalking Horse: the Partial Matching Problem / 1.2：

Organization of the Survey / 1.3：

Geometric Graphs and Local Weak Convergence / 2：

Geometric Graphs / 2.1：

<$>{\cal G}^\ast<$> as a Metric Space / 2.2：

Local Weak Convergence / 2.3：

The Standard Construction / 2.4：

A Prototype: The Limit of Uniform Random Trees / 2.5：

Maximal Weight Partial Matching on Random Trees / 3：

Weighted Matchings of Graphs in General / 3.1：

Our Case: Random Trees with Random Edge Weights / 3.2：

Two Obvious Guesses: One Right, One Wrong / 3.3：

Not Your Grandfather's Recursion / 3.4：

A Direct and Intuitive Plan / 3.5：

Characterization of the Limit of <$>B(T_n^{small})<$> / 3.6：

Characterization of the Limit of <$>B(T_n^{big})<$> / 3.7：

The Limit Theorem for Maximum Weight Partial Matchings / 3.8：

Closing the Loop: Another Probabilistic Solution of a Fixed-Point Equation / 3.9：

From Coupling to Stability - Thence to Convergence / 3.10：

Looking Back: Perspective on a Case Study / 3.11：

The Mean-Field Model of Distance / 4：

From Poisson Points in <$>{\op R}^{d}<$> to a Simple Distance Model / 4.1：

The Poisson Weighted Infinite Tree - or, the PWIT / 4.2：

The Cut-off Components of a Weighted Graph and a PWIT / 4.3：

The Minimum Spanning Forests of an Infinite Graph / 4.4：

The Average Length Per Vertex of the MSF of a PWIT / 4.5：

The Connection to Frieze's ζ(3) Theorem / 4.6：

Minimal Cost Perfect Matchings / 5：

A Natural Heuristic - Which Fails for a Good Reason / 5.1：

Involution Invariance and the Standard Construction / 5.2：

Involution Invariance and the Convergence of MSTs / 5.3：

A Heuristic That Works by Focusing on the Unknown / 5.4：

A Distributional Identity with a Logistic Solution / 5.5：

A Stochastic Process that Constructs a Matching / 5.6：

Calculation of a Limiting Constant: <$>\pi^{2}/6<$> / 5.7：

Passage from a PWIT Matching to a K_n Matching / 5.8：

Finally - Living Beyond One's Means / 5.9：

Problems in Euclidean Space / 6：

A Motivating Problem / 6.1：

Far Away Places and Their Influence / 6.2：

Euclidean Methods and Some Observations in Passing / 6.3：

Recurrence of Random Walks in Limits of Planar Graphs / 6.4：

Limitations, Challenges, and Perspectives / 7：

References

Potts and random-cluster processes

Random-cluster measures

Ising and Potts models

Random-cluster and Ising-Potts coupled

The limit as <$>q \downarrow 0<$>

Rank-generating functions

Infinite-volume random-cluster measures

Stochastic ordering

A differential formula

Conditional probabilities

Infinite-volume weak limits

Random-cluster measures on infinite graphs

The case q < 1

Phase transition, the big picture

Infinite open clusters

First- and second-order phase transition

General results in d (≥ 2) dimensions

The subcritical phase, p < p_c(q)

The supercritical phase, p > p_c(q)

Near the critical point, p ≃ p_c(q)

In two dimensions

Graphical duality

Value of the critical point

First-order phase transition

SLE limit when q ≤ 4

On complete graphs and trees

On complete graphs / 7.1：

On trees and non-amenable graphs / 7.2：

Time-evolutions of random-cluster models / 8：

Reversible dynamics / 8.1：

Coupling from the past / 8.2：

Swendsen-Wang dynamics / 8.3：

The Basic Model and Some Fundamental Questions

Notation

The Time Constant

The Fundamental Processes of Hammersley and Welsh

About μ

Minimizing Paths

Asymptotic Shape and Shape Fluctuations

Shape Theorems for Standard FPP

About the Asymptotic Shape for Lattice FPP

FPP Based on Poisson Point Processes

Upper Bounds on Shape Fluctuations

Some Related Longitudinal Fluctuation Exponents

Monotonicity

Transversal Fluctuations and the Divergence of Shape Fluctuations

Transversal Fluctuation Exponents

Upper Bounds on <$>\xi<$>

Lower Bounds on <$>\chi<$>

Lower Bounds on <$>\xi<$>

Fluctuations for Other Related Models

Infinite Geodesics and Spanning Trees

Semi-Infinite Geodesics and Spanning Trees

Coalescence and Another Spanning Tree in 2 Dimensions

Doubly-Infinite Geodesics

Summary of Some Open Problems

Mixing times for reversible, continuous-time Markov chains

Analytic methods

Tensorization of the Poincaré and logarithmic Sobolev inequalities

Geometric tools

Comparison methods

Coupling methods and block dynamics

Statistical mechanics models in <$>{\op Z}^d<$>

Grand canonical Gibbs measures

Mixing conditions and absence of long-range order

Canonical Gibbs measures for lattice gases

The ferromagnetic Ising and Potts models

FK representation of Potts models

Antiferromagnetic models on an arbitrary graph: Potts and hard-core models

Model with random interactions

Unbounded spin systems

Ground states of certain quantum Heisenberg models as classical Gibbs measures

Glauber dynamics in <$>{\op Z}^d<$>

The dynamics in a finite volume

The dynamics in an infinite volume

Graphical construction

Uniform ergodicity and logarithmic Sobolev constant

Mixing property versus logarithmic Sobolev constant in <$>{\op Z}^d<$>

The auxiliary chain and sweeping out relations method

The renormalization group approach

The martingale method

The recursive analysis

Rapid mixing for unbounded spin systems

Torpid mixing in the phase coexistence region

Torpid mixing for the Ising model in <$>\Lambda \subset {\op Z}^{d}<$> with free boundary conditions

Interface driven mixing inside one phase

Torpid mixing for Potts model in <$>{\op Z}^d<$>

Glauber dynamics for certain random systems in <$>{\op Z}^d<$>

Combination of torpid and rapid mixing: the dilute Ising model

Relaxation to equilibrium for spin glasses

Glauber dynamics for more general structures

Glauber dynamics on trees and hyperbolic graphs

Glauber dynamics for the hard-core model

Cluster algorithms: the Swendsen-Wang dynamics for Potts models

Mixing time for conservative dynamics / 9：

Random transposition, Bernoulli-Laplace and symmetric simple exclusion / 9.1：

The asymmetric simple exclusion / 9.2：

The Kac model for the Boltzmann equation / 9.3：

Adsorbing staircase walks / 9.4：

Kawasaki dynamics for lattice gases / 10：

Diffusive scaling of the mixing time in the one-phase region / 10.1：

Background and Notation / 10.2：

Finite Markov Chains

Invariant Markov Chains on Finite Groups

Shuffling Cards and the Cut-off Phenomenon

Three Examples of Card Shuffling

Exact Computations

The Cut-off Phenomenon

Probabilistic Methods

Coupling

Strong Stationary Times

Spectrum and Singular Values

General Finite Markov Chains

The Random Walk Case

Lower Bounds

Eigenvalue Bounds Using Paths

Cayley Graphs

The Second Largest Eigenvalue

The Lowest Eigenvalue

Diameter Bounds, Isoperimetry and Expanders

Results Involving Volume Growth Conditions

Moderate Growth

Nilpotent Groups

Nilpotent Groups with many Generators / 7.3：

Representation Theory for Finite Groups

The General Set-up

Abelian Examples

Random Random Walks

Central Measures and Bi-invariant Walks

Characters and Bi-invariance

Random Transposition on the Symmetric Group

Walks Based on Conjugacy Classes of the Symmetric Group

Finite Classical Groups

Fourier Analysis for Non-central Measures / 9.5：

Comparison Techniques

The min-max Characterization of Eigenvalues

Comparing Dirichlet Forms Using Paths

Comparison for Non-symmetric Walks / 10.3：

The Random-Cluster Model / Geoffrey Grimmett

Models of First-Passage Percolation / C. Douglas Howard

Relaxation Times of Markov Chains in Statistical Mechanics and Combinatorial Structures / Fabio Martinelli

Random Walks on Finite Groups / Laurent Saloff-Coste

Index

Introduction / 1：

続きを見る

東工大ブックレビュー

類似資料:

1 図書 Hitting probabilities of single points for processes with stationary independent increments Kesten, Harry, 1931- American Mathematical Society	7 図書 Discrete Markov chains Romanovskiĭ, Vsevolod Ivanovich, 1879-1954, Seneta, E. (Eugene), 1941- Wolters-Noordhoff
2 図書 Probability theory of classical Euclidean optimization problems Yukich, Joseph Springer	8 図書 Markov chains with stationary transition probabilities Chung, Kai Lai, 1917- Springer
3 図書 Probabilistic combinatorics and its applications Bollobás, Béla, Chung, Fan R. K., American Mathematical Society Short Course [on] Probabilistic Combinatorics and its … American Mathematical Society	9 図書 Markov chains with stationary transition probabilities Chung, Kai Lai, 1917- Springer
4 図書 Perplexing problems in probability : festschrift in honor of Harry Kesten (: us ; : sz) Bramson, Maury, 1951-, Kesten, Harry, 1931-, Durrett, Richard, 1951- Birkhauser	10 図書 Further topics on discrete-time Markov control processes Hernández-Lerma, O. (Onésimo), Lasserre, Jean-Bernard, 1953- Springer
5 図書 Percolation theory for mathematicians Kesten, Harry, 1931- Birkhäuser	11 図書 Markov decision processes : discrete stochastic dynamic programming Puterman, Martin L. Wiley
6 図書 Computational probability Grassmann, Winfried K. Kluwer Academic	12 図書 Random walks, Brownian motion and interacting particle systems : a festschrift in honor of Frank Spitzer (: us ; : gw) Kesten, Harry, 1931-, Durrett, Richard, 1951-, Spitzer, Frank, 1926- Birkhäuser