Overview

This study discusses two problems of fine pedigree - counting and generation - both of which are of fundamental importance to discrete mathematics and probability. When asking questions like ""How many are there?"" and ""What does it look like on average?"" of families of combinatorial structures, answers are often difficult to find - we can be blocked by seemingly intractable algorithms. This text shows how to get around the problem of intractability with the Markov chain Monte Carlo method, as well as highlighting the method's natural limits. It uses the technique of coupling before introducing ""path coupling"", a technique which radically simplifies and improves upon other methods in the area.

Full Product Details

Author:   Russ Bubley
Publisher:   Springer London Ltd
Imprint:   Springer London Ltd
Edition:   2001 ed.
Dimensions:   Width: 16.20cm , Height: 1.70cm , Length: 24.10cm
Weight:   0.405kg
ISBN:  

9781852333256

ISBN 10:   1852333251
Pages:   152
Publication Date:   13 November 2000
Audience:   College/higher education ,  Professional and scholarly ,  Undergraduate ,  Postgraduate, Research & Scholarly
Format:   Hardback
Publisher's Status:   Out of Print
Availability:   Out of stock  

Table of Contents

1 Mathematical Background.- 1.1 Computational Complexity.- 1.1.1 Introduction.- 1.1.2 Notation for Asymptotics: ?, ?, and ?.- 1.1.3 Complexity Classes.- 1.1.4 Oracles, Reductions, and Hardness.- 1.1.5 More Complexity Classes.- 1.1.6 Conclusion.- 1.1.7 Some Common Problems in Complexity Theory.- 1.2 Probability.- 1.3 Markov Chains.- 1.4 Graph Theory.- 1.4.1 Tutte-Groethendieck Polynomial.- 1.4.2 Hypergraphs.- 2 Techniques for Sampling and Approximate Sampling.- 2.1 Introduction.- 2.1.1 Definitions.- 2.2 Direct Sampling.- 2.2.1 Monte Carlo Method: Rejection Sampling.- 2.2.2 Karp-Luby Technique.- 2.3 Markov Chain Method.- 2.3.1 Coupling.- 2.3.1.1 Maximal couplings.- 2.3.2 Dobrushin's Uniqueness Criterion.- 2.3.3 Canonical Paths.- 2.3.4 Conductance.- 2.3.5 Comparison Methods.- 2.3.6 Other Methods.- 2.3.6.1 Poincare-type inequalities.- 2.3.6.2 Logarithmic Sobolev inequalities.- 2.3.7 Coupling from the Past.- 3 Approximate Counting.- 3.1 Parsimonious Reductions.- 3.2 Counting Directly.- 3.2.1 Direct Sampling.- 3.2.2 Karp-Luby Technique.- 3.3 Counting and Sampling.- 3.4 The Markov Chain Monte Carlo Method.- 4 Applications: Coupling.- 4.1 Hypergraph Colourings.- 4.1.1 Introduction.- 4.1.1.1 Notation and preliminaries.- 4.1.2 Approximate Sampling.- 4.1.2.1 Computing the permutation.- 4.1.2.2 Rapidity of coupling.- 4.1.2.3 Two sufficient conditions.- A condition of k > ?1+?3.- A condition of k > 2?2.- 4.1.3 Almost uniform sampling for k=2?2.- 4.1.3 The Approximation Scheme.- 4.1.4 Conclusions.- 4.2 Sink-Free Graph Orientations and Twice-Sat.- 4.2.1 Introduction.- 4.2.1.1 Notation and preliminaries.- 4.2.1.2 Equivalence of Twice-Sat and SFO.- 4.2.2 Decision and Construction.- 4.2.3 Exact Counting.- 4.2.3.1 Self-reducibility.- 4.2.3.2 Relationship to counting independent sets.- 4.2.3.3 #P-completeness of #SFO.- 4.2.4 Approximate Sampling.- 4.2.5 The Approximation Scheme.- 4.2.6 Conclusions.- 4.3 Log-Concave Sampling, and the Volume of a Convex Body.- 4.3.1 Introduction.- 4.3.2 Background and Preliminaries.- 4.3.2.1 Convex bodies and gauge functions.- 4.3.2.2 Sampling equivalence.- 4.3.2.3 Modifying FK.- 4.3.2.4 Metropolis random walks.- 4.3.2.5 The random walk.- 4.3.2.6 Coupling.- 4.3.2.7 Technical results.- 4.3.3 Analysis of the Random Walk.- 4.3.3.1 Boundedness of the walk.- 4.3.3.2 Bringing the random walks close.- 4.3.3.3 Making the random walks meet.- 4.3.4 Improvements.- 4.3.4.1 A faster simulation of the random walk.- 4.3.4.2 An even faster simulation.- 4.3.5 Conclusions.- Intermezzo: Path Coupling.- 5 Applications: Path Coupling.- 5.1 Introduction.- 5.2 Twice-Sat Revisited.- 5.3 Sink- and Source-Free Graph Orientations.- 5.3.1 Introduction.- 5.3.2 Decision and Construction.- 5.3.3 Exact Counting.- 5.3.3.1 Self-reducibility.- 5.3.3.2 #P-completeness of #SSFO.- 5.3.4 Approximate Counting and Sampling.- 5.4 Totally Edge Cyclic Orientations.- 5.4.1 Approximate Sampling.- 5.5 Independent Sets: The Conserved Hard-Core Model.- 5.5.1 #P-Completeness of Exact Counting.- 5.5.2 Approximate Sampling.- 5.6 Independent Sets: The Non-Conserved Hard-Core Model.- 5.6.1 Approximate Counting.- 5.7 Linear Extensions of a Partial Order.- 5.7.1 Introduction.- 5.7.2 Notation and Preliminaries.- 5.7.3 The Coupling.- 5.7.4 Lower Bounds and Related Chains.- 5.7.5 Conclusions.- 5.8 Graph Colouring.- 5.9 The Extended Potts Framework.- 5.10 Graph Colouring Revisited.- 5.10.1 #P-Completeness.- 5.10.2 Approximate Sampling.- 6 Directions for Future Work.- 6.1 Breaking Thresholds.- 6.2 Beyond Self-Reducibility.- 6.3 Mixed Methods for Approximate Counting.- 6.4 Faster Reductions from Approximate Counting to Approximate Sampling.- 6.5 Anti-ferromagnetic Models.- 6.6 Log-Concave Sampling via Path Coupling.- Appendices.- A An Application of Dobrushin's Uniqueness Criterion.- B A Hierarchy of #SAT Restrictions.- B.1 Introduction.- B.2 A Summary of Known Results.- B.2.1 Easy Exact Counting.- B.2.2 Hard Exact Counting.- B.2.3 Easy Approximate Counting.- B.2.4 Hard Approximate Counting.- B.3 Summary and Conclusions.- C Equivalence of Transposition Distance to Spearman's Footrule.

Reviews

Author Information

Tab Content 6

Author Website:  

Countries Available

All regions