The hit-and-run version of top-to-random. (12th September 2022)

• Record Type: Journal Article
• Authors: Boardman, Samuel; Rudolf, Daniel; Saloff-Coste, Laurent
• Is Part Of: Journal of applied probability. Volume 59:Number 3(2022)
• Page Start: 860
• Page End: 879
• Publication Date: 2022-09-12
• Subjects: Markov chain -- card shuffling -- cut-off phenomenon; 60J10 -- 60B10 -- 60B15 -- 60G51; 519.2
• DOI: 10.1017/jpr.2021.96
• Languages: English
• ISSNs: 0021-9002

Abstract

Abstract: We study an example of a hit-and-run random walk on the symmetric group $\mathbf S_n$ . Our starting point is the well-understood top-to-random shuffle. In the hit-and-run version, at each single step, after picking the point of insertion j uniformly at random in $\{1, \ldots, n\}$, the top card is inserted in the j th position k times in a row, where k is uniform in $\{0, 1, \ldots, j-1\}$ . The question is, does this accelerate mixing significantly or not? We show that, in $L^2$ and sup-norm, this accelerates mixing at most by a constant factor (independent of n ). Analyzing this problem in total variation is an interesting open question. We show that, in general, hit-and-run random walks on finite groups have non-negative spectrum.