xiv PREFACE In 1991 one of us (Y. Peres) arrived as a postdoc at Yale and visited Shizuo Kakutani, whose rather large oﬃce was full of books and papers, with bookcases and boxes from floor to ceiling. A narrow path led from the door to Kakutani’s desk, which was also overflowing with papers. Kakutani admitted that he sometimes had diﬃculty locating particular papers, but he proudly explained that he had found a way to solve the problem. He would make four or five copies of any really interesting paper and put them in different corners of the oﬃce. When searching, he would be sure to find at least one of the copies. . . . Cross-references in the text and the Index should help you track earlier occur- rences of an example. You may also find the chapter dependency diagrams below useful. We have included brief accounts of some background material in Appendix A. These are intended primarily to set terminology and notation, and we hope you will consult suitable textbooks for unfamiliar material. Be aware that we occasionally write representing a real number when an integer is required (see, e.g., the ( n δk )symbols ’s in the proof of Proposition 13.31). We hope the reader will realize that this omission of floor or ceiling brackets (and the details of analyzing the resulting perturbations) is in her or his best interest as much as it is in ours. For the Instructor The prerequisites this book demands are a first course in probability, linear algebra, and, inevitably, a certain degree of mathematical maturity. When intro- ducing material which is standard in other undergraduate courses—e.g., groups—we provide definitions, but often hope the reader has some prior experience with the concepts. In Part I, we have worked hard to keep the material accessible and engaging for students. (Starred sections are more sophisticated and are not required for what follows immediately they can be omitted.) Here are the dependencies among the chapters of Part I: $* #' !''! ,"%!' (' #!) ,# $)%!# ( (($#"' $+ $)#' ).# (+$ ' ((# "' $* "' #*!)' Chapters 1 through 7, shown in gray, form the core material, but there are several ways to proceed afterwards. Chapter 8 on shuffling gives an early rich application but is not required for the rest of Part I. A course with a probabilistic focus might cover Chapters 9, 10, and 11. To emphasize spectral methods and combinatorics, cover Chapters 8 and 12 and perhaps continue on to Chapters 13 and 17.

Purchased from American Mathematical Society for the exclusive use of nofirst nolast (email unknown) Copyright 2009 American Mathematical Society. Duplication prohibited. Please report unauthorized use to cust-serv@ams.org. Thank You! Your purchase supports the AMS' mission, programs, and services for the mathematical community.