CONTENTS vii Chapter 10. Hitting Times 127 10.1. Definition 127 10.2. Random Target Times 128 10.3. Commute Time 130 10.4. Hitting Times for the Torus 133 10.5. Bounding Mixing Times via Hitting Times 134 10.6. Mixing for the Walk on Two Glued Graphs 138 Exercises 139 Notes 141 Chapter 11. Cover Times 143 11.1. Cover Times 143 11.2. The Matthews Method 143 11.3. Applications of the Matthews Method 147 Exercises 151 Notes 152 Chapter 12. Eigenvalues 153 12.1. The Spectral Representation of a Reversible Transition Matrix 153 12.2. The Relaxation Time 154 12.3. Eigenvalues and Eigenfunctions of Some Simple Random Walks 156 12.4. Product Chains 160 12.5. An 2 Bound 163 12.6. Time Averages 165 Exercises 167 Notes 168 Part II: The Plot Thickens 169 Chapter 13. Eigenfunctions and Comparison of Chains 171 13.1. Bounds on Spectral Gap via Contractions 171 13.2. Wilson’s Method for Lower Bounds 172 13.3. The Dirichlet Form and the Bottleneck Ratio 175 13.4. Simple Comparison of Markov Chains 179 13.5. The Path Method 182 13.6. Expander Graphs* 185 Exercises 187 Notes 187 Chapter 14. The Transportation Metric and Path Coupling 189 14.1. The Transportation Metric 189 14.2. Path Coupling 191 14.3. Fast Mixing for Colorings 193 14.4. Approximate Counting 195 Exercises 198 Notes 199 Chapter 15. The Ising Model 201 15.1. Fast Mixing at High Temperature 201 15.2. The Complete Graph 203
Previous Page Next Page