An absorbing version of the top-to-random shuffle

Lewis, Joel Brewster; Rai, Mehr

doi:10.2140/involve.2024.17.603

Download this article
	For screen
	For printing

Recent Issues

The Journal

About the journal

Ethics and policies

Peer-review process

Submission guidelines

ISSN 1944-4184 (online)

ISSN 1944-4176 (print)

Author index

To appear

Other MSP journals

An absorbing version of the top-to-random shuffle

Joel Brewster Lewis and Mehr Rai

Vol. 17 (2024), No. 4, 603–632

DOI: 10.2140/involve.2024.17.603

Abstract

Consider a randomly shuffled deck of $2 n$ cards with $n$ red cards and $n$ black cards. We study the average number of moves it takes to go from a randomly shuffled deck to a deck that alternates in color by performing the following move: if the top card and the bottom card of the deck differ in color, place the top card at the bottom of the deck; otherwise, insert the top card randomly in the deck. We use tools from combinatorics, probability, and linear algebra to study this process.

Keywords

finite Markov chain, absorbing Markov chain, card shuffling, top-to-random shuffle

Mathematical Subject Classification

Primary: 60C05, 60J10

Secondary: 05A05

Milestones

Received: 16 June 2022

Revised: 2 May 2023

Accepted: 4 May 2023

Published: 2 October 2024

Communicated by Jonathon Peterson

Authors

Joel Brewster Lewis
Department of Mathematics George Washington University Washington, DC United States

Mehr Rai
Department of Mathematics Aalto University FI-00076 Aalto Finland

Vol. 17, No. 4, 2024