Hacker News Reader

Comment by symmetricsaurus | Hacker News Reader

About this cutoff. I guess that it is an analogue to the phase transition we see in for example the Ising model (this example was given in the article).

This transition is due to a change in temperature, i. e. the chance of flipping a spin into a non-favorable configuration. How does this relate to the number of shuffles in a deck?

There is no equivalent of a temperature here from what I can see.

View on HN

The "cut-off" phenomenon is dynamical, not involving changes in parameters. The idea is that if you start a (irreducible aperiodic) Markov chain with initial condition drawn from a non-stationary distribution, and you compute the distance d(n) between the distribution at step n and the stationary distribution (where distance usually means "total variation distance" https://en.wikipedia.org/wiki/Total_variation_distance_of_pr...) then d(n) can drop off sharply as a function of n, rather than exponentially for all n as one might expect.

Here is one of Persi's papers on this topic:

http://www.pnas.org/content/93/4/1659.full.pdf

There is also a chapter in Trefethen and Embree's (very intersting) book "Spectra and Pseudospectra" on the topic, and IIRC it had a nice explanation of the cutoff phenomenon. Offhand I don't know a paper I can point to, but perhaps someone on the list does.

I don't mean to imply d(n) does not drop off exponentially (as it should), only that it has a sharp drop-off before the exponential scaling sets in, rather than a steady exponential all the way.

Also, if you equip an Ising model with Glauber dynamics, the resulting Markov chain does exhibit a cutoff phenonmenon. See, e.g., https://arxiv.org/abs/0909.4320 .

Reply on news.ycombinator.com