Pith. sign in

REVIEW 1 cited by

Cutoff for non-negatively curved Markov chains

Not yet reviewed by Pith; the record is open.

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 2102.05597 v2 pith:2HN22543 submitted 2021-02-10 math.PR math.CO

classification math.PRmath.CO
keywords cutoffchainsmarkovabeliancayleyconditionemphparticular
verification ladder T0 review T1 audit T2 compute T3 formal

Signed reviews

No signed human review yet.

0 comments
read the original abstract

Discovered in the context of card shuffling by Aldous, Diaconis and Shahshahani, the cutoff phenomenon has since then been established in a variety of Markov chains. However, proving cutoff remains a delicate affair, which requires a detailed knowledge of the chain. Identifying the general mechanisms underlying this phase transition -- without having to pinpoint its precise location -- remains one of the most fundamental open problems in the area of mixing times. In the present paper, we make a step in this direction by establishing cutoff for Markov chains with non-negative curvature, under a suitably refined product condition. The result applies, in particular, to random walks on abelian Cayley expanders satisfying a mild degree condition, hence in particular to \emph{almost all} abelian Cayley graphs. Our proof relies on a quantitative \emph{entropic concentration principle}, which we believe to lie behind all cutoff phenomena.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Some inequalities for reversible Markov chains and branching random walks via spectral optimization

    math.PR 2019-08 accept novelty 8.0 of 10

    For reversible finite Markov chains, the L-infinity mixing time is at most trel log(e thit / trel), so the mixing time is comparable to the maximal hitting time exactly when the spectral gap times the hitting time rem...

Pith tools