Jump to ContentJump to Main Navigation
The Nature of Computation$
Users without a subscription are not able to see the full content.

Cristopher Moore and Stephan Mertens

Print publication date: 2011

Print ISBN-13: 9780199233212

Published to Oxford Scholarship Online: December 2013

DOI: 10.1093/acprof:oso/9780199233212.001.0001

Show Summary Details
Page of

PRINTED FROM OXFORD SCHOLARSHIP ONLINE (www.oxfordscholarship.com). (c) Copyright Oxford University Press, 2019. All Rights Reserved. An individual user may print out a PDF of a single chapter of a monograph in OSO for personal use. date: 23 October 2019

Random Walks and Rapid Mixing

Random Walks and Rapid Mixing

Chapter:
(p.563) Chapter 12 Random Walks and Rapid Mixing
Source:
The Nature of Computation
Author(s):

Cristopher Moore

Stephan Mertens

Publisher:
Oxford University Press
DOI:10.1093/acprof:oso/9780199233212.003.0012

Random sampling is a technique for dealing with possible states or solutions having an exponentially large space. The best method of random sampling generally involves a random walk or a Markov chain. A Markov chain requires a number of steps to approach equilibrium, and thus provide a good random sample of the state space. This number of steps is called mixing time, which can be calculated by thinking about how quickly its choices overwhelm the system’s memory of its initial state, the extent to which one part of a system influences another, and how smoothly probability flows from one part of the state space to another. This chapter explores random walks and rapid mixing, first by considering a classic example from physics: a block of iron. It then discusses transition matrices, ergodicity, coupling, spectral gap, and expanders, as well as the role of conductance and the spectral gap in rapid mixing. It concludes by showing that temporal mixing is closely associated with spatial mixing.

Keywords:   random sampling, random walks, Markov chain, equilibrium, mixing time, rapid mixing, coupling, spectral gap, expanders, conductance

Oxford Scholarship Online requires a subscription or purchase to access the full text of books within the service. Public users can however freely search the site and view the abstracts and keywords for each book and chapter.

Please, subscribe or login to access full text content.

If you think you should have access to this title, please contact your librarian.

To troubleshoot, please check our FAQs , and if you can't find the answer there, please contact us .