A discrete probability problem in card shuffling. Issue 3 (1st February 2016) - Rao, M. Bhaskara; Zhang, Haimeng; Huang, Chunfeng; Cheng, Fu-Chih
Abstract: There are n cards serially numbered from 1 to n . The cards are shuffled and placed in a line one after the other on top of a table with faces up. The numbers on the faces are read from left to right. If there are consecutive numbers in increasing order of magnitude the corresponding cards are merged into one. After the merger, the cards are numbered serially from one to whatever the number of cards we now have. The cards are shuffled and placed in a line one after another on top of the table with faces up. The process continues until we have only one card left. In this paper, we develop a probabilistic recurrence relation approach to obtain the mean, variance, and distribution of the number of shuffles needed. A Markov chain formulation and its properties are discussed in the paper as well.