Report icon

Report

A Numerical Analyst Looks at the "Cutoff Phenomenon" in Card Shuffling and Other Markov Chains

Abstract:

Diaconis and others have shown that certain Markov chains exhibit a "cutoff phenomenon" in which, after an initial period of seemingly little progress, convergence to the steady state occurs suddenly. Since Markov chains are just powers of matrices, how can such effects be explained in the language of applied linear algebra? We attempt to do this, focusing on two examples: random walk on a hypercube, which is essentially the same as the problem of Ehrenfest urns, and the celebrated case of ri...

Expand abstract

Actions


Access Document


Files:

Authors


Gudbjorn F. Jonsson More by this author
Lloyd N. Trefethen More by this author
Publication date:
1997
URN:
uuid:da57cc8f-538f-4cfd-8486-ca61b69489f5
Local pid:
oai:eprints.maths.ox.ac.uk:1313

Terms of use


Metrics



If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP