Show simple item record

dc.contributor.authorBernstein, Megan
dc.descriptionPresented as part of the Workshop on Algorithms and Randomness on May 17, 2018 at 4:00 p.m. in the Klaus Advanced Computing Building, Room 1116.en_US
dc.descriptionMegan Bernstein is an Algorithms and Randomness Center postdoctoral fellow at Georgia Tech. Her research is in the fields of probability, random algorithms, and combinatorics. This includes finding Markov chain mixing times, such as for random walks on the symmetric group (also known as card shuffles), using tools from representation theory, algebraic combinatorics, and probability.en_US
dc.descriptionRuntime: 35:05 minutesen_US
dc.description.abstractCutoff is a remarkable property of many Markov chains in which they after number of steps abruptly transition in a smaller order window from an unmixed to a mixed distribution. Most random walks on the symmetric group, also known as card shuffles, are believed to mix with cutoff, but we are far from being able to prove this. Spectral techniques are one of the few known that are strong enough to give cutoff, but diagonalization is difficult for random walks on groups where the generators of the walk are not conjugation invariant. Using a diagonalization by Dieker and Saliola , I will show an upper bound that, together with a lower bound from Subag, gives that cutoff occurs for the random-to-random card shuffle on n cards occurs at 3/4n log n - 1/4n log log n ± cn steps (answering a 2001 conjecture of Diaconis). Includes joint work with Evita Nestoridi.en_US
dc.format.extent35:05 minutes
dc.relation.ispartofseriesWorkshop on Algorithms and Randomness 2018en_US
dc.subjectSpectral techniquesen_US
dc.titleCutoff with window for the random to random shuffleen_US
dc.contributor.corporatenameGeorgia Institute of Technology. Algorithms, Randomness and Complexity Centeren_US
dc.contributor.corporatenameGeorgia Institute of Technology. School of Mathematicsen_US

Files in this item


This item appears in the following Collection(s)

  • ARC Talks and Events [84]
    Distinguished lectures, colloquia, seminars and speakers of interest to the ARC community

Show simple item record