4 ms·

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 t

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.

kkylin 9y ago
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_probability_measures 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 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.
- kkylin 9y ago
  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 https://arxiv.org/abs/0909.4320 .

kkylin 9y ago

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_probability_measures 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 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.

kkylin 9y ago
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 https://arxiv.org/abs/0909.4320 .