All

Card Shuffling with Adjacent Swaps and Fill's Gap Problem

  • Speaker: Gary R. W. Greaves(南京工业大学)

  • Time: Apr 23, 2026, 10:00-11:00

  • Location: M1001, College of Science Building,Tencent Meeting ID: 637 218 483

Abstract
Certain biased card shuffles, which have been extensively studied in probability and combinatorics, can be modelled by a natural Markov chain on the symmetric group in which neighbouring elements are swapped according to prescribed probabilities. The spectral gap of the transition matrix determines how quickly the Markov chain converges to equilibrium.
In this talk, I will present a sharp lower bound on the spectral gap for abroad class of such Markov chains and explain how this resolves a longstanding conjecture of Fill. The key idea is to decompose the  transition matrix into an average of elementary transition matrices that can be interpreted as orthogonal projections in a suitable inner-product space. Finally, I will discuss results on the multiplicity of the second-largest eigenvalue in the extremal case where the spectral gap is minimised.