Counting, Sampling and Integrating

Algorithms and Complexity

By: Mark Jerrum

Write A Review

Paperback | 23 January 2003

At a Glance

Paperback
128 Pages

Dimensions(cm)
24.13 x 17.15 x 1.02

Paperback

$119.75

or 4 interest-free payments of $29.94 with

or

Ships in 5 to 7 business days

These notes had their origin in a postgraduate lecture series I gave at the Eid- genossiche Technische Hochschule (ETH) in Zurich in the Spring of 2000. I am very grateful to my hosts, the Forschungsinstitut fUr Mathematik at ETH, for providing the ideal opportunity to develop and present this material in what I hope is a reasonably coherent manner, and also for encouraging and assisting me to record the proceedings in these lecture notes. The subject of the lecture series was counting (of combinatorial structures) and related topics, viewed from a computational perspective. As we shall see, "related topics" include sampling combinatorial structures (being computationally equivalent to approximate counting via efficient reductions), evaluating partition functions (being weighted counting) and calculating the volume of bodies (being counting in the limit). We shall be inhabiting a different world to the one conjured up by books with titles like Combinatorial Enumeration or Graphical Enumeration. There, the prob- lems are usually parameterised on a single integer parameter n, and the required solutions are closed form or asymptotic estimates obtained using very refined and precise analytical tools.

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 $79.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.

More in Probability & Statistics

Speed

How it Explains the World

Paperback

RRP $36.99

$29.75

20%
OFF

The Maths Book

Big Ideas Simply Explained

Hardcover

RRP $42.99

$32.75

24%
OFF

The Art of Uncertainty

How to Navigate Chance, Ignorance, Risk and Luck

Hardcover

RRP $55.00

$41.75

24%
OFF

Fooled By Randomness

The Hidden Role of Chance in Life and in the Markets

Paperback

RRP $26.99

$22.99

15%
OFF

Understanding Structural Equation Models : Models of Relationships Between Variables - Phillip K. Wood

$22.99

15%
OFF

Sampling Theory and Practice - Casey Murphy

$21.75

13%
OFF

Psychology Statistics For Dummies

For Dummies

Paperback

RRP $49.95

$38.75

22%
OFF

Introduction to Medical Statistics

4th edition

Paperback

RRP $70.95

$62.75

12%
OFF

On the Edge

The Art of Risking Everything

Paperback

RRP $36.99

$29.75

20%
OFF

Statistics without Tears

An Introduction for Non-Mathematicians

Paperback

RRP $26.99

$20.75

23%
OFF

Naked Statistics

Stripping the Dread from the Data

Paperback

RRP $29.95

$22.75

24%
OFF

Hands-On Programming with R

Write Your Own Functions and Simulations

Paperback

RRP $76.00

$39.75

48%
OFF

Calling Bullshit

The Art of Scepticism in a Data-Driven World

Paperback

RRP $26.99

$22.99

15%
OFF

Foreword	p. ix
Two good counting algorithms	p. 1
Spanning trees	p. 1
Perfect matchings in a planar graph	p. 5
#P-completeness	p. 11
The class #P	p. 13
A primal #P-complete problem	p. 15
Computing the permanent is hard on average	p. 21
Sampling and counting	p. 25
Preliminaries	p. 25
Reducing approximate counting to almost uniform sampling	p. 28
Markov chains	p. 30
Coupling and colourings	p. 33
Colourings of a low-degree graph	p. 33
Bounding mixing time using coupling	p. 36
Path coupling	p. 41
Canonical paths and matchings	p. 49
Matchings in a graph	p. 49
Canonical paths	p. 51
Back to matchings	p. 56
Extensions and further applications	p. 62
Continuous time	p. 63
Volume of a convex body	p. 65
A few remarks on Markov chains with continuous state space	p. 67
Invariant measure of the ball walk	p. 68
Mixing rate of the ball walk	p. 72
Proof of the Poincare inequality (Theorem 6.7)	p. 74
Proofs of the geometric lemmas	p. 82
Relaxing the curvature condition	p. 85
Using samples to estimate volume	p. 89
Appendix: a proof of Corollary 6.8	p. 91
Inapproximability	p. 93
Independent sets in a low degree graph	p. 96
Bibliography	p. 105
Table of Contents provided by Rittenhouse. All Rights Reserved.

Counting, Sampling and Integrating

Algorithms and Complexity

At a Glance

Paperback

Shipping

How to return your order

Defective items

You Can Find This Book In

More in Probability & Statistics

Speed

How it Explains the World

The Maths Book

Big Ideas Simply Explained

The Art of Uncertainty

How to Navigate Chance, Ignorance, Risk and Luck

Fooled By Randomness

The Hidden Role of Chance in Life and in the Markets

Understanding Structural Equation Models

Models of Relationships Between Variables

Understanding Structural Equation Models

Models of Relationships Between Variables

The Art of Statistics

Learning from Data

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

Everything Is Predictable

How Bayes' Remarkable Theorem Explains the World

Psychology Statistics For Dummies

For Dummies

Introduction to Medical Statistics

4th edition

On the Edge

The Art of Risking Everything

Statistics without Tears

An Introduction for Non-Mathematicians

Naked Statistics

Stripping the Dread from the Data

Hands-On Programming with R

Write Your Own Functions and Simulations

Calling Bullshit

The Art of Scepticism in a Data-Driven World

This product is categorised by