A central limit theorem for a card shuffling problem

Given a positive integer n, consider a permutation of n objects chosen uniformly at random. In this permutation, we collect maximal subsequences consisting of consecutive numbers arranged in ascending order called blocks. Each block is then merged, and after all merges, the elements of this new set are relabeled from 1 to the current number of elements. We continue to permute and merge this new set uniformly at random until only one object is left. In this paper, we investigate the distribution of Xn, the number of permutations needed for this process to end. In particular, we find explicit asymptotic expressions for the mean value E[Xn], the variance Var[Xn], and higher central moments, and show that Xn satisfies a central limit theorem.

Duke Scholars

Author Lin Jiu DKU Faculty