2000 Mathematics Subject Classification. Primary 60J10, 60J27, 60B15, 60C05, 65C05, 60K35, 68W20, 68U20, 82C22. FRONT COVER: The three color figures on the front cover are courtesy of David B. Wilson. The figure on the left is a uniformly random lozenge tiling of a hexagon (see Section 22.2), the figure in the middle is a random sample of an Ising model at its critical temperature (see Sections 3.3.5 and 22.2) with mixed boundary conditions, and the figure on the right is a uniformly random 3-coloring (see Section 3.1) with certain boundary conditions. For additional information and updates on this book, visit www.ams.org/bookpages/mbk-58 Library of Congress Cataloging-in-Publication Data Levin, David A., 1971– Markov chains and mixing times : with a chapter on coupling from the past by James G. Propp and David B. Wilson / David A. Levin, Yuval Peres, Elizabeth L. Wilmer. p. cm. Includes bibliographical references and index. ISBN 978-0-8218-4739-8 (alk. paper) 1. Markov processes. I. Peres, Y. (Yuval) II. Wilmer, Elizabeth L. (Elizabeth Lee), 1970– III. Title. QA274.7.L48 2008 519.2 33—dc22 2008031811 Copying and reprinting. Individual readers of this publication, and nonprofit libraries acting for them, are permitted to make fair use of the material, such as to copy a chapter for use in teaching or research. Permission is granted to quote brief passages from this publication in reviews, provided the customary acknowledgment of the source is given. Republication, systematic copying, or multiple reproduction of any material in this publication is permitted only under license from the American Mathematical Society. Requests for such permission should be addressed to the Acquisitions Department, American Mathematical Society, 201 Charles Street, Providence, Rhode Island 02904-2294, USA. Requests can also be made by e-mail to reprint-permission@ams.org. c 2009 by the authors. All rights reserved. Printed in the United States of America. The paper used in this book is acid-free and falls within the guidelines established to ensure permanence and durability. Visit the AMS home page at http://www.ams.org/ 10 9 8 7 6 5 4 3 2 1 14 13 12 11 10 09
Previous Page Next Page