#  Top to random shuffles on colored permutations

Fumihiko Nakano  Mathematical Institute, Tohoku University, Sendai 980-8578,
Japan e-mail<EMAIL_ADDRESS>Taizo Sadahiro Department of
Computer Science, Tsuda University, 2-1-1, Tsuda, Kodaira City, 187-8577,
Tokyo, Japan. e-mail<EMAIL_ADDRESS>Tetsuya Sakurai  Mathematical
Institute, Tohoku University, Sendai 980-8578, Japan e-mail :
<EMAIL_ADDRESS>
###### Abstract

A deck of $n$ cards are shuffled by repeatedly taking off the top card,
flipping it with probability $1/2$, and inserting it back into the deck at a
random position. This process can be considered as a Markov chain on the group
$B_{n}$ of signed permutations. We show that the eigenvalues of the transition
probability matrix are $0,1/n,2/n,\ldots,(n-1)/n,1$ and the multiplicity of
the eigenvalue $i/n$ is equal to the number of the signed permutation having
exactly $i$ fixed points. We show the similar results also for the colored
permutations. Further, we show that the mixing time of this Markov chain is
$n\log n$, same as the ordinary ’top-to-random’ shuffles without flipping the
cards. The cut-off is also analyzed by using the asymptotic behavior of the
Stirling numbers of the second kind.

##  1 Introduction and the statement of the main result

The top-to-random shuffle of cards, which is a Markov chain on the symmetric
group, has long been studied [1, 5]. By modifying the arguments in [5] and
[7], this paper studies the generalized top-to-random shuffling defined on the
colored permutation group. For example, when the number of the ’colors’ is
two, the Markov chain can be described as follows: We take the top card of the
deck of $n$ cards and before inserting it back into the deck at the random
position, we flip the card with probability $1/2$. After repeating this
procedure, we have a random configuration of the cards which can be regarded
as an element of the hyperoctahedral group $B_{n}$. This generalization is
similar to those of the riffle shuffle [3], [9]. Our main aim in this paper is
to show a closed formula describing the probability distribution after
shuffling $k$-times in terms of (generalized) Stirling numbers, the explicit
form of the eigenvalues of the transition probability matrix, and the mixing
time and cut-off of the Markov chain. By a colored permutation group, we mean
the wreath product of a cyclic group and a symmetric group. Throughout, the
symmetric group of degree $n$ is denoted by $\mathfrak{S}_{n}$, and the cyclic
group of order $p$ is denoted by $C_{p}$. For positive integers $p$ and $n$,
the wreath product $C_{p}\wr{\mathfrak{S}}_{n}$ is denoted by $G_{n,p}$. That
is, the colored permutation group $G_{n,p}$ is defined by

$G_{n,p}=\left\\{(s,\sigma)\,|\,s=(s_{1},\ldots,s_{n})\in
C_{p}^{n},\sigma\in{\mathfrak{S}}_{n}\right\\}$

equipped with the following multiplication rule,

$(t,\tau)(s,\sigma)=(\sigma t+s,\tau\sigma)$

for $(t,\tau)$ and $(s,\sigma)\in G_{n,p}$, where

$\sigma t=(t_{\sigma(1)},t_{\sigma(2)},\ldots,t_{\sigma(n)}).$

For example, let $s=(0,\ldots,0,\stackrel{{\scriptstyle\stackrel{{\scriptstyle
i}}{{\vee}}}}{{k}},0,\ldots,0)$ and $\sigma=(1,2,\ldots,i)$ be a cyclic
permutatiion in ${\mathfrak{S}}_{n}$. Then,

$(t,\tau)(s,\sigma)=((t_{2},t_{3},\ldots,t_{i},t_{1}+k,t_{i+1},\ldots,t_{n}),(\tau(2),\tau(3),\ldots,\tau(i),\tau(1),\tau(i+1),\ldots,\tau(n))).$

