A central limit theorem for a card shuffling problem

22.10.2024 15:00 - 16:30

Shane Chern (Universität Wien)

Abstract: Given a positive integer $n$, consider a random permutation $\tau$ of the set $\{1,2,$ $\ldots, n\}$. In $\tau$, we look for sequences of consecutive integers that appear in adjacent positions: a maximal such a sequence is called a block. Each block in $\tau$ is merged, and after all the merges, the elements of this new set are relabeled from $1$ to the current number of elements. We continue to randomly permute and merge this new set until only one integer is left. In this talk, I will investigate the asymptotic behavior of $X_n$, the number of permutations needed for this process to end. In particular, I will display an explicit asymptotic expression for each of the mean value $\mathbf{E}[X_n]$ and the variance $\mathbf{Var}[X_n]$ as well as for every higher central moment, and show that $X_n$ satisfies a central limit theorem. This is joint work with Lin Jiu and Italo Simonelli.

Organiser:
I. Fischer (U Wien), M. Schlosser (U Wien)
Location:

SR 09, 2. OG, OMP 1