We interpret the multiplication by this special element $S_{i,k}=(s,\sigma)$
as follows: We have a deck of $n$ cards each numbered
$\tau(1),\tau(2),\ldots,\tau(n)$ from the top to the bottom. We take the top
card and change the color of the card to $t_{1}+k$ and insert it into the deck
at the $i$-th place from the top. To introduce the ’shuffle’ we regard
$(s,\sigma)\in G_{n,p}$ as a sequence of the pairs $(s_{i},\sigma(i))\in
C_{p}\times[n]$, so that $(s,\sigma)$ is a word over the alphabet
$C_{p}\times[n]$. Especially for $p\leq 3$, we express $(0,k)\in
C_{p}\times[n]$ simply by $k$, $(1,k)\in C_{p}\times[n]$ by $\bar{k}$, and
$(2,k)$ by $\bar{\bar{k}}$. For example, by using this notation,
$((0,1,0,2),4123)\in G_{4,3}$ can be simply expressed as
$4\bar{1}2\bar{\bar{3}}$. Thus elements of $G_{n,p}$ can be considered as
words over the alphabet $C_{p}\times[n]$, on which we can use the shuffle
operator $\mathbin{\mathchoice{\kern 0.0pt\hbox to0.0pt{\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox to0.0pt{\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}}$. Define the word $W_{k,n}$
by

$W_{k,n}:=(0,k+1)(0,k+2)\cdots(0,n)\in(C_{p}\times[n])^{n-k}.$

Then an element ${\mathbf{B}}_{k}$ of the group algebra ${\mathbb{Q}}G_{n,p}$
is defined by

${\mathbf{B}}_{k}:=\begin{cases}id&(k=0)\\\ \sum_{\alpha\in
G_{k,p}}\alpha\mathbin{\mathchoice{\kern 0.0pt\hbox to0.0pt{\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox to0.0pt{\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}}W_{k,n},&(1\leq k\leq
n-1)\\\ \sum_{\alpha\in G_{n,p}}\alpha&(k=n)\end{cases}$

In particular, we have

${\mathbf{B}}_{1}=(0,1)\mathbin{\mathchoice{\kern 0.0pt\hbox to0.0pt{\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox to0.0pt{\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern
0.0pt}}W_{1,n}+(1,1)\mathbin{\mathchoice{\kern 0.0pt\hbox to0.0pt{\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox to0.0pt{\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern
0.0pt}}W_{1,n}+\cdots+(p-1,1)\mathbin{\mathchoice{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}}W_{1,n}.$

For example, when $n=3$ and $p=2$, we have,

${\mathbf{B}}_{1}=1\mathbin{\mathchoice{\kern 0.0pt\hbox to0.0pt{\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox to0.0pt{\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern
0.0pt}}23+\bar{1}\mathbin{\mathchoice{\kern 0.0pt\hbox to0.0pt{\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox to0.0pt{\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern
0.0pt}}23=123+213+231+\bar{1}23+2\bar{1}3+23\bar{1}.$

Therefore $\dfrac{1}{np}{\bf B}_{1}$ can be regarded as a probability
distribution over $G_{n,p}$, which we call the top to random shuffle over
$G_{n,p}$. When $p=1$, the powers of $\left(\dfrac{1}{np}{\bf
B}_{1}\right)^{k}$ exhibit very interesting properties and have been studied
extensively [5]. The main purpose of this paper is to consider the case for
general $p$ : (i) to give a precise description of the distribution of the
eigenvalues of the left regular representation of ${\bf B}_{1}$, and (ii) to
derive a sharp estimate on the distance between the distribution of
$\left(\dfrac{1}{np}{\bf B}_{1}\right)^{k}$ and the stationary distribution,
and show that it exhibits the cut-off phenomenon. To state our first main
result we need to define the fixed points of a colored permutation. An element
$(s,\sigma)\in G_{n,p}$ has a fixed point at $i$ if $s_{i}=0$ and
$\sigma(i)=i$. For example $4\bar{1}2\bar{\bar{3}}\in G_{4,3}$ has no fixed
point and $1\bar{2}35\bar{\bar{4}}$ has two fixed points at $1$ and $3$. A
dearrangement in $G_{n,p}$ is a colored permutation having no fixed points. We
denote the number of dearrangement in $G_{n,p}$ by $D_{n,p}$, which is
expressed by a closed form given later. Therefore, the number of colored
permutations in $G_{n,p}$ having exactly $i$ fixed points is equal to
${n\choose i}D_{n-i,p}$.

###### Theorem 1.1

Let $L:G_{n,p}\rightarrow{\rm GL}(L^{2}(G_{n,p}))$ be the left regular
representation of $G_{n,p}$. Then the eigenvalues of $L({\mathbf{B}}_{1})$ are
$0,p,2p,\cdots,np$. The multiplicity of the eigenvalue $ip$ is equal to the
number of colored permutations having exactly $i$ fixed points.

Remark
(1) Let $P_{n,p}$ be the transition probability matrix of the Markov chain
generated by the top to random shuffle. Then the eigenvalues of $P_{n,p}$ are
given by $(ip)/(np)=i/n$, $i=0,1,\cdots,n$.
(2) If $p=1$, $P_{n,1}$ does not have $(n-1)/n$ as an eigenvalue because of
$D_{n-(n-1),1}=0$. It is not the case for $p\geq 2$, since $D_{n-(n-1),p}\neq
0$ for $p\geq 2$.
(3) For a generalized riffle shuffle (i.e., the riffle shuffle on $G_{n,p}$),
the multiplicity of eigenvalues are equal to the Stirling-Frobenius cycle
number [10].

Example
When $n=3$ and $p=2$, we have $48$ elements in $G_{n,p}$. The left regular
representation of ${\mathbf{B}}_{1}$ is

$\begin{array}[]{rrr}123\\\ 1\bar{2}\bar{3}\\\ \bar{1}2\bar{3}\\\
\bar{1}\bar{2}3\\\ 231\\\ 2\bar{3}\bar{1}\\\ \bar{2}3\bar{1}\\\
\bar{2}\bar{3}1\\\ 312\\\ 3\bar{1}\bar{2}\\\ \bar{3}1\bar{2}\\\
\bar{3}\bar{1}2\\\ 213\\\ \bar{2}1\bar{3}\\\ 2\bar{1}\bar{3}\\\
\bar{2}\bar{1}3\\\ 321\\\ \bar{3}2\bar{1}\\\ 3\bar{2}\bar{1}\\\
\bar{3}\bar{2}1\\\ 132\\\ \bar{1}3\bar{2}\\\ 1\bar{3}\bar{2}\\\
\bar{1}\bar{3}2\\\ 12\bar{3}\\\ 1\bar{2}3\\\ \bar{1}23\\\
\bar{1}\bar{2}\bar{3}\\\ 23\bar{1}\\\ 2\bar{3}1\\\ \bar{2}31\\\
\bar{2}\bar{3}\bar{1}\\\ 31\bar{2}\\\ 3\bar{1}2\\\ \bar{3}12\\\
\bar{3}\bar{1}\bar{2}\\\ 21\bar{3}\\\ \bar{2}13\\\ 2\bar{1}3\\\
\bar{2}\bar{1}\bar{3}\\\ 32\bar{1}\\\ \bar{3}21\\\ 3\bar{2}1\\\
\bar{3}\bar{2}\bar{1}\\\ 13\bar{2}\\\ \bar{1}32\\\ 1\bar{3}2\\\
\bar{1}\bar{3}\bar{2}\end{array}\left(\begin{array}[]{rrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrr}1&0&0&0&1&0&0&0&0&0&0&0&1&0&0&0&0&0&0&0&0&0&0&0&0&0&1&0&1&0&0&0&0&0&0&0&0&0&1&0&0&0&0&0&0&0&0&0\\\
0&1&0&0&0&1&0&0&0&0&0&0&0&0&1&0&0&0&0&0&0&0&0&0&0&0&0&1&0&1&0&0&0&0&0&0&1&0&0&0&0&0&0&0&0&0&0&0\\\
0&0&1&0&0&0&1&0&0&0&0&0&0&1&0&0&0&0&0&0&0&0&0&0&1&0&0&0&0&0&1&0&0&0&0&0&0&0&0&1&0&0&0&0&0&0&0&0\\\
0&0&0&1&0&0&0&1&0&0&0&0&0&0&0&1&0&0&0&0&0&0&0&0&0&1&0&0&0&0&0&1&0&0&0&0&0&1&0&0&0&0&0&0&0&0&0&0\\\
0&0&0&0&1&0&0&0&1&0&0&0&0&0&0&0&0&0&0&0&1&0&0&0&0&0&0&0&1&0&0&0&0&1&0&0&0&0&0&0&0&0&0&0&0&1&0&0\\\
0&0&0&0&0&1&0&0&0&1&0&0&0&0&0&0&0&0&0&0&0&0&1&0&0&0&0&0&0&1&0&0&1&0&0&0&0&0&0&0&0&0&0&0&0&0&0&1\\\
0&0&0&0&0&0&1&0&0&0&1&0&0&0&0&0&0&0&0&0&0&1&0&0&0&0&0&0&0&0&1&0&0&0&0&1&0&0&0&0&0&0&0&0&1&0&0&0\\\
0&0&0&0&0&0&0&1&0&0&0&1&0&0&0&0&0&0&0&0&0&0&0&1&0&0&0&0&0&0&0&1&0&0&1&0&0&0&0&0&0&0&0&0&0&0&1&0\\\
1&0&0&0&0&0&0&0&1&0&0&0&0&0&0&0&1&0&0&0&0&0&0&0&0&0&1&0&0&0&0&0&0&1&0&0&0&0&0&0&1&0&0&0&0&0&0&0\\\
0&1&0&0&0&0&0&0&0&1&0&0&0&0&0&0&0&0&1&0&0&0&0&0&0&0&0&1&0&0&0&0&1&0&0&0&0&0&0&0&0&0&1&0&0&0&0&0\\\
0&0&1&0&0&0&0&0&0&0&1&0&0&0&0&0&0&1&0&0&0&0&0&0&1&0&0&0&0&0&0&0&0&0&0&1&0&0&0&0&0&1&0&0&0&0&0&0\\\
0&0&0&1&0&0&0&0&0&0&0&1&0&0&0&0&0&0&0&1&0&0&0&0&0&1&0&0&0&0&0&0&0&0&1&0&0&0&0&0&0&0&0&1&0&0&0&0\\\
1&0&0&0&0&0&0&0&0&0&0&0&1&0&0&0&1&0&0&0&0&0&0&0&0&0&1&0&0&0&0&0&0&0&0&0&0&0&1&0&1&0&0&0&0&0&0&0\\\
0&0&1&0&0&0&0&0&0&0&0&0&0&1&0&0&0&1&0&0&0&0&0&0&1&0&0&0&0&0&0&0&0&0&0&0&0&0&0&1&0&1&0&0&0&0&0&0\\\
0&1&0&0&0&0&0&0&0&0&0&0&0&0&1&0&0&0&1&0&0&0&0&0&0&0&0&1&0&0&0&0&0&0&0&0&1&0&0&0&0&0&1&0&0&0&0&0\\\
0&0&0&1&0&0&0&0&0&0&0&0&0&0&0&1&0&0&0&1&0&0&0&0&0&1&0&0&0&0&0&0&0&0&0&0&0&1&0&0&0&0&0&1&0&0&0&0\\\
0&0&0&0&0&0&0&0&1&0&0&0&0&0&0&0&1&0&0&0&1&0&0&0&0&0&0&0&0&0&0&0&0&1&0&0&0&0&0&0&1&0&0&0&0&1&0&0\\\
0&0&0&0&0&0&0&0&0&0&1&0&0&0&0&0&0&1&0&0&0&1&0&0&0&0&0&0&0&0&0&0&0&0&0&1&0&0&0&0&0&1&0&0&1&0&0&0\\\
0&0&0&0&0&0&0&0&0&1&0&0&0&0&0&0&0&0&1&0&0&0&1&0&0&0&0&0&0&0&0&0&1&0&0&0&0&0&0&0&0&0&1&0&0&0&0&1\\\
0&0&0&0&0&0&0&0&0&0&0&1&0&0&0&0&0&0&0&1&0&0&0&1&0&0&0&0&0&0&0&0&0&0&1&0&0&0&0&0&0&0&0&1&0&0&1&0\\\
0&0&0&0&1&0&0&0&0&0&0&0&1&0&0&0&0&0&0&0&1&0&0&0&0&0&0&0&1&0&0&0&0&0&0&0&0&0&1&0&0&0&0&0&0&1&0&0\\\
0&0&0&0&0&0&1&0&0&0&0&0&0&1&0&0&0&0&0&0&0&1&0&0&0&0&0&0&0&0&1&0&0&0&0&0&0&0&0&1&0&0&0&0&1&0&0&0\\\
0&0&0&0&0&1&0&0&0&0&0&0&0&0&1&0&0&0&0&0&0&0&1&0&0&0&0&0&0&1&0&0&0&0&0&0&1&0&0&0&0&0&0&0&0&0&0&1\\\
0&0&0&0&0&0&0&1&0&0&0&0&0&0&0&1&0&0&0&0&0&0&0&1&0&0&0&0&0&0&0&1&0&0&0&0&0&1&0&0&0&0&0&0&0&0&1&0\\\
0&0&1&0&1&0&0&0&0&0&0&0&0&0&1&0&0&0&0&0&0&0&0&0&1&0&0&0&1&0&0&0&0&0&0&0&1&0&0&0&0&0&0&0&0&0&0&0\\\
0&0&0&1&0&1&0&0&0&0&0&0&1&0&0&0&0&0&0&0&0&0&0&0&0&1&0&0&0&1&0&0&0&0&0&0&0&0&1&0&0&0&0&0&0&0&0&0\\\
1&0&0&0&0&0&1&0&0&0&0&0&0&0&0&1&0&0&0&0&0&0&0&0&0&0&1&0&0&0&1&0&0&0&0&0&0&1&0&0&0&0&0&0&0&0&0&0\\\
0&1&0&0&0&0&0&1&0&0&0&0&0&1&0&0&0&0&0&0&0&0&0&0&0&0&0&1&0&0&0&1&0&0&0&0&0&0&0&1&0&0&0&0&0&0&0&0\\\
0&0&0&0&1&0&0&0&0&1&0&0&0&0&0&0&0&0&0&0&0&1&0&0&0&0&0&0&1&0&0&0&1&0&0&0&0&0&0&0&0&0&0&0&1&0&0&0\\\
0&0&0&0&0&1&0&0&1&0&0&0&0&0&0&0&0&0&0&0&0&0&0&1&0&0&0&0&0&1&0&0&0&1&0&0&0&0&0&0&0&0&0&0&0&0&1&0\\\
0&0&0&0&0&0&1&0&0&0&0&1&0&0&0&0&0&0&0&0&1&0&0&0&0&0&0&0&0&0&1&0&0&0&1&0&0&0&0&0&0&0&0&0&0&1&0&0\\\
0&0&0&0&0&0&0&1&0&0&1&0&0&0&0&0&0&0&0&0&0&0&1&0&0&0&0&0&0&0&0&1&0&0&0&1&0&0&0&0&0&0&0&0&0&0&0&1\\\
0&0&1&0&0&0&0&0&0&1&0&0&0&0&0&0&1&0&0&0&0&0&0&0&1&0&0&0&0&0&0&0&1&0&0&0&0&0&0&0&1&0&0&0&0&0&0&0\\\
0&0&0&1&0&0&0&0&1&0&0&0&0&0&0&0&0&0&1&0&0&0&0&0&0&1&0&0&0&0&0&0&0&1&0&0&0&0&0&0&0&0&1&0&0&0&0&0\\\
1&0&0&0&0&0&0&0&0&0&0&1&0&0&0&0&0&1&0&0&0&0&0&0&0&0&1&0&0&0&0&0&0&0&1&0&0&0&0&0&0&1&0&0&0&0&0&0\\\
0&1&0&0&0&0&0&0&0&0&1&0&0&0&0&0&0&0&0&1&0&0&0&0&0&0&0&1&0&0&0&0&0&0&0&1&0&0&0&0&0&0&0&1&0&0&0&0\\\
0&0&1&0&0&0&0&0&0&0&0&0&0&0&1&0&1&0&0&0&0&0&0&0&1&0&0&0&0&0&0&0&0&0&0&0&1&0&0&0&1&0&0&0&0&0&0&0\\\
1&0&0&0&0&0&0&0&0&0&0&0&0&0&0&1&0&1&0&0&0&0&0&0&0&0&1&0&0&0&0&0&0&0&0&0&0&1&0&0&0&1&0&0&0&0&0&0\\\
0&0&0&1&0&0&0&0&0&0&0&0&1&0&0&0&0&0&1&0&0&0&0&0&0&1&0&0&0&0&0&0&0&0&0&0&0&0&1&0&0&0&1&0&0&0&0&0\\\
0&1&0&0&0&0&0&0&0&0&0&0&0&1&0&0&0&0&0&1&0&0&0&0&0&0&0&1&0&0&0&0&0&0&0&0&0&0&0&1&0&0&0&1&0&0&0&0\\\
0&0&0&0&0&0&0&0&0&1&0&0&0&0&0&0&1&0&0&0&0&1&0&0&0&0&0&0&0&0&0&0&1&0&0&0&0&0&0&0&1&0&0&0&1&0&0&0\\\
0&0&0&0&0&0&0&0&0&0&0&1&0&0&0&0&0&1&0&0&1&0&0&0&0&0&0&0&0&0&0&0&0&0&1&0&0&0&0&0&0&1&0&0&0&1&0&0\\\
0&0&0&0&0&0&0&0&1&0&0&0&0&0&0&0&0&0&1&0&0&0&0&1&0&0&0&0&0&0&0&0&0&1&0&0&0&0&0&0&0&0&1&0&0&0&1&0\\\
0&0&0&0&0&0&0&0&0&0&1&0&0&0&0&0&0&0&0&1&0&0&1&0&0&0&0&0&0&0&0&0&0&0&0&1&0&0&0&0&0&0&0&1&0&0&0&1\\\
0&0&0&0&1&0&0&0&0&0&0&0&0&0&1&0&0&0&0&0&0&1&0&0&0&0&0&0&1&0&0&0&0&0&0&0&1&0&0&0&0&0&0&0&1&0&0&0\\\
0&0&0&0&0&0&1&0&0&0&0&0&0&0&0&1&0&0&0&0&1&0&0&0&0&0&0&0&0&0&1&0&0&0&0&0&0&1&0&0&0&0&0&0&0&1&0&0\\\
0&0&0&0&0&1&0&0&0&0&0&0&1&0&0&0&0&0&0&0&0&0&0&1&0&0&0&0&0&1&0&0&0&0&0&0&0&0&1&0&0&0&0&0&0&0&1&0\\\
0&0&0&0&0&0&0&1&0&0&0&0&0&1&0&0&0&0&0&0&0&0&1&0&0&0&0&0&0&0&0&1&0&0&0&0&0&0&0&1&0&0&0&0&0&0&0&1\end{array}\right)$

whose characteritic polynomial $\det(xI-L({\mathbf{B}}_{1}))$ is

$(x-6)\cdot(x-4)^{3}\cdot(x-2)^{15}\cdot x^{29}.$

We turn to study the cutoff. We see that the mixing time is in the order of
$n\log n$ (Theorem 3.1). Let $d_{TV}(\mu,\nu)$ be the total variation distance
between the probability distributions $\mu,\nu$.

###### Theorem 1.2

(1) Let $c>0$. Then we can find $f(c)>0$, s.t. for $k=[n\log n+cn]$ we have

$\displaystyle d_{TV}\left(\left(\frac{1}{np}{\bf B}_{1}\right)^{k},U\right)$
$\displaystyle=$ $\displaystyle f(c)+o(1),\quad n\to\infty.$

where

$\displaystyle f(c)\leq e^{-c}+{\cal O}(e^{-2c}),\quad c\to\infty.$

(2) Suppose $\\{c_{n}\\}_{n}$ satisfy

$\displaystyle\log\left\\{\log(np)\cdot\log n\right\\}\leq c_{n}<<\log n$

where $a_{n}\ll b_{n}$ means that $\lim_{n\to\infty}\dfrac{a_{n}}{b_{n}}=0$.
Let $k:=[n\log n-c_{n}\cdot n]$. Then for any $\delta>0$, we have

$\displaystyle d_{TV}\left(\left(\frac{1}{np}{\bf
B}_{1}\right)^{k},U\right)\geq 1-{\cal
O}\left(\frac{1}{n^{1/2-\delta}}\right),\quad n\to\infty.$

Remark
For the second statement (2), the condition $\log\left\\{\log(np)\cdot\log
n\right\\}\leq c_{n}<<\log n$ for $\\{c_{n}\\}$ roughly means that
$(2+\delta)\log\log n\leq c_{n}\ll\log n$ for any small $\delta>0$. The
exponent $1/2-\delta$ originates in the asymptotic formula of the Stirling
numbers of the second kind [8]. If we take $c_{n}$ bigger such as
$\log\left\\{\log(np)\cdot\log n+d\log n\right\\}\leq c_{n}<<\log n$, then the
lower bound becomes $d_{TV}\left(\left(\frac{1}{np}{\bf
B}_{1}\right)^{k},U\right)\geq 1-{\cal
O}\left(\frac{1}{n^{d+1/2-\delta}}\right)$.

The outline of this paper is as follows. In section 2, we study basic
properties of ${\bf B}_{k}$ and derive a formula expressing the powers of
${\bf B}_{k}$ in terms of orthogonal idempotents, from which we can compute
the eigenvalues and corresponding eigenspaces of the left-regular
representation of ${\bf B}_{1}$ explicitly. In section 3, we derive a formula
computing the total variance distance beween the probability distribution of
the repeated top to random shuffles and the uniform distribution. It then
follows that the mixing time is in the order of $n\log n$. In section 4, we
further estimate this TV distance using the asymptotic formula for the
Stirling numbers of the second kind [8], yielding a cutoff statement.

##  2 Eigenvalues and their multiplicities

The following lemma follows from a theorem in [12] which treats more general
cases. However we present its elementary proof.

###### Lemma 2.1

We have the following formula for the products of ${\bf B}_{k}$’s.

$\displaystyle{\bf B}_{k}{\bf B}_{1}$ $\displaystyle=$
$\displaystyle\begin{cases}pk{\bf B}_{k}+{\bf B}_{k+1}&(1\leq k\leq n-1)\\\
pn{\bf B}_{n}&(k=n)\end{cases}$

from which we have

$\displaystyle{\bf B}_{k}$ $\displaystyle=$ $\displaystyle{\bf B}_{1}({\bf
B}_{1}-p{\bf I})({\bf B}_{1}-2p{\bf I})\cdots({\bf B}_{1}-(k-1)p{\bf I}).$

In particular, ${\mathbf{B}}_{1},{\mathbf{B}}_{2},\ldots,{\mathbf{B}}_{n}$
generate a commutative subalgebra of ${\mathbb{Q}}G_{n,p}$.

Proof. We rewrite ${\mathbf{B}}_{k}=\sum_{\alpha\in
G_{k,p}}\alpha\mathbin{\mathchoice{\kern 0.0pt\hbox to0.0pt{\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox to0.0pt{\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}}W_{k,n}$ by grouping the
terms by the leading letter as follows.

${\mathbf{B}}_{k}=\sum_{t\in(C_{p}\times[k])\cup\\{(0,k+1)\\}}{\mathbf{C}}_{k}(t),$

where ${\mathbf{C}}_{k}(t)$ is the sum of the elements in ${\mathbf{B}}_{a}$
whose leading letter is $t$. For example when $p=2$ and $n=4$,

${\mathbf{C}}_{2}(\bar{2})=\bar{2}134+\bar{2}314+\bar{2}341+\bar{2}\bar{1}34+\bar{2}3\bar{1}4+\bar{2}34\bar{1}.$

and

${\mathbf{B}}_{2}={\mathbf{C}}_{2}(1)+{\mathbf{C}}_{2}(\bar{1})+{\mathbf{C}}_{2}(2)+{\mathbf{C}}_{2}(\bar{2})+{\mathbf{C}}_{2}(3).$

By lemma 5.1, we have

${\mathbf{C}}_{k}(t){\mathbf{B}}_{1}=\begin{cases}{\mathbf{B}}_{k}&t\in[p]\times[k],\\\
{\mathbf{B}}_{k+1}&t=(0,k+1)\end{cases}$

which yields

${\mathbf{B}}_{k}{\mathbf{B}}_{1}=pk{\mathbf{B}}_{k}+{\mathbf{B}}_{k+1}.$

Therefore

${\mathbf{B}}_{k}={\mathbf{B}}_{k-1}\left({\mathbf{B}}_{1}-p(k-1){\bf
I}\right)={\mathbf{B}}_{1}\left({\mathbf{B}}_{1}-p{\bf
I}\right)\left({\mathbf{B}}_{1}-2p{\bf
I}\right)\cdots\left({\mathbf{B}}_{1}-(k-1)p{\bf I}\right)$

and ${\mathbf{B}}_{a}$ and ${\mathbf{B}}_{b}$ commute for any $1\leq a,b\leq
n$.

Let ${k\brack a}$ (resp. ${k\brace a}$), where $k,a$ are non-negative
integers, be the Stirling number of the first kind (resp. the second kind)
defined respectively by

$\displaystyle{k+1\brack a}$ $\displaystyle=$ $\displaystyle k{k\brack
a}+{k\brack a-1},\quad a\geq 1,\quad{0\brack a}=1(a=0)$
$\displaystyle{k+1\brace a}$ $\displaystyle=$ $\displaystyle a{k\brace
a}+{k\brace a-1},\quad a\geq 1,\quad{0\brace a}=1(a=0).$

Then we can express as a linear combination of ${\bf B}_{a}$’s in terms of the
Stirling numbers of the second kind. Since these numbers defined above are the
Möbius function each other, the other way around is also possible.

###### Theorem 2.2

$\displaystyle{\bf B}_{1}^{k}$ $\displaystyle=$
$\displaystyle\sum_{a=0}^{n}p^{k-a}\left\\{\begin{array}[]{c}k\\\
a\end{array}\right\\}{\bf B}_{a},\quad k=0,1,\cdots,n.$ (3)
$\displaystyle{\mathbf{B}}_{a}$ $\displaystyle=$
$\displaystyle\sum_{i=0}^{a}(-p)^{a-i}{a\brack i}{\mathbf{B}}_{1}^{i},\quad
a=1,2,\cdots,n.$ (4)

For proof, we introduce

$\displaystyle(x)_{n,p}$ $\displaystyle:=$ $\displaystyle
x(x-p)(x-2p)\cdots\bigl{(}x-(n-1)p\bigr{)}$

and show basic identities.

###### Lemma 2.3

$\displaystyle(1)$
$\displaystyle\quad(x)_{n,p}=\sum_{k=0}^{n}p^{n-k}(-1)^{n-k}{n\brack k}x^{k}$
$\displaystyle(2)$ $\displaystyle\quad x^{n}=\sum_{k=0}^{n}p^{n-k}{n\brace
k}(x)_{k,p}.$

Proof. It suffices to substitute
$(x)_{n,p}=p^{n}\left(\dfrac{x}{p}\right)_{n}$ into the following well-known
formulas.

$\displaystyle(x)_{n}$ $\displaystyle=$
$\displaystyle\sum_{k=0}^{n}(-1)^{n-k}{n\brack k}x^{k}$ $\displaystyle x^{n}$
$\displaystyle=$ $\displaystyle\sum_{k=0}^{n}{n\brace k}(x)_{k}$

Theorem 2.2 follows immediately from Lemma 2.3.

Proof of Theorem 2.2
By Lemma 2.1, we have ${\bf B}_{a}=({\bf B}_{1})_{a,p}$. Taking $x={\bf
B}_{1}$, $n=k$, in Lemma 2.3 yields

$\displaystyle{\bf B}_{a}$ $\displaystyle=$ $\displaystyle({\bf
B}_{1})_{a,p}=\sum_{k=0}^{n}p^{a-k}(-1)^{a-k}{a\brack k}{\bf B}_{1}^{k},\quad
a=1,2,\cdots,n$ $\displaystyle{\bf B}_{1}^{k}$ $\displaystyle=$
$\displaystyle\sum_{a=0}^{k}p^{k-a}{n\brace a}({\bf
B}_{1})_{a,p}=\sum_{a=0}^{k}p^{k-a}{k\brace a}{\bf B}_{a},\quad
k=1,2,\cdots,n.$

Besides, we can explicitly see that they are valid also for $a=0$ and $k=0$.

Remark  ${k\brack a}_{p}:=p^{k-a}{k\brack a}$, and ${k\brace
a}_{p}:=p^{k-a}{k\brace a}$ satisfy the recursion equation and the Möbius
relation similar to the usual one, so that we can regard them as a $p$-version
of the Stirling numbers.

$\displaystyle{k+1\brack a}_{p}=pk{k\brace a}_{p}+{k\brack
a-1}_{p},\quad{0\brack 0}_{p}=1$ $\displaystyle{k+1\brace a}_{p}=pa{k\brace
a}_{p}+{k\brace a-1}_{p},\quad{0\brace 0}_{p}=1$
$\displaystyle\sum_{j}(-1)^{n-j}{n\brack j}_{p}{j\brace i}_{p}=\delta_{n,i}.$

However, ${k\brack a}_{p}$ is different from the Stirling-Frobenius cycle
number of parameter $p$ which appears in the analysis of a $p$-version of the
riffle shuffle [9, 10].

We define the elements ${\bf e}_{i}$ of the group algebra
${\mathbb{Q}}G_{n,p}$ by

${\bf e}_{i}=\frac{1}{i!}\sum_{a=i}^{n}\frac{(-1)^{a-i}}{p^{a}(a-i)!}{\bf
B}_{a},$ (5)

for $i=0,1,\ldots,n$. Then the powers of ${\bf B}_{1}$ are expressed in terms
of $\\{{\bf e}_{i}\\}$, which in turn shows that $\\{{\bf e}_{i}\\}$ is the
orthogonal idempotents : $\sum_{i=0}^{n}{\bf e}_{i}=I$, ${\bf e}_{i}\cdot{\bf
e}_{j}=\delta_{i,j}$.

###### Theorem 2.4

${\bf B}_{1}^{k}=\sum_{i=0}^{n}(pi)^{k}{\bf e}_{i},\quad k=0,1,\ldots,$ (6)

Proof. We use the following idendity [7]

${k\brace a}=[t^{k}]\left(\frac{k!}{a!}\left(e^{t}-1\right)^{a}\right).$

In fact, by Taylor’s expansion,

$\displaystyle\frac{k!}{a!}\left(e^{t}-1\right)^{a}$ $\displaystyle=$
$\displaystyle\frac{k!}{a!}\left(\frac{t}{1!}+\frac{t^{2}}{2!}+\cdots\right)\left(\frac{t}{1!}+\frac{t^{2}}{2!}+\cdots\right)\cdots\left(\frac{t}{1!}+\frac{t^{2}}{2!}+\cdots\right).$

Taking the coefficient of $t^{k}$ leads us to this formula :

$\displaystyle[t^{k}]\frac{k!}{a!}\left(e^{t}-1\right)^{a}$ $\displaystyle=$
$\displaystyle\sum_{k_{1}+\cdots+k_{a}=k}\frac{k!}{k_{1}!k_{2}!\cdots
k_{a}!}\cdot\frac{1}{a!}\cdot t^{k}={k\brace a}t^{k}.$

By the bionmial theorem,

$\displaystyle{k\brace a}$ $\displaystyle=$
$\displaystyle[t^{k}]\frac{k!}{a!}\sum_{i=0}^{a}\left(\begin{array}[]{c}a\\\
i\end{array}\right)(-1)^{a-i}e^{it}=\sum_{i=0}^{a}\frac{(-1)^{a-i}}{i!(a-i)!}\cdot
i^{k}.$

We note that this formula is valid also for $k=0$. Using this equation in (3)
and changing the order of summation yield the conclusion.

$\displaystyle{\bf B}_{1}^{k}$ $\displaystyle=$
$\displaystyle\sum_{a=0}^{n}p^{k-a}\sum_{i=0}^{a}\frac{(-1)^{a-i}}{i!(a-i)!}\cdot
i^{k}{\bf
B}_{a}=\sum_{i=0}^{n}(ip)^{k}\sum_{a=i}^{n}\frac{1}{p^{a}}\cdot\frac{(-1)^{a-i}}{i!(a-i)!}{\bf
B}_{a}=\sum_{i=0}^{n}(ip)^{k}{\bf e}_{i}.$

The following lemma is in [2] which can be proved by the standard argument of
the inclusion and exclusion principle [11].

###### Lemma 2.5

([2]) Let $D_{n,p}$ be the number of derangements in $G_{n,p}$. Then,

$D_{n,p}=p^{n}n!\sum_{k=0}^{n}\frac{(-1)^{k}}{p^{k}k!}.$

Proof of Theorem 1.1 Let $E_{i}$ be the matrices defined by

$E_{i}=L(e_{i})$

for $i=0,1,\ldots,n$. By transforming the both sides of $(\ref{eq:Bpower})$ by
$L$, we have

$L({\bf B}_{1})^{k}=\sum_{i=0}^{n}(pi)^{k}E_{i}.$

Since each ${\bf B}_{a}$ contains exactly one identity permutation, we have
${\rm Trace}\,L({\mathbf{B}}_{a})=|G_{n,p}|=p^{n}n!$. Then we compute

$\displaystyle{\rm Trace}\;E_{i}$ $\displaystyle=$
$\displaystyle\frac{1}{i!}\sum_{a=i}^{n}\frac{(-1)^{a-i}}{p^{a}(a-i)!}p^{n}n!={n\choose
i}p^{n-i}(n-i)!\sum_{b=0}^{n-i}\frac{(-1)^{b}}{p^{b}b!}={n\choose i}D_{n-i,p}$

which is the number of elements of $G_{n,p}$ with $i$ fixed points.

We have analogous formulas for ${\bf B}_{a}$.

###### Corollary 2.6

${\mathbf{B}}_{a}^{k}=\sum_{i=a}^{n}\left(p^{a}a!{i\choose a}\right)^{k}{\bf
e}_{i},\quad k=0,1,\ldots$ (8)

Therefore, the eigenvalues of $L({\mathbf{B}}_{a})$ are

$0,p^{a}a!,~{}p^{a}a!{a+1\choose a},p^{a}a!{a+2\choose
a},\ldots,p^{a}a!{n\choose a}.$

The multiplicity of the eigenvalue $p^{a}a!{i\choose a}$ is same as that for
${\bf B}_{1}$.

Proof. It suffices to show

${\mathbf{B}}_{a}=\sum_{i=a}^{n}p^{a}a!{i\choose a}{\bf e}_{i},\quad
a=0,1,\cdots,n.$

In order for that, we aim to express ${\bf B}_{a}$ in terms of ${\bf e}_{i}$’s
by using (5)

${\bf
e}_{i}=\sum_{b=i}^{n}\frac{1}{p^{i}i!}\frac{(-1)^{b-i}}{p^{b-i}(b-i)!}{\bf
B}_{b}=\sum_{b=i}^{n}\frac{1}{p^{i}i!}[x^{b-i}]\left(e^{-\frac{x}{p}}\right){\bf
B}_{b}.$ (9)

The “reciprocal” of these coefficients are equal to

$\displaystyle i!p^{i}[x^{i-a}]\left(e^{\frac{x}{p}}\right)$ $\displaystyle=$
$\displaystyle
i!p^{i}\frac{1}{(i-a)!}[x^{i-a}]\left(\frac{x}{p}\right)^{i-a}=p^{a}a!{i\choose
a}$

which satisfy

$\displaystyle\sum_{i=a}^{n}\left(e^{\frac{x}{p}}\right)[x^{i-a}]\left(e^{-\frac{x}{p}}\right)[x^{b-i}]=\delta_{a,b}.$

Thus, applying $\sum_{i=a}^{n}i!p^{i}[x^{i-a}]\left(e^{\frac{x}{p}}\right)$ on
both sides of (9) yields

$\displaystyle\sum_{i=a}^{n}i!p^{i}\left(e^{\frac{x}{p}}\right)[x^{i-a}]{\bf
e}_{i}$ $\displaystyle=$
$\displaystyle\sum_{i=a}^{n}i!p^{i}\left(e^{\frac{x}{p}}\right)[x^{i-a}]\sum_{b=i}^{n}\frac{1}{p^{i}i!}\left(e^{-\frac{x}{p}}\right)[x^{b-i}]{\bf
B}_{b}$ $\displaystyle\sum_{i=a}^{n}p^{a}a!{i\choose a}{\bf e}_{i}$
$\displaystyle=$
$\displaystyle\sum_{i=a}^{n}\sum_{b=i}^{n}\left(e^{\frac{x}{p}}\right)[x^{i-a}]\left(e^{-\frac{x}{p}}\right)[x^{b-i}]1\left(0\leq
a\leq i\leq b\leq n\right){\bf B}_{b}$ $\displaystyle=$
$\displaystyle\sum_{b=a}^{n}\sum_{i=a}^{n}\left(e^{\frac{x}{p}}\right)[x^{i-a}]\left(e^{-\frac{x}{p}}\right)[x^{b-i}]{\bf
B}_{b}$ $\displaystyle=$ $\displaystyle\sum_{b=a}^{n}\delta_{a,b}{\bf
B}_{b}={\bf B}_{a}.$

Here, we introduce the generalized Stirling numbers, which arise in the Boson
normal ordering problem [4].

$\displaystyle S_{r,s}(n,k)$ $\displaystyle:=$
$\displaystyle\frac{(-1)^{k}}{k!}\sum_{p=s}^{k}(-1)^{p}{k\choose
p}\prod_{j=1}^{p}\Bigl{(}p+(j-1)(r-s)\Bigr{)}^{\underline{s}}$ $\displaystyle
where\quad m^{\underline{s}}$ $\displaystyle:=$ $\displaystyle
m(m-1)\cdots(m-s+1)$

Then we obtain ${\bf B}_{a}$-analogue of Theorem 2.2.

###### Theorem 2.7

${\bf B}_{a}^{k}=\sum_{b=a}^{n}p^{ka-b}S_{a,a}(k,b){\mathbf{B}}_{b}.$

Proof. Using $p^{\underline{a}}=a!{p\choose a}$ in the definition, we have

$\displaystyle S_{a,a}(k,b)$ $\displaystyle=$
$\displaystyle\frac{(-1)^{b}}{b!}\sum_{i=a}^{b}(-1)^{i}{b\choose
i}\Bigl{(}a!{i\choose a}\Bigr{)}^{k}.$

Using

$\displaystyle{\bf e}_{i}$ $\displaystyle=$
$\displaystyle\frac{1}{i!}\sum_{b=i}^{n}\frac{(-1)^{b-i}}{p^{b}(b-i)!}{\bf
B}_{b}=\sum_{b=i}^{n}\frac{1}{p^{b}}\frac{(-1)^{b-i}}{b!}{b\choose i}{\bf
B}_{b}$

in (8) yields

$\displaystyle{\bf B}_{a}^{k}$ $\displaystyle=$
$\displaystyle\sum_{i=a}^{n}\Bigl{(}p^{a}a!{i\choose
a}\Bigr{)}^{k}\sum_{b=i}^{n}\frac{1}{p^{b}}\frac{(-1)^{b-i}}{b!}{b\choose
i}{\bf B}_{b}$ $\displaystyle=$
$\displaystyle\sum_{b=a}^{n}\frac{p^{ka-b}}{b!}\sum_{i=a}^{b}(-1)^{b-i}{b\choose
i}\Bigl{(}a!{i\choose a}\Bigr{)}^{k}{\bf B}_{b}$ $\displaystyle=$
$\displaystyle\sum_{b=a}^{n}p^{ka-b}S_{a,a}(k,b){\bf B}_{b}.$

Remark  An asymptotic formula for $S_{a,a}(k,b)$ would yield a cut-off
statement for the shuffles corresponding to ${\bf B}_{a}$.

##  3 Mixing time

In this section, we consider the mixing time of the top-to-random shuffle on
the colored permutation. Although the state space of the Markov chain is
$p^{n}$ times larger than the ordinary top-to-random shuffle on
${\mathfrak{S}}_{n}$, the mixing times do not differ significantly. Let
${\mathbf{B}}=\sum_{w\in G_{n,p}}c_{w}w\in{\mathbb{Q}}G_{n,p}$ be an element
of the group algebra ${\mathbb{Q}}G_{n,p}$. We define the $L^{1}$-norm
$|{\mathbf{B}}|$ of ${\mathbf{B}}$ by

$|{\mathbf{B}}|=\sum_{w\in G_{n,p}}|c_{w}|.$

Then it can easily be confirmed

$|{\mathbf{B}}_{a}|={n\choose a}p^{a}a!.$

and since these elements in $G_{n,p}$ consisting ${\bf B}_{a-1}$ are contained
by ${\bf B}_{a}$,

$|{\mathbf{B}}_{a}-{\mathbf{B}}_{a-1}|=|{\mathbf{B}}_{a}|-|{\mathbf{B}}_{a-1}|.$

A probability distribution ${\bf P}$ over $G_{n,p}$ can be regarded as an
element of ${\mathbb{R}}G_{n,p}$, i.e., ${\bf P}$ can be expressed as

${\bf P}=\sum_{w\in G_{n,p}}p_{w}w,$

where $p_{w}\geq 0$ and $\sum_{w\in G_{n,p}}p_{w}=1$. Let ${\bf P},{\bf
Q}\in{\mathbb{R}}G_{n,p}$ be two probability distributions on $G_{n,p}$. The
total variation distance $d_{\rm TV}$ between ${\mathbf{P}}$ and ${\bf Q}$ is
defined by

$d_{\rm TV}({\bf P},{\bf
Q})=\frac{1}{2}\left|{\mathbf{P}}-{\mathbf{Q}}\right|.$

###### Theorem 3.1

Let $p$ be greater than $1$ and let $U$ be the uniform distribution over
$G_{n,p}$, that is,

$U=\sum_{w\in G_{n,p}}\frac{1}{p^{n}n!}w.$

Then,

$\displaystyle
d_{TV}\left(\left(\frac{1}{pn}{\mathbf{B}}_{1}\right)^{k},\,U\right)$
$\displaystyle\leq$ $\displaystyle 1-\frac{{k\brace n}n!}{n^{k}}.$

Remark  When we put $k$ balls randomly into $n$ boxes, the probability of the
event that no box is empty is equal to ${k\brace n}n!/n^{k}$, which can be
approximated by $e^{-ne^{-k/n}}$ when $n$ and $k$ are large (Lemma 5.2) We
have

$1-{k\brace n}n!/n^{k}\approx 1-e^{-ne^{-k/n}}\leq\varepsilon$

for

$k\geq n\log n+n\log\frac{-1}{\log(1-\varepsilon)}.$

implying that the mixing time is $\simeq n\log n$.

Proof. By Theorem 2.2, we have

$\left(\frac{1}{pn}{\mathbf{B}}\right)^{k}=\frac{1}{p^{k}n^{k}}\sum_{a=1}^{n}p^{k-a}{k\brace
a}{\mathbf{B}}_{a}.$

Therefore, if we let $A$ be the smallest of the integers $a$ such that

$\frac{1}{p^{n}n!}>\frac{\sum_{b=a}^{n}p^{k-b}{k\brace b}}{p^{k}n^{k}},$

by Lemma 3.2 below, we have

$\displaystyle d_{\rm
TV}\left(\left(\frac{1}{pn}{\mathbf{B}}\right)^{k},U\right)$ $\displaystyle=$
$\displaystyle\sum_{a\geq
A}\left(\frac{1}{p^{n}n!}-\frac{1}{p^{k}n^{k}}\sum_{b=a}^{n}p^{k-b}{k\brace
b}\right)(|B_{a}|-|B_{a-1}|)$ $\displaystyle\leq$ $\displaystyle\sum_{a\geq
A}\left(\frac{1}{p^{n}n!}-\frac{p^{k-n}{k\brace
n}}{p^{k}n^{k}}\right)\left(|{\mathbf{B}}_{a}|-|{\mathbf{B}}_{a-1}|\right)$
$\displaystyle\leq$
$\displaystyle\left(\frac{1}{p^{n}n!}-\frac{p^{k-n}{k\brace
n}}{p^{k}n^{k}}\right)|{\mathbf{B}}_{n}|=1-\frac{{k\brace n}n!}{n^{k}}.$

The following lemma gives us the TV distance between the distribution of
$k$-repeated top to random shuffles and the uniform distribution.

###### Lemma 3.2

Let

$\displaystyle A$ $\displaystyle:=$
$\displaystyle\min\left\\{a\,\middle|\,\frac{1}{p^{n}n!}>\frac{1}{(np)^{k}}\sum_{b=a}^{n}p^{k-b}\left\\{\begin{array}[]{c}k\\\
b\end{array}\right\\}\right\\}.$

Then

$\displaystyle d_{TV}\left(\left(\frac{1}{pn}B_{1}\right)^{k},U\right)$
$\displaystyle=$ $\displaystyle\sum_{a\geq
A}\left(\frac{1}{p^{n}n!}-\frac{1}{p^{k}n^{k}}\sum_{b=a}^{n}p^{k-b}{k\brace
b}\right)(|{\bf B}_{a}|-|{\bf B}_{a-1}|).$

Proof. Let

$\displaystyle{\bf C}_{a}$ $\displaystyle:=$ $\displaystyle{\bf B}_{a}-{\bf
B}_{a-1},\;{\bf C}_{0}:={\bf B}_{0}.$ $\displaystyle x_{a}$ $\displaystyle:=$
$\displaystyle\frac{1}{(pn)^{k}}\sum_{b=a}^{n}p^{k-b}{k\brace b},\quad
a=0,1,\cdots,n.$

Then

$\displaystyle\left(\frac{1}{pn}{\bf B}_{1}\right)^{k}$ $\displaystyle=$
$\displaystyle\frac{1}{(pn)^{k}}\sum_{b=1}^{n}p^{k-b}{k\brace
b}\sum_{a=1}^{b}{\bf C}_{a}+\frac{1}{(pn)^{k}}\sum_{b=1}^{n}p^{k-b}{k\brace
b}{\bf C}_{0}$ $\displaystyle=$
$\displaystyle\sum_{a=1}^{n}\frac{1}{(pn)^{k}}\sum_{b=a}^{n}p^{k-b}{k\brace
b}{\bf C}_{a}+\frac{1}{(pn)^{k}}\sum_{b=0}^{n}p^{k-b}{k\brace b}{\bf C}_{0}$
$\displaystyle=$ $\displaystyle\sum_{a=0}^{n}x_{a}{\bf C}_{a},\quad
k=0,1,\cdots,$

Where we used ${k\brace 0}=0$. Similarly, using ${\bf
B}_{n}=\sum_{a=0}^{n}{\bf C}_{a}$ we have

$\displaystyle U$ $\displaystyle=$ $\displaystyle\sum_{a=0}^{n}y_{a}{\bf
C}_{a},\quad y_{a}:=\frac{1}{n!p^{n}}.$

Hence

$\displaystyle d_{TV}\left(\left(\frac{1}{pn}{\bf B}_{1}\right)^{k},U\right)$
$\displaystyle=$ $\displaystyle\frac{1}{2}\sum_{a=0}^{n}|x_{a}-y_{a}||{\bf
C}_{a}|=\sum_{a\,:\,y_{a}>x_{a}}(x_{a}-y_{a})|{\bf C}_{a}|.$

Since $x_{a}$ is monotonically decreasing and $y_{a}$ is constant, and since
$A:=\min\\{a\,|\,y_{a}>x_{a}\\}$, we have

$\displaystyle d_{TV}\left(\left(\frac{1}{pn}{\bf B}_{1}\right)^{k},U\right)$
$\displaystyle=$ $\displaystyle\sum_{a\geq A}(y_{a}-x_{a})|{\bf C}_{a}|$
$\displaystyle=$ $\displaystyle\sum_{a\geq
A}\left(\frac{1}{p^{n}n!}-\frac{1}{p^{k}n^{k}}\sum_{b=a}^{n}p^{k-b}{k\brace
b}\right)(|{\bf B}_{a}|-|{\bf B}_{a-1}|).$

##  4 Cut - off

In this section we prove Theorem 1.2. It is easy to show the upper bound. In
fact, by Theorem 3.1, Lemma 5.2, we have

$\displaystyle d_{TV}\left(\frac{1}{(np)^{k}}B_{1}^{k},U\right)$
$\displaystyle\leq$ $\displaystyle
1-\exp[-ne^{-\frac{k}{n}}](1+o(1))\stackrel{{\scriptstyle
n\to\infty}}{{\to}}1-\exp[-e^{-c}].$

It then suffices to compute the Taylor’s expansion of $\exp[-e^{-c}]$. For the
lower bound, let

$\displaystyle X:=\lfloor n-\log n\rfloor.$

We divide into two cases : Case 1 : $A\leq X$ and Case 2 : $X\leq A$.

###  4.1  Case 1 : ($A\leq X$)

We first substitute $\sum_{a\geq A}$ for $\sum_{a\geq X}$ in the formula in
Lemma 3.2. Using $|B_{a}|=p^{a}a!{n\choose a}$, we have

$\displaystyle d_{TV}\left(\frac{1}{(np)^{k}}B_{1}^{k},U\right)$ (13)
$\displaystyle\geq$ $\displaystyle\sum_{a\geq
X}\left(\frac{1}{p^{n}n!}-\frac{1}{(np)^{k}}\sum_{b=a}^{n}p^{k-b}\left\\{\begin{array}[]{c}k\\\
b\end{array}\right\\}\right)\left(|B_{a}|-|B_{a-1}|\right)$
$\displaystyle\geq$ $\displaystyle\sum_{a\geq
X}\left(\frac{1}{p^{n}n!}-\frac{1}{(np)^{k}}\sum_{b=X}^{n}p^{k-b}\left\\{\begin{array}[]{c}k\\\
b\end{array}\right\\}\right)\left(|B_{a}|-|B_{a-1}|\right)$ (16)
$\displaystyle=$
$\displaystyle\left(1-\frac{n!}{n^{k}}\sum_{b=X}^{n}p^{n-b}\left\\{\begin{array}[]{c}k\\\
b\end{array}\right\\}\right)\left(1-\frac{1}{(n-X+1)!\cdot p^{n-X+1}}\right)$
$\displaystyle=:$ $\displaystyle(1-C)(1-D).$

We aim to show $C,D={\cal O}(n^{-1/2+\delta})$ below.

####  4.1.1  Estimate for $C$

We use the following property of the Stirling numbers of the second kind [6]:
we can uniquely find $r_{k}$ such that

$\displaystyle\left\\{\begin{array}[]{c}k\\\
1\end{array}\right\\}<\left\\{\begin{array}[]{c}k\\\
2\end{array}\right\\}<\cdots<\left\\{\begin{array}[]{c}k\\\
r_{k}\end{array}\right\\}\geq\left\\{\begin{array}[]{c}k\\\
r_{k}+1\end{array}\right\\}>\cdots>\left\\{\begin{array}[]{c}k\\\
k\end{array}\right\\}.$

Moreover [8], $r_{k}$ satisfies

$\displaystyle r_{k}$ $\displaystyle=$ $\displaystyle\frac{k}{\log k}+{\cal
O}\left(k(\log k)^{-\frac{3}{2}}\right).$

Because we are taking $k=n\log n-n\cdot c_{n}$,

$\displaystyle r_{k}\simeq\frac{k}{\log k}=\frac{n\log
n\left(1-\frac{c_{n}}{n}\right)}{\log n+\log\log
n+\log\left(1-\frac{c_{n}}{n}\right)}$

which is quite likely in the sum $\sum_{b=X}^{n}$. Therefore, according to the
large and small relationship, we further divide into three cases : Case (i)
$X\leq n\leq r_{k}$, Case (ii) $X\leq r_{k}\leq n$, and Case (iii) $r_{k}\leq
X\leq n$.

#####  Case (i) $X\leq n\leq r_{k}$ :

Since $X\leq b\leq n$, we have ${k\brace b}\leq{k\brace n}$. By Lemma 5.3,

$\displaystyle\frac{n!}{n^{k}}\sum_{b=X}^{n}p^{n-b}\left\\{\begin{array}[]{c}k\\\
b\end{array}\right\\}$ $\displaystyle\leq$
$\displaystyle\frac{n!}{n^{k}}\sum_{b=X}^{n}p^{n-b}\left\\{\begin{array}[]{c}k\\\
n\end{array}\right\\}$ $\displaystyle\leq$
$\displaystyle\exp\left[-e^{c_{n}}\right]\frac{1}{n^{\frac{1}{2}-\delta}}\frac{p}{p-1}\left(p^{n-X}-\frac{1}{p}\right)\left(1+{\cal
O}(n^{-2})\right).$

We can explicitly see that the assumption on Lemma 5.3 is satisfied which we
will not mention in what follows for simplicity. By the same reason, we will
omit the error factor $\left(1+{\cal O}(n^{-2})\right)$ below. By the
assumption $\log\left\\{\log(np)\cdot\log n\right\\}\leq c_{n}$ on
$\\{c_{n}\\}$, we have

$\displaystyle\exp\left[e^{c_{n}}\right]\geq\exp\left[\log(np)\cdot\log
n\right]=(np)^{\log n}$

yielding

$\displaystyle\frac{n!}{n^{k}}\sum_{b=X}^{n}p^{n-b}\left\\{\begin{array}[]{c}k\\\
b\end{array}\right\\}$ $\displaystyle\leq$
$\displaystyle\frac{1}{(np)^{\log(n)}}\frac{1}{n^{\frac{1}{2}-\delta}}\cdot\frac{p}{p-1}\left(p^{\log
n}-\frac{1}{p}\right)$ $\displaystyle=$ $\displaystyle{\cal
O}\left(\frac{1}{n^{1+\log n+\frac{1}{2}-\delta}}\right)={\cal O}(n^{-1}).$

#####  Case (ii) $X\leq r_{k}\leq n$ :

We set $g(n)$ by the equation $r_{k}=:n-g(n)$. $X\leq r_{k}\leq n$ implies
$0\leq g(n)\leq\log n$. We then compute

$\displaystyle\frac{n!}{n^{k}}\sum_{b=X}^{n}p^{n-b}\left\\{\begin{array}[]{c}k\\\
b\end{array}\right\\}$ $\displaystyle\leq$
$\displaystyle\frac{n!}{n^{k}}\sum_{b=X}^{n}p^{n-b}\left\\{\begin{array}[]{c}k\\\
r_{k}\end{array}\right\\}$ $\displaystyle=$
$\displaystyle\left(\frac{r_{k}}{n}\right)^{k}\frac{n!}{r_{k}!}\cdot\frac{r_{k}!}{r_{k}^{k}}\left\\{\begin{array}[]{c}k\\\
r_{k}\end{array}\right\\}\frac{p}{p-1}\left(p^{n-X}-\frac{1}{p}\right)$
$\displaystyle=:$ $\displaystyle E\cdot F\cdot
G\cdot\frac{p}{p-1}\left(p^{n-X}-\frac{1}{p}\right).$

We shall estimate each factors $E,F,G$ below. $E$ and $F$ are easy :

$\displaystyle E$ $\displaystyle:=$
$\displaystyle\left(\frac{r_{k}}{n}\right)^{k}=\left(1-\frac{g(n)}{n}\right)^{k}=\left(1-\frac{g(n)}{n}\right)^{n\log
n-c_{n}\cdot n}\leq 1$ (25) $\displaystyle F$ $\displaystyle:=$
$\displaystyle\frac{n!}{(n-g(n))!}\leq n^{g(n)}\leq n^{\log n}.$ (26)

To estimate $G$, we first use Lemma 5.3.

$\displaystyle G$ $\displaystyle:=$
$\displaystyle\frac{r_{k}!}{r_{k}^{k}}\left\\{\begin{array}[]{c}k\\\
r_{k}\end{array}\right\\}\leq\exp\left[-r_{k}e^{-\frac{k}{r_{k}}}\right]\frac{1}{r_{k}^{1/2-\delta}}$
$\displaystyle=$
$\displaystyle\exp\left[-n\left(1-\frac{g(n)}{n}\right)\left(\frac{1}{n}\right)^{\frac{1}{1-\frac{g(n)}{n}}}\cdot\left(e^{c_{n}}\right)^{\frac{1}{1-\frac{g(n)}{n}}}\right]\frac{1}{r_{k}^{1/2-\delta}}.$

Each factors in the exponential satisfy

$\displaystyle\left(\frac{1}{n}\right)^{\frac{1}{1-\frac{g(n)}{n}}}$
$\displaystyle=$ $\displaystyle\frac{1}{n}\left(1+{\cal O}\left(\frac{(\log
n)^{2}}{n}\right)\right)$
$\displaystyle\left(e^{c_{n}}\right)^{\frac{1}{1-\frac{g(n)}{n}}}$
$\displaystyle=$ $\displaystyle\left(1+{\cal O}\left(\dfrac{(\log
n)^{2}}{n}\right)\right)e^{c_{n}}$
$\displaystyle\left(\frac{1}{r_{k}}\right)^{\frac{1}{2}-\delta}$
$\displaystyle\leq$ $\displaystyle\left(\frac{1}{n\left(1-\frac{\log
n}{n}\right)}\right)^{\frac{1}{2}-\delta}\leq(const.)\left(\frac{1}{n}\right)^{\frac{1}{2}-\delta}$

so that

$G\leq\exp\left[-e^{c_{n}}\left(1+{\cal O}\left(\frac{(\log
n)^{2}}{n}\right)\right)\right]\left(\frac{1}{n}\right)^{\frac{1}{2}-\delta}.$
(28)

By (25, 26, 28), we have

$\displaystyle\frac{n!}{n^{k}}\sum_{b=X}^{n}p^{n-b}\left\\{\begin{array}[]{c}k\\\
b\end{array}\right\\}$ $\displaystyle\leq$ $\displaystyle 1\cdot n^{\log
n}\cdot\exp\left[-e^{c_{n}}\left(1+{\cal O}\left(\frac{(\log
n)^{2}}{n}\right)\right)\right]\left(\frac{1}{n}\right)^{\frac{1}{2}-\delta}\frac{p^{2}}{p-1}\left(p^{\log
n}-\frac{1}{p}\right)$ $\displaystyle=$ $\displaystyle(np)^{\log
n}\exp\left[-e^{c_{n}}\left(1+{\cal O}\left(\frac{(\log
n)^{2}}{n}\right)\right)\right]\left(\frac{1}{n}\right)^{\frac{1}{2}-\delta}\frac{p^{2}}{p-1}\left(1-\frac{1}{p^{\log
n+1}}\right).$

Therefore the condition $\log\left\\{(\log np)(\log n)\right\\}\leq c_{n}$ on
$\\{c_{n}\\}$ yields

$\displaystyle\frac{n!}{n^{k}}\sum_{b=X}^{n}p^{n-b}\left\\{\begin{array}[]{c}k\\\
b\end{array}\right\\}\leq\frac{(np)^{\log n}}{(np)^{\log
n}}\cdot\frac{1}{\exp\left[(\log np)(\log n){\cal O}\left(\frac{(\log
n)^{2}}{n}\right)\right]}\left(\frac{1}{n}\right)^{\frac{1}{2}-\delta}={\cal
O}\left(\frac{1}{n^{\frac{1}{2}-\delta}}\right).$

#####  Case (iii) $r_{k}\leq X\leq n$ :

We proceed as Case (ii) :

$\displaystyle\frac{n!}{n^{k}}\sum_{b=X}^{n}p^{n-b}\left\\{\begin{array}[]{c}k\\\
b\end{array}\right\\}$ $\displaystyle\leq$
$\displaystyle\frac{n!p^{n}}{n^{k}}\left\\{\begin{array}[]{c}k\\\
X\end{array}\right\\}\sum_{b=X}^{n}p^{-b}$ $\displaystyle=$
$\displaystyle\frac{n!}{n^{k}}\cdot\frac{X^{k}}{X!}\cdot\frac{X!}{X^{k}}\left\\{\begin{array}[]{c}k\\\
X\end{array}\right\\}p^{n}\sum_{b=X}^{n}p^{-b}$ $\displaystyle\leq$
$\displaystyle\left(\frac{X}{n}\right)^{k}\frac{n!}{X!}\exp\left[-Xe^{-\frac{k}{X}}\right]\left(\frac{1}{X}\right)^{\frac{1}{2}-\delta}\cdot\frac{p^{2}}{p-1}\left(p^{\log
n}-\frac{1}{p}\right)$ $\displaystyle=:$ $\displaystyle E\cdot F\cdot
G\cdot\frac{p^{2}}{p-1}\left(p^{\log n}-\frac{1}{p}\right)$

and aim to estimate each factors $E,F,G$. However, this is reduced to
substituting $g(n)$ in Case (ii) for $\log n$, and hence a similar argument
yields

$\displaystyle\frac{n!}{n^{k}}\sum_{b=X}^{n}p^{n-b}\left\\{\begin{array}[]{c}k\\\
b\end{array}\right\\}={\cal O}\left(\frac{1}{n^{\frac{1}{2}-\delta}}\right).$

####  4.1.2  Estimate for $D$

Using $(\log n+1)!\approx n^{\log\log n}$ and $p^{\log n}=n^{\log p}$ directly
leads us to the conclusion.

$\displaystyle D=\frac{1}{(\log n+1)!p^{\log n+1}}={\cal O}\left(n^{-\log\log
n-\log p}\right)={\cal O}(n^{-1}).$

###  4.2  Case 2 : ($A\geq X$)

We first compute

$\displaystyle d_{TV}\left(\frac{1}{(np)^{k}}B_{1}^{k},U\right)$
$\displaystyle=$ $\displaystyle\sum_{a\geq
A}\left(\frac{1}{p^{n}n!}-\frac{1}{(np)^{k}}\sum_{b=a}^{n}p^{k-b}\left\\{\begin{array}[]{c}k\\\
b\end{array}\right\\}\right)\left(|B_{a}|-|B_{a-1}|\right)$
$\displaystyle\geq$ $\displaystyle\sum_{a\geq
A}\left(\frac{1}{p^{n}n!}-\frac{1}{(np)^{k}}\sum_{b=A}^{n}p^{k-b}\left\\{\begin{array}[]{c}k\\\
b\end{array}\right\\}\right)\left(|B_{a}|-|B_{a-1}|\right)$ $\displaystyle=$
$\displaystyle\left(\frac{1}{p^{n}n!}-\frac{1}{(np)^{k}}\sum_{b=A}^{n}p^{k-b}\left\\{\begin{array}[]{c}k\\\
b\end{array}\right\\}\right)\sum_{a\geq A}\left(|B_{a}|-|B_{a-1}|\right)$
$\displaystyle\geq$
$\displaystyle\left(\frac{1}{p^{n}n!}-\frac{1}{(np)^{k}}\sum_{b=X}^{n}p^{k-b}\left\\{\begin{array}[]{c}k\\\
b\end{array}\right\\}\right)\sum_{a\geq A}\left(|B_{a}|-|B_{a-1}|\right)$
$\displaystyle=$
$\displaystyle\left(1-\frac{n!}{n^{k}}\sum_{b=X}^{n}p^{n-b}\left\\{\begin{array}[]{c}k\\\
b\end{array}\right\\}\right)\left(1-\frac{1}{(n-A+1)!\,p^{n-A+1}}\right)$
$\displaystyle=:$ $\displaystyle(1-C)(1-D^{\prime})$

where $D^{\prime}$ is equal to $D$ but $X$ is substituted by $A$. $C$ satifies
the same estimate as in Case 1. In fact, we did not use the fact that $A\leq
X$ to estimate $C$ in Case 1. Hence

$\displaystyle
C=\frac{n!}{n^{k}}\sum_{b=X}^{n}p^{n-b}\left\\{\begin{array}[]{c}k\\\
b\end{array}\right\\}={\cal O}\left(\frac{1}{n^{\frac{1}{2}-\delta}}\right).$

To estimate $D^{\prime}$, we aim to have a lower bound on $M:=n-A$. By the
definition of $A$,

$\displaystyle\frac{1}{p^{n}n!}\leq\frac{1}{(np)^{k}}\sum_{b=A-1}^{n}p^{k-b}\left\\{\begin{array}[]{c}k\\\
b\end{array}\right\\}$

so that we have

$1\leq\frac{n!}{n^{k}}\sum_{b=A-1}^{n}p^{n-b}\left\\{\begin{array}[]{c}k\\\
b\end{array}\right\\}\leq\sum_{b=A-1}^{n}p^{n-b}\begin{cases}\dfrac{n!}{n^{k}}\left\\{\begin{array}[]{c}k\\\
n\end{array}\right\\}&(X\leq n\leq K_{k})\\\
\dfrac{n!}{n^{k}}\left\\{\begin{array}[]{c}k\\\
r_{k}\end{array}\right\\}&(X\leq r_{k}\leq n)\\\
\dfrac{n!}{n^{k}}\left\\{\begin{array}[]{c}k\\\
X\end{array}\right\\}&(r_{k}\leq X\leq n)\end{cases}$ (41)

By the argument in Case 1, if $(X-1\leq)A-1\leq b\leq n$,

$\displaystyle\dfrac{n!}{n^{k}}\left\\{\begin{array}[]{c}k\\\
b\end{array}\right\\}\leq\begin{cases}\dfrac{n!}{n^{k}}\left\\{\begin{array}[]{c}k\\\
n\end{array}\right\\}\leq\exp\left[-e^{c_{n}}\right]\left(\frac{1}{n}\right)^{\frac{1}{2}-\delta}&(X\leq
n\leq r_{k})\\\ \dfrac{n!}{n^{k}}\left\\{\begin{array}[]{c}k\\\
r_{k}\end{array}\right\\}\leq n^{\log n}\exp\left[-e^{c_{n}}\left(1+{\cal
O}\left(\frac{(\log
n)^{2}}{n}\right)\right)\right]\left(\frac{1}{n}\right)^{\frac{1}{2}-\delta}&(X\leq
r_{k}\leq n)\\\ \dfrac{n!}{n^{k}}\left\\{\begin{array}[]{c}k\\\
X\end{array}\right\\}\leq n^{\log n}\exp\left[-e^{c_{n}}\left(1+{\cal
O}\left(\frac{(\log
n)^{2}}{n}\right)\right)\right]\left(\frac{1}{n}\right)^{\frac{1}{2}-\delta}&(r_{k}\leq
X)\end{cases}$

Using this estimate and the assumption $\exp[e^{c_{n}}]\geq(np)^{\log n}$ on
$(\ref{star})$, we have

$\displaystyle 1$ $\displaystyle\leq$
$\displaystyle\frac{n!}{n^{k}}\sum_{b=A-1}^{n}p^{n-b}\left\\{\begin{array}[]{c}k\\\
b\end{array}\right\\}\leq\sum_{b=A-1}^{n}p^{n-b}\cdot\frac{n^{\log
n}}{(np)^{\log n}}\cdot\frac{1}{n^{\frac{1}{2}-\delta}}$

from which we have $n^{\frac{1}{2}-\delta}\leq(const.)p^{M}$. Therefore

$\displaystyle\frac{1}{(n-A+1)!\,p^{n-A+1}}\leq\frac{1}{M!}\frac{1}{p^{M}}={\cal
O}\left(\frac{1}{n^{\frac{1}{2}-\delta}}\right).$

##  5 Appendix

###  5.1 Some elementary facts on the shuffle algebra

###### Lemma 5.1

We rewrite ${\mathbf{B}}_{k}=\sum_{\alpha\in
G_{k,p}}\alpha\mathbin{\mathchoice{\kern 0.0pt\hbox to0.0pt{\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox to0.0pt{\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}}W_{k,n}$ by grouping the
terms by the head (or top) letter as follows.

${\mathbf{B}}_{k}=\sum_{t\in(C_{p}\times[k])\cup\\{(0,k+1)\\}}{\mathbf{C}}_{k}(t),$

where ${\mathbf{C}}_{k}(t)$ is the sum of the elements in ${\mathbf{B}}_{a}$
whose leading letter is $t$. We then have

${\mathbf{C}}_{k}(t){\mathbf{B}}_{1}=\begin{cases}{\mathbf{B}}_{k}&t\in[p]\times[k],\\\
{\mathbf{B}}_{k+1}&t=(0,k+1)\end{cases}$

Proof. We regard each $\alpha\in G_{k,p}$ as a word, so that we denote by
$i(\alpha)$ the leading letter, and by $\widetilde{\alpha}$ the remaining ones
: $\alpha=i(\alpha)\widetilde{\alpha}$. Then we write

$\displaystyle{\bf B}_{k}$ $\displaystyle=$ $\displaystyle\sum_{\alpha\in
G_{k,p}}\alpha\mathbin{\mathchoice{\kern 0.0pt\hbox to0.0pt{\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox to0.0pt{\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}}(a+1)(a+2)\cdots n$
$\displaystyle=$ $\displaystyle
1\sum_{i(\alpha)=1}\widetilde{\alpha}\mathbin{\mathchoice{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern
0.0pt}}W_{k,n}+2\sum_{i(\alpha)=2}\widetilde{\alpha}\mathbin{\mathchoice{\kern
0.0pt\hbox to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise
0.0pt\hbox to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern
0.0pt}}W_{k,n}+\cdots+k\sum_{i(\alpha)=k}\widetilde{\alpha}\mathbin{\mathchoice{\kern
0.0pt\hbox to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise
0.0pt\hbox to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}}W_{k,n}$
$\displaystyle+(k+1)\sum_{\alpha\in G_{k,p}}\alpha\mathbin{\mathchoice{\kern
0.0pt\hbox to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise
0.0pt\hbox to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}}W_{k+1,n}$ $\displaystyle=:$
$\displaystyle C_{k}(1)+\cdots+C_{k}(k)+C_{k}(k+1).$

(i) $t=1,2,\cdots,k$ :

$\displaystyle C_{k}(t)$ $\displaystyle=$ $\displaystyle
t\sum_{i(\alpha)=t}\widetilde{\alpha}\mathbin{\mathchoice{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern
0.0pt}}W_{k,n}=t\sum_{i(\alpha)=t}\widetilde{\alpha}\mathbin{\mathchoice{\kern
0.0pt\hbox to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise
0.0pt\hbox to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}}(k+1)\cdots n$

Applying ${\bf B}_{1}$ from the right is equivalent to inserting the first
alphabet $t$ randomly. Since the shuffle operator is associative, we have

$\displaystyle C_{k}(t){\bf B}_{1}$ $\displaystyle=$
$\displaystyle\sum_{i(\alpha)=t}t\mathbin{\mathchoice{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern
0.0pt}}\left(\widetilde{\alpha}\mathbin{\mathchoice{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern
0.0pt}}W_{k}\right)=\sum_{i(\alpha)=t}\left(t\mathbin{\mathchoice{\kern
0.0pt\hbox to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise
0.0pt\hbox to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern
0.0pt}}\widetilde{\alpha}\right)\mathbin{\mathchoice{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern
0.0pt}}W_{k}=\left(\sum_{i(\alpha)=t}t\mathbin{\mathchoice{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern
0.0pt}}\widetilde{\alpha}\right)\mathbin{\mathchoice{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}}W_{k}$

Equation
$\displaystyle\sum_{\alpha\,:\,i(\alpha)=t}t\mathbin{\mathchoice{\kern
0.0pt\hbox to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise
0.0pt\hbox to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern 0.0pt}{\kern 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hss}\raise 0.0pt\hbox
to0.0pt{\vrule height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\hfill\vrule
height=0.0pt,depth=0.0pt,width=0.0pt}\kern
0.0pt}}\widetilde{\alpha}=\sum_{\alpha\in G_{k,p}}\alpha$ yields the result.
(ii) $t=k+1$ : we can argue similarly as in (i).

###  5.2 Asymptotics on Stirling numbers

The following lemma is well-known, but we provide a proof for completeness.

###### Lemma 5.2

Let $\lambda>0$. Then if $n$ and $k$ goes to infinity satisfying
$ne^{-\frac{k}{n}}\to\lambda$, we have

$\displaystyle{k\brace n}\frac{n!}{n^{k}}\to e^{-\lambda}.$

Proof. We consider putting $k$ balls uniformly at random into $n$ boxes. Then
$p(k,n):={k\brace n}\frac{n!}{n^{k}}$ is equal to the probability that no
boxes are empty. We aim to show $p(k,n)\to e^{-\lambda}$. By the inclusion -
exclusion principle,

$p(k,n)=\sum_{j=0}^{n}(-1)^{j}{n\choose j}\left(1-\frac{j}{n}\right)^{k}.$
(44)

Here we use the following estimates :

$\displaystyle{n\choose
j}=\frac{n(n-1)\cdots(n-j+1)}{j!}\begin{cases}\leq\dfrac{n^{j}}{j!}\\\
=\dfrac{n^{j}}{j!}\left(1-{\cal
O}\left(\dfrac{j^{2}}{n}\right)\right)\end{cases}$ $\displaystyle 0\leq x\leq
1/2\quad\Longrightarrow\quad e^{-x-x^{2}}\leq 1-x\leq e^{-x}.$

Then we have

$\frac{1}{j!}\left(ne^{-\frac{k}{n}}\right)^{j}e^{-k\left(\frac{j}{n}\right)^{2}}\left(1-{\cal
O}\left(\frac{j^{2}}{n}\right)\right)\leq{n\choose
j}\left(1-\frac{j}{n}\right)^{k}\leq\frac{1}{j!}\left(ne^{-\frac{k}{n}}\right)^{j}.$
(45)

Now we use the fact $k=n\log n-n\cdot\log(\lambda+o(1))$ and the estimate (45)
to apply the dominated convergence theorem on (44), yielding the conclusion.

We next turn to the general case.

###### Lemma 5.3

Suppose

$\frac{n}{\sqrt{k}}\to\infty,\quad\frac{k}{n}-\log\sqrt{k}\to\infty.$ (46)

Then for any $\delta>0$, the following bound is valid for sufficiently large
$n$.

$\displaystyle S_{k,n}$ $\displaystyle\leq$
$\displaystyle\frac{n^{k}}{n!}\exp\left[-ne^{-\frac{k}{n}}\right]e^{\left(\frac{1}{2}-\delta\right)e^{-\frac{k}{n}}}\left(1+{\cal
O}(n^{-2})\right).$

In particular, when $k=n\log n-c_{n}n$, $c_{n}\ll\log n$, we have

$\displaystyle S_{k,n}$ $\displaystyle\leq$
$\displaystyle\frac{n^{k}}{n!}\exp\left[-ne^{-\frac{k}{n}}\right]\frac{1}{n^{\frac{1}{2}-\delta}}\left(1+{\cal
O}(n^{-2})\right).$

We used Lemma 5.3 several times in the proof of Theorem 1.2, and it is easy to
check that the assumption (46) is valid in all cases. Lemma 5.3 follows
directly from the result by Menon [8].

###### Lemma 5.4

(Menon [8]) Suppose

$\displaystyle\frac{n}{\sqrt{k}}\to\infty,\quad\frac{k}{n}-\log\sqrt{k}\to\infty.$

Then

$\displaystyle S_{k,n}$ $\displaystyle=$
$\displaystyle\frac{n^{k}}{n!}\exp\left[-e^{\lambda}\right]\left(1+{\cal
O}(n^{-2})\right)$ $\displaystyle\mbox{ where }\quad\lambda$ $\displaystyle:=$
$\displaystyle\log n-\frac{k}{n}+\frac{1}{2n}-\frac{1}{12n^{2}}.$

Acknowledgement  This work is partially supported by JSPS KAKENHI Grant Number
20K03659(F.N.).

## References

  * [1] David Aldous and Persi Diaconis.  Shuffling cards and stopping times.  The American Mathematical Monthly, 93(5):333–348, 1986.
  * [2] Sami H Assaf.  Cyclic derangements.  The Electronic Journal of Combinatorics, 17(R163):1, 2010\.
  * [3] François Bergeron and Nantel Bergeron.  Orthogonal idempotents in the descent algebra of bn and applications.  Journal of Pure and Applied Algebra, 79(2):109–129, 1992.
  * [4] P. Blasiak, K.A Penson, and A.L. Solomon.  Boson normal ordering problem and generalized bell numbers.  Annals of Combinatorics, 7:127–139, 2003.
  * [5] Persi Diaconis, James Allen Fill, and Jim Pitman.  Analysis of top to random shuffles.  Combinatorics, probability and computing, 1(02):135–155, 1992.
  * [6] A.J. Dobson.  A note on stirling numbers of the second kind.  Journal of Combinatorial Theory, 5:212–214, 1968.
  * [7] A. M. Garsia.  On the powers of top to random shuffling, 2002.
  * [8] V. V. Menon.  On the maximum of stirling numbers of the second kind.  Journal of Combinatorial Theory, A15:11–24, 1973.
  * [9] Fumihiko Nakano and Taizo Sadahiro.  A generalization of carries process and riffle shuffles.  Discrete Mathematics, 339(2):974–991, 2016.
  * [10] Fumihiko Nakano and Taizo Sadahiro.  Determinantal formula for generalized riffle shuffle.  Discrete Mathematics, 344(12):112599, 2021.
  * [11] Richard P Stanley.  Enumerative combinatorics. vol. 1, vol. 49 of cambridge studies in advanced mathematics, 1997.
  * [12] Roger Tian.  Generalizations of an expansion formula for top to random shuffles.  Annals of Combinatorics, 20:899–916, 2016.