text:
# 1 Introduction

## 1 Introduction

In an unpublished effort to study the way real people shuffle cards, Gilbert-Shannon-Reeds introduced the following model, called $`k`$-riffle shuffling. Given a deck of $`n`$ cards, one cuts it into $`k`$ piles with probability of pile sizes $`j_1,\mathrm{},j_k`$ given by $`\frac{\left(\genfrac{}{}{0pt}{}{n}{j_1,\mathrm{},j_k}\right)}{k^n}`$. Then cards are dropped from the packets with probability proportional to the pile size at a given time (thus if the current pile sizes are $`A_1,\mathrm{},A_k`$, the next card is dropped from pile $`i`$ with probability $`\frac{A_i}{A_1+\mathrm{}+A_k}`$).

The theory of riffle shuffling is relevant to many parts of mathematics. One area of mathematics influenced by shuffling is Markov chain theory \[D2\]. For instance Bayer and Diaconis \[BayD\] proved that $`\frac{3}{2}log_2(n)`$ $`2`$-shuffles are necessary and sufficient to mix up a deck of $`n`$ cards and observed a cut-off phenomenon. The paper \[Hanl\] gives applications of shuffling to Hochschild homology and the paper \[BW\] describes the relation with explicit versions of the Poincaré-Birkhoff-Witt theorem. Section 3.8 of \[ShSter\] describes GSR shuffles in the language of Hopf algebras. In recent work, Stanley \[Sta\] has related biased riffle shuffles with the Robinson-Schensted-Knuth correspondence, thereby giving an elementary probabilistic interpretation of Schur functions and a different approach to some work of interest to the random matrix community. He recasts many of the results of \[BayD\] and \[F1\] using quasisymmetric functions. Connections of riffle shuffling with dynamical systems appear in \[BayD\], \[La1\], \[La2\], \[F4\]. Generalizations of the GSR shuffles to other Coxeter groups appear in \[BB\],\[F2\], \[F3\], \[F4\], \[F5\].

It is useful to recall one of the most remarkable properties of GSR $`k`$-shuffles. Since $`k`$-shuffles induce a probability measure on conjugacy classes of $`S_n`$, they induce a probability measure on partitions $`\lambda `$ of $`n`$. Consider the factorization of random degree $`n`$ polynomials over a field $`F_q`$ into irreducibles. The degrees of the irreducible factors of a randomly chosen degree $`n`$ polynomial also give a random partition of $`n`$. The fundamental result of Diaconis-McGrath-Pitman (DMP) \[DMP\] is that this measure on partitions of $`n`$ agrees with the measure induced by card shuffling when $`k=q`$. This allowed natural questions on shuffling to be reduced to known results on factors of polynomials and vice versa. Lie theoretic formulations, generalizations, and analogs of the DMP theorem appear in \[F2\],\[F3\],\[F4\].

The motivation behind this paper was to understand the DMP theorem and its cousins in terms of symmetric function theory. (All notation will follow that of \[Mac\] and background will appear in Section 2). For the DMP theorem itself Stanley \[Sta\] gives an argument using ideas from symmetric theory. The argument in Section 3 is different and emphasizes the role of the RSK correspondence and the Cauchy identity

$$\underset{\lambda }{}s_\lambda (x)s_\lambda (y)=\underset{\lambda }{}\frac{1}{z_\lambda }p_\lambda (x)p_\lambda (y).$$

Here $`s_\lambda `$ and $`p_\lambda `$ denote the Schur functions and power sum symmetric functions respectively.

Given Section 3, it was very natural to seek card shuffling interpretations for the Cauchy type identities

$$\underset{\lambda }{}s_\lambda ^{}(x)s_\lambda (y)=\underset{\lambda }{}\frac{ϵ_\lambda }{z_\lambda }p_\lambda (x)p_\lambda (y)$$

$$\underset{\lambda }{}s_\lambda (x)S_\lambda (y)=\underset{\genfrac{}{}{0pt}{}{\lambda }{allpartsodd}}{}\frac{2^{l(\lambda )}}{z_\lambda }p_\lambda (x)p_\lambda (y)$$

$$\underset{\lambda }{}s_\lambda ^{}(x)S_\lambda (y)=\underset{\genfrac{}{}{0pt}{}{\lambda }{allpartsodd}}{}\frac{2^{l(\lambda )}ϵ_\lambda }{z_\lambda }p_\lambda (x)p_\lambda (y)$$

$$\underset{\lambda }{}s_\lambda (x)\stackrel{~}{s}_\lambda (\alpha ,\beta ,\gamma )=\underset{\lambda }{}\frac{1}{z_\lambda }p_\lambda (x)\stackrel{~}{p}_\lambda (\alpha ,\beta ,\gamma )$$

Here $`\lambda ^{}`$ denotes the transpose of a partition and $`ϵ_\lambda =(1)^{|\lambda |l(\lambda )}`$ where $`l(\lambda )`$ is the number of parts of $`\lambda `$. $`S_\lambda `$ is a symmetric function studied for instance by Stembridge \[Stem\] and defined in Section 5. The symmetric function $`\stackrel{~}{s}_\lambda (\alpha ,\beta ,\gamma )`$ is an extended Schur function to be discussed in Section 6. (The fourth identity is actually a generalization of the second identity though it will be helpful to treat them differently).

In fact these identities (and probably many identities from symmetric function theory) are related to card shuffling. Section 4 relates the first of these identities to riffle shuffles followed by reversing the order of the cards; the resulting cycle index permits calculations of interest to real-world shufflers. Section 5 relates the second of these identities to the cycle structure of affine hyperoctahedral shuffles, which are generalizations of unimodal permutations; the third identity shows that dealing from the bottom of the deck has no effect for these shuffles. This gives a non-Lie theoretic approach to some results in \[F4\] and proves a more general assertion. Although there is some overlap with the preprint \[Th\] for the case of unimodal permutations, even in that case the treatment here is quite different and forces into consideration a variation of the RSK correspondence, which we believe to be new. We should also point out that Gannon \[Gan\] was the first to solve the problem of counting unimodal permutations by cycle structure, using completely different ideas. (His results are not in the form of a cycle index and it would be interesting to understand the results in this paper by his technique).

Section 6 develops preliminaries related to the case of extended Schur functions. It defines models of card shuffling called $`(\stackrel{}{\alpha },\stackrel{}{\beta },\gamma )`$ shuffles (which include the GSR shuffles) and explains how they iterate. This model contains other shuffles of interest such as iterations of the following procedure. Given a deck of $`n`$ cards, cut the deck into two piles where the sizes are $`k,nk`$ with probability $`\frac{\left(\genfrac{}{}{0pt}{}{n}{k}\right)}{2^n}`$; then shuffle the size $`k`$ pile thoroughly and riffle it with the remaining cards. This special case was first studied in \[DFP\] (their work was on convergence rates, not in cycle structure or increasing subsequence structure). Section 6 proves that if one applies the usual RSK correspondence to a permutation distributed as a $`(\stackrel{}{\alpha },\stackrel{}{\beta },\gamma )`$ shuffle, then the probability of getting any recording tableau of shape $`\lambda `$ is the extended Schur function $`\stackrel{~}{s}_\lambda (\stackrel{}{\alpha },\stackrel{}{\beta },\gamma )`$. (When $`\gamma 0`$ this is equivalent to a result of Kerov/Vershik \[KV\] and Berele/Remmel \[BeRe\]. However the case $`\gamma 0`$ (which arises for the shuffle in this paragraph), is treated incorrectly in \[KV\] and not at all in \[BeRe\]).

Section 7 applies the results of Sections 3 and 6 to find formulas for cycle structure after $`(\stackrel{}{\alpha },\stackrel{}{\beta },\gamma )`$ shuffles; for instance it is proved that after such a shuffle on a deck of size $`n`$, the expected number of fixed points is the sum of the first $`n`$ extended power sum symmetric functions evaluated at the relevant parameters. An upper bound on the convergence rate of these shuffles is derived. Section 7 closes with a discussion of convolutions of top to random shuffles, and remarks that for sufficiently large $`n`$, $`5/6log_2(n)+c`$ 2-riffle shuffles bring the longest increasing subsequence to its limit distribution.

## 2 Background

This section collects the facts from symmetric function theory which will be needed later. Chapter 1 of \[Mac\] is a superb introduction to symmetric functions. We review a few essentials here.

The power sum symmetric functions $`p_\lambda `$ are an orthogonal basis of the ring of symmetric functions. Letting $`z_\lambda =_ii^{n_i}n_i!`$ be the centralizer size of the conjugacy of $`S_n`$ indexed by the partition $`\lambda `$ with $`n_i`$ parts of size $`i`$, one has that

$$p_\lambda ,p_\mu =\delta _{\lambda \mu }z_\lambda .$$

The descent set of a permutation $`w`$ is defined as the set of $`i`$ with $`1in1`$ such that $`w(i)>w(i+1)`$; the ascent set is the set of $`i`$ with $`1in1`$ such that $`w(i)<w(i+1)`$. The descent set of a standard Young tableau $`T`$ is the set of $`i`$ such that $`i+1`$ is in a lower row of $`T`$ than $`i`$. The RSK correspondence (carefully exposited in \[Sa\],\[SVol2\]) associates to a permutation $`w`$ a pair of standard Young tableau (its insertion tableau $`P(w)`$ and its recording tableau $`Q(w)`$) and the descent set of $`w`$ is equal to the descent set of $`Q(w)`$. Further the descent set of $`w^1`$ is equal to the descent set of $`P(w)`$, since $`Q(w^1)=P(w)`$. Des$`(w)`$ and Asc$`(w)`$ will denote the descent and ascent set of $`w`$ respectively. The notation $`\lambda n`$ means that $`\lambda `$ is a partition of $`n`$. The symbol $`f_\lambda `$ denotes the number of standard Young tableau of shape $`\lambda `$.

The following result is a simple consequence of work of Gessel and Reutenauer \[GR\] and Garsia \[Gar\].

###### Theorem 1

Let $`\beta _\lambda (D)`$ be the number of standard Young tableau of shape $`\lambda `$ with descent set $`D`$. Let $`N_i(w)`$ be the number of $`i`$-cycles of a permutation $`w`$. Then

1. $$\underset{\genfrac{}{}{0pt}{}{wS_n}{Des(w)=D}}{}\underset{i1}{}x_i^{N_i(w)}=\underset{\lambda n}{}s_\lambda (y)\beta _\lambda (D),\underset{i,j1}{}e^{\frac{x_i^j}{ij}_{d|i}\mu (d)p_{jd}(y)^{i/d}}$$
2. $$\underset{\genfrac{}{}{0pt}{}{wS_n}{Asc(w)=D}}{}\underset{i1}{}x_i^{N_i(w)}=\underset{\lambda n}{}s_\lambda ^{}(y)\beta _\lambda (D),\underset{i,j1}{}e^{\frac{x_i^j}{ij}_{d|i}\mu (d)p_{jd}(y)^{i/d}}.$$

Proof: The number of $`w`$ in $`S_n`$ with descent set $`D`$ and $`n_i`$ $`i`$-cycles is the coefficient of $`_ix_i^{N_i(w)}`$ on the left hand side of the first equation. Let $`\tau `$ be the partition with $`n_i`$ parts of size $`i`$ and let Lie$`{}_{\tau }{}^{}(y)`$ be the symmetric function associated with the corresponding Lie character (for background on Lie characters and relevant symmetric function theory see \[R\]). By \[GR\], the number of $`w`$ in $`S_n`$ with descent set $`D`$ and $`n_i`$ $`i`$-cycles is equal to the inner product

$$\underset{\lambda n}{}s_\lambda (y)\beta _\lambda (D),Lie_\tau (y).$$

From \[Gar\] it follows that Lie$`{}_{\tau }{}^{}(y)`$ is the coefficient of $`_ix_i^{n_i}`$ in

$$\underset{i,j1}{}e^{\frac{x_i^j}{ij}_{d|i}\mu (d)p_{jd}(y)^{i/d}}.$$

This proves the first assertion.

For the second assertion, note that $`\beta _\lambda ^{}(D)=\beta _\lambda (\{1,\mathrm{},n1\}D)`$. This follows from the fact that if a permutation $`w`$ has RSK shape $`\lambda `$ and descent set $`D`$, then its reversal has RSK shape $`\lambda ^{}`$ and ascent set $`D`$. Thus

$`{\displaystyle \underset{\lambda n}{}}s_\lambda ^{}(y)\beta _\lambda (D),{\displaystyle \underset{i,j1}{}}e^{\frac{x_i^j}{ij}_{d|i}\mu (d)p_{jd}(y)^{i/d}}`$
$`=`$ $`{\displaystyle \underset{\lambda n}{}}s_\lambda (y)\beta _\lambda (\{1,\mathrm{},n1\}D),{\displaystyle \underset{i,j1}{}}e^{\frac{x_i^j}{ij}_{d|i}\mu (d)p_{jd}(y)^{i/d}}`$
as desired. $`\mathrm{}`$

## 3 Biased riffle shuffles

We emphasize from the start that the main result in this subsection is not new: it is equivalent to assertions proved in \[F1\] and then in work of Stanley \[Sta\]. It was first proved for ordinary riffle shuffles in \[DMP\]. The value of the current argument is that it underscores the role of RSK and the Cauchy identity

$$\underset{\lambda }{}s_\lambda (x)s_\lambda (y)=\underset{\lambda }{}\frac{1}{z_\lambda }p_\lambda (x)p_\lambda (y)$$

(the sums are over all partitions of all natural numbers).

Biased riffle shuffles were introduced in \[DFP\] and studied further in \[F1\]. A biased riffle shuffle with parameters $`\stackrel{}{q}=(q_1,q_2,\mathrm{})`$ where $`q_i=1`$ is defined as follows. First cut the deck into piles of sizes $`k_1,k_2,\mathrm{}`$ by picking the $`k`$’s according to the distribution

$$\left(\genfrac{}{}{0pt}{}{n}{k_1,k_2,\mathrm{}}\right)\underset{i}{}q_i^{k_i}.$$

Now drop cards from the packets one at a time, according to the rule that at each stage the probability of dropping from a packet is proportional to the number of cards in that packet. For instance if there are 2 packets with sizes $`3`$ and $`5`$, then the next card would come from the first packet with probability $`3/8`$. It is not hard to see that the probability that a biased riffle shuffle gives a permutation $`w`$ depends on $`w`$ only through Des$`(w^1)`$. The main case of interest is $`q_1=\mathrm{}=q_k=1/k`$ all other $`q_i=0`$ and corresponds to ordinary riffle shuffles \[BayD\].

To determine the cycle structure after a biased riffle shuffle we could make use of the following result of Stanley \[Sta\].

###### Theorem 2

Let $`w`$ be distributed as a biased riffle shuffle with parameters $`\stackrel{}{q}`$. Let $`T`$ be a standard Young tableau of shape $`\lambda `$. Then the probability that the RSK algorithm associates insertion tableau $`T`$ to $`w`$ is equal to $`s_\lambda (\stackrel{}{q})`$.

Instead (to simplify later sections) we will use the following similar result, which we record for completeness.

###### Theorem 3

Let $`w`$ be distributed as a biased riffle shuffle with parameters $`\stackrel{}{q}`$. Let $`T`$ be a standard Young tableau of shape $`\lambda `$. Then the probability that the RSK algorithm associates recording tableau $`T`$ to $`w`$ is equal to $`s_\lambda (\stackrel{}{q})`$.

Proof: Given a length $`n`$ word $`J`$ on the symbols $`\{1,\mathrm{},k\}`$, let $`a_i`$ be the number of occurrences of symbol $`i`$ in $`J`$ respectively. Define a permutation $`w`$ in two line form by putting $`1,\mathrm{},a_1`$ in the positions occupied by the $`1`$’s of $`J`$ from left to right, then putting the next $`a_2`$ numbers in the positions occupied by the $`2`$’s of $`J`$ from left to right, and so on. For instance the word

$$\mathrm{1\; 3\; 2\; 1\; 2\; 2\; 1\; 3\; 1\; 2}$$

corresponds to the permutation

$$\mathrm{1\; 9\; 5\; 2\; 6\; 7\; 3\; 10\; 4\; 8}.$$

It is easy to see that in general the recording tableau of $`w`$ under the RSK algorithm is equal to the recording tableau of $`J`$ under the RSK algorithm. Arguing as in \[BayD\], if the entries of the random word $`J`$ are chosen independently with probability $`q_i`$ of symbol $`i`$, then the resulting distribution on permutations $`w`$ is the same as performing a $`\stackrel{}{q}`$ biased riffle shuffle. As in \[KV\], the combinatorial definition of the Schur function immediately implies that the chance that $`J`$ has recording tableau $`T`$ is $`s_\lambda (\stackrel{}{q})`$. $`\mathrm{}`$

Lemma 1 could be simplified via Theorem 2 but we prefer not to take this path.

###### Lemma 1

Let $`\beta _\lambda (D)`$ be the number of standard Young tableau of shape $`\lambda `$ with descent set $`D`$. If $`\beta _\lambda (D)0`$, then the probability that a biased $`\stackrel{}{q}`$-shuffle produces a permutation $`w`$ with Des$`(w^1)=D`$ and RSK shape $`\lambda `$ is equal to the probability that a biased $`\stackrel{}{q}`$-shuffle produces a permutation with $`(P,Q)`$ tableaux satisfying Des$`(P(w))=D`$,shape$`(Q(w))=\lambda `$ divided by $`\beta _\lambda (D)f_\lambda `$.

Proof: Fix any permutation $`w`$ such that Des$`(w^1)=D`$ and such that $`w`$ has RSK shape $`\lambda `$ (this is possible if $`\beta _\lambda (D)0`$). Let $`x`$ be the probability of obtaining $`w`$ after a biased $`\stackrel{}{q}`$ shuffle. Since all $`w`$ with Des$`(w^1)=D`$ are equally likely, $`x=y/z`$ where $`y`$ is the probability that a biased $`\stackrel{}{q}`$ shuffle leads to a permutation with inverse descent set $`D`$ and RSK shape $`\lambda `$, and $`z`$ is the number of permutations with inverse descent set $`D`$ and RSK shape $`\lambda `$. Now $`y`$ is the probability that after a biased $`\stackrel{}{q}`$ shuffle one obtains a permutation $`w`$ with Des$`(P(w))=D`$, shape$`(Q(w))=\lambda `$. Note that $`z`$ is simply $`\beta _\lambda (D)f_\lambda `$, since the insertion tableau can be any standard Young tableau of shape $`\lambda `$ and descent set $`D`$, and the recording tableau can be any standard Young tableau of shape $`\lambda `$. $`\mathrm{}`$

Now we prove the main result in this subsection.

###### Theorem 4

Let $`E_{n,\stackrel{}{q}}`$ denote expected value under the biased riffle shuffle measure with parameters $`\stackrel{}{q}`$. Let $`N_i(w)`$ be the number of $`i`$-cycles of the permutation $`w`$. Then

$$\underset{n0}{}u^nE_{n,\stackrel{}{q}}(\underset{i}{}x_i^{N_i})=\underset{i,j}{}e^{\frac{(u^ix_i)^j}{ij}_{d|i}\mu (d)p_{jd}(\stackrel{}{q})^{i/d}}.$$

Proof: Let $`w`$ be a fixed permutation such that Des$`(w^1)=D`$; then Prob$`{}_{\stackrel{}{q}}{}^{}(D)`$ will denote the probability of obtaining $`w`$ after a biased riffle shuffle with parameters $`\stackrel{}{q}`$. Using part 1 of Theorem 1 one concludes that the sought cycle index is

$`{\displaystyle \underset{n0}{}}u^nE_{n,\stackrel{}{q}}({\displaystyle \underset{i}{}}x_i^{N_i})`$
$`=`$ $`{\displaystyle \underset{n0}{}}u^n{\displaystyle \underset{n_i0}{}}({\displaystyle \underset{i}{}}x_i^{n_i}){\displaystyle \underset{D\{1,\mathrm{},n1\}}{}}Prob_\stackrel{}{q}(D)|\{w:Des(w)=D,N_i(w)=n_i\}|`$
$`=`$ $`{\displaystyle \underset{n0}{}}{\displaystyle \underset{D\{1,\mathrm{},n1\}}{}}Prob_\stackrel{}{q}(D){\displaystyle \underset{\lambda n}{}}s_\lambda (y)\beta _\lambda (D),{\displaystyle \underset{i,j1}{}}e^{\frac{(u^ix_i)^j}{ij}_{d|i}\mu (d)p_{jd}(y)^{i/d}}`$
$`=`$ $`{\displaystyle \underset{n0}{}}{\displaystyle \underset{\lambda n}{}}s_\lambda (y){\displaystyle \underset{D\{1,\mathrm{},n1\}}{}}Prob_\stackrel{}{q}(D)\beta _\lambda (D),{\displaystyle \underset{i,j1}{}}e^{\frac{(u^ix_i)^j}{ij}_{d|i}\mu (d)p_{jd}(y)^{i/d}}`$
Lemma 1 implies that

$$\underset{D\{1,\mathrm{},n1\}}{}Prob_\stackrel{}{q}(D)\beta _\lambda (D)$$

is $`\frac{1}{f_\lambda }`$ multiplied by the probability that the recording tableau of a permutation obtained after a biased $`\stackrel{}{q}`$ shuffle has shape $`\lambda `$. By Theorem 3, this latter probability is $`s_\lambda (\stackrel{}{q})f_\lambda `$. Hence the sought cycle index is simply the inner product

$$\underset{\lambda }{}s_\lambda (y)s_\lambda (\stackrel{}{q}),\underset{i,j1}{}e^{\frac{(u^ix_i)^j}{ij}_{d|i}\mu (d)p_{jd}(y)^{i/d}}.$$

Applying the Cauchy identity yields

$$\underset{\lambda }{}\frac{1}{z_\lambda }p_\lambda (y)p_\lambda (\stackrel{}{q}),\underset{i,j1}{}e^{\frac{(u^ix_i)^j}{ij}_{d|i}\mu (d)p_{jd}(y)^{i/d}}.$$

Since $`p_\lambda ,p_\mu =\delta _{\lambda ,\mu }z_\lambda `$ this simplifies to

$$\underset{i,j1}{}e^{\frac{(u^ix_i)^j}{ij}_{d|i}\mu (d)p_{jd}(\stackrel{}{q})^{i/d}}.$$

$`\mathrm{}`$

We remark that for $`k`$-riffle shuffles the cycle index simplifies to

$$\underset{i1}{}(\frac{1}{1\frac{u^ix_i}{k^i}})^{\frac{1}{i}_{d|i}\mu (d)k^{i/d}}.$$

## 4 Dealing from the Bottom of the Deck

This section considers cycle structure of a biased riffle shuffle followed by dealing from the bottom of the deck. This is equivalent to turning the deck upside down after shuffling. (Persi Diaconis points out that someone running card guessing experiments might do this). The results in this section are all new. Results about subsequence structure are omitted since reversing the order of a permutation simply transposes its RSK shape.

Let $`\lambda ^{}`$ denote the transpose of $`\lambda `$. Let $`l(\lambda )`$ be the number of parts of $`\lambda `$ and let $`ϵ_\lambda `$ denote $`(1)^{|\lambda |l(\lambda )}`$. Whereas the previous subsection used the Cauchy identity, this subsection uses the dual Cauchy identity

$$\underset{\lambda }{}s_\lambda ^{}(x)s_\lambda (y)=\underset{\lambda }{}\frac{ϵ_\lambda }{z_\lambda }p_\lambda (x)p_\lambda (y)$$

(the sums are over all partitions of all natural numbers).

###### Theorem 5

Let $`E_{n,\stackrel{}{q}}^{}`$ denote expected value under the biased riffle shuffle measure with parameters $`\stackrel{}{q}`$ followed by reversing the order of the cards. Then

$$\underset{n0}{}u^nE_{n,\stackrel{}{q}}^{}(\underset{i}{}x_i^{N_i})=\underset{i,j}{}e^{\frac{((u)^ix_i)^j}{ij}_{d|i}\mu (d)(p_{jd}(\stackrel{}{q}))^{i/d}}.$$

Proof: Let $`w`$ be a fixed permutation such that Asc$`(w^1)=D`$; then Prob$`{}_{\stackrel{}{q}}{}^{}(D)`$ will denote the probability of obtaining $`w`$ after a $`\stackrel{}{q}`$ biased riffle shuffle followed by reversing the order of the cards.

Using part 2 of Theorem 1 one concludes that the sought cycle index is

$`{\displaystyle \underset{n0}{}}u^nE_{n,\stackrel{}{q}}^{}({\displaystyle \underset{i}{}}x_i^{N_i})`$
$`=`$ $`{\displaystyle \underset{n0}{}}u^n{\displaystyle \underset{n_i0}{}}({\displaystyle \underset{i}{}}x_i^{n_i}){\displaystyle \underset{D\{1,\mathrm{},n1\}}{}}Prob_\stackrel{}{q}^{}(D)|\{w:Asc(w)=D,N_i(w)=n_i\}|`$
$`=`$ $`{\displaystyle \underset{n0}{}}{\displaystyle \underset{D\{1,\mathrm{},n1\}}{}}Prob_\stackrel{}{q}^{}(D){\displaystyle \underset{\lambda n}{}}s_\lambda ^{}(y)\beta _\lambda (D),{\displaystyle \underset{i,j1}{}}e^{\frac{(u^ix_i)^j}{ij}_{d|i}\mu (d)p_{jd}(y)^{i/d}}`$
$`=`$ $`{\displaystyle \underset{n0}{}}{\displaystyle \underset{\lambda n}{}}s_\lambda ^{}(y){\displaystyle \underset{D\{1,\mathrm{},n1\}}{}}Prob_\stackrel{}{q}^{}(D)\beta _\lambda (D),{\displaystyle \underset{i,j1}{}}e^{\frac{(u^ix_i)^j}{ij}_{d|i}\mu (d)p_{jd}(y)^{i/d}}.`$
From the proof of Theorem 4,

$$\underset{D\{1,\mathrm{},n1\}}{}Prob_\stackrel{}{q}^{}(D)\beta _\lambda (D)=\underset{D\{1,\mathrm{},n1\}}{}Prob_\stackrel{}{q}(D)\beta _\lambda (D)=s_\lambda (\stackrel{}{q}).$$

Consequently the sought cycle index is simply the inner product

$$\underset{\lambda }{}s_\lambda ^{}(y)s_\lambda (\stackrel{}{q}),\underset{i,j1}{}e^{\frac{(u^ix_i)^j}{ij}_{d|i}\mu (d)p_{jd}(y)^{i/d}}.$$

Applying the dual Cauchy identity yields

$$\underset{\lambda }{}\frac{ϵ_\lambda }{z_\lambda }p_\lambda (y)p_\lambda (\stackrel{}{q}),\underset{i,j1}{}e^{\frac{(u^ix_i)^j}{ij}_{d|i}\mu (d)p_{jd}(y)^{i/d}}.$$

Since $`p_\lambda ,p_\mu =\delta _{\lambda ,\mu }z_\lambda `$ this simplifies to

$$\underset{i,j1}{}e^{\frac{(u^ix_i)^j}{ij}_{d|i}\mu (d)(1)^{jii/d}p_{jd}(\stackrel{}{q})^{i/d}}.$$

$`\mathrm{}`$

The case of most interest is $`q_1=\mathrm{}=q_k=\frac{1}{k}`$ and all other $`q_i=0`$. Then the cycle index simplifies to

$$\underset{i1}{}(\frac{1}{1\frac{(u)^ix_i}{k^i}})^{\frac{1}{i}_{d|i}\mu (d)(k)^{i/d}}.$$

Much information can be gleaned from this cycle index in analogy with results in \[DMP\] for ordinary riffle shuffles (i.e. when one deals from the top of the deck). We record three such results which are perhaps the the most interesting.

###### Corollary 1

The expected number of fixed points after a $`k`$-riffle shuffle on n cards followed by reversing the order of the cards is

$$1\frac{1}{k}+\frac{1}{k^2}\mathrm{}+\frac{(1)^{n1}}{k^{n1}}.$$

Proof: The generating function for fixed points is given by setting $`x_i=1`$ for all $`i>1`$ in the cycle index. This yields

$$(1+x_1u/k)^k\underset{i1}{}(\frac{1}{1\frac{(u)^i}{k^i}})^{\frac{1}{i}_{d|i}\mu (d)(k)^{i/d}}.$$

Multiplying and dividing by $`(1+u/k)^k`$ gives

$$\frac{(1+x_1u/k)^k}{(1+u/k)^k}\underset{i}{}(\frac{1}{1\frac{(u)^i}{k^i}})^{\frac{1}{i}_{d|i}\mu (d)(k)^{i/d}}.$$

Observe that

$$\frac{1}{1u}=\underset{i1}{}(\frac{1}{1\frac{(u)^i}{k^i}})^{\frac{1}{i}_{d|i}\mu (d)(k)^{i/d}}$$

since this is what one obtains by setting all $`x_i=1`$ in the cycle index. Hence the generating function for fixed points is

$$\frac{(1+x_1u/k)^k}{(1+u/k)^k(1u)}.$$

Then one differentiates with respect to $`x_1`$, sets $`x_1=1`$, and takes the coefficient of $`u^n`$. $`\mathrm{}`$

We remark that \[DMP\] showed that the expected number of fixed points for $`k`$-riffle shuffles on an n-card deck is

$$1+\frac{1}{k}+\frac{1}{k^2}\mathrm{}+\frac{1}{k^{n1}}.$$

It is straightforward to compute higher moments for $`k`$ shuffles followed by reversal.

The next goal is to determine the limit behavior of the distributions of the short cycles. The answer differs considerably from the GSR riffle shuffle case, in which only convolutions of geometric distributions come into play.

We require a simple lemma.

###### Lemma 2

If $`f(u)`$ has a Taylor series $`_{n0}a_nu^n`$ which converges at $`u=1`$, then the $`n\mathrm{}`$ limit of the coefficient of $`u^n`$ in $`\frac{f(u)}{1u}`$ is $`f(1)`$.

Proof: This follows because the coefficient of $`u^n`$ in $`\frac{f(u)}{1u}`$ is $`a_0+\mathrm{}+a_n`$. $`\mathrm{}`$

###### Corollary 2

1. Fix $`u`$ such that $`0<u<1`$. Choose a random deck size with probability of getting $`n`$ equal to $`(1u)u^n`$. Let $`N_i(w)`$ be the number of $`i`$-cycles of $`w`$ distributed as the reversal of a $`k`$ riffle shuffle. Then the random variables $`N_i`$ are independent, where $`N_i`$ ($`i`$ odd) is the convolution of $`\frac{1}{i}_{d|i}\mu (d)k^{i/d}`$ many binomials with parameter $`u^i/(k^i+u^i)`$ and $`N_i`$ ($`i`$ even) is the convolution of $`\frac{1}{i}_{d|i}\mu (d)(k)^{i/d}`$ many geometrics with parameter $`u^i/k^i`$.
2. Let $`N_i(w)`$ be the number of $`i`$-cycles of $`w`$ distributed as the reversal of a $`k`$ riffle shuffle. Then as $`n\mathrm{}`$ the random variables $`N_i`$ converge in finite dimensional distribution to independent random variables, where $`N_i`$ ($`i`$ odd) becomes the convolution of $`\frac{1}{i}_{d|i}\mu (d)k^{i/d}`$ many binomials with parameter $`1/(k^i+1)`$ and $`N_i`$ ($`i`$ even) becomes the convolution of $`\frac{1}{i}_{d|i}\mu (d)(k)^{i/d}`$ many geometrics with parameter $`1/k^i`$.

Proof: As noted after Theorem 5, the cycle index of a $`k`$-shuffle followed by reversing the order of the cards is

$$\underset{i1}{}(\frac{1}{1\frac{(u)^ix_i}{k^i}})^{\frac{1}{i}_{d|i}\mu (d)(k)^{i/d}}.$$

The proof of Corollary 1 gives that

$$\frac{1}{1u}=\underset{i1}{}(\frac{1}{1\frac{(u)^i}{k^i}})^{\frac{1}{i}_{d|i}\mu (d)(k)^{i/d}}.$$

Dividing these equations implies that

$`{\displaystyle \underset{n0}{}}(1u)u^nE_{n,1/k,\mathrm{},1/k}^{}({\displaystyle \underset{i}{}}x_i^{N_i})`$
$`=`$ $`{\displaystyle \underset{iodd}{}}({\displaystyle \frac{1+u^ix_i/k^i}{1+u^i/k^i}})^{1/i_{d|i}\mu (d)k^{i/d}}{\displaystyle \underset{ieven}{}}({\displaystyle \frac{1u^i/k^i}{1u^ix_i/k^i}})^{1/i_{d|i}\mu (d)(k)^{i/d}}.`$
This proves the first assertion of the theorem. The second assertion follows from dividing both sides of this equation by $`1u`$ and applying Lemma 2. (Note that if all but finitely many $`x_i=1`$, only finitely many terms in the generating function remain. Since $`k2`$ the Taylor series converges at $`u=1`$ provided that the remaining $`x`$’s aren’t too much larger than 1). $`\mathrm{}`$

Finally we observe (Corollary 3) that the distribution of the large cycles is the same as for random permutations (in contrast to the case of small cycles). One can guess this heuristically from the generating function since the large $`i`$ terms of the cycle index converge to those of random permutations. The same happens for ordinary riffle shuffles (Proposition 5.5 of \[DMP\]). The distribution of large cycles in random permutations has been broadly studied (\[VS\] and the references therein).

###### Corollary 3

Fix $`k`$ and let $`L_1,\mathrm{},L_r`$ be the lengths of the $`r`$ longest cycles of $`\pi `$. Then for $`k`$ fixed, or growing with $`n`$ as $`n\mathrm{}`$,

$$|Prob_{n,1/k,\mathrm{},1/k}^{}(L_1/nt_1,\mathrm{},L_r/nt_r)Prob_{S_n}(L_1/nt_1,\mathrm{}L_r/nt_r)|0$$

uniformly in $`t_1,\mathrm{},t_r`$. (Here $`Prob_{S_n}`$ denotes the uniform distribution on $`S_n`$).

Proof: Given the cycle index for k-shuffles followed by a reversal, this follows from minor modifications of either the arguments in \[Hans\] or \[ABT\]. $`\mathrm{}`$

## 5 Unimodal Permutations and a Variation of the RSK Correspondence

One goal of this section is to understand cycle structure after shuffling by the following method.

Generalized Shuffling Method on $`C_n`$

Step 1: Start with a deck of $`n`$ cards face down. Let $`0y_1,\mathrm{},y_k1`$ be such that $`y_i=1`$. Choose numbers $`j_1,\mathrm{},j_{2k}`$ multinomially with the probability of getting $`j_1,\mathrm{},j_{2k}`$ equal to $`\left(\genfrac{}{}{0pt}{}{n}{j_1,\mathrm{},j_{2k}}\right)_{i=1}^ky_i^{j_{2i1}+j_{2i}}`$. Make $`2k`$ stacks of cards of sizes $`j_1,\mathrm{},j_{2k}`$ respectively. Flip over the even numbered stacks.

Step 2: Drop cards from packets with probability proportional to packet size at a given time. Equivalently, choose uniformly at random one of the $`\left(\genfrac{}{}{0pt}{}{n}{j_1,\mathrm{},j_{2k}}\right)`$ interleavings of the packets.

Cycle structure of this model of shuffling was analyzed for equal $`y`$ in \[F4\]. (Actually there one flipped over the odd numbered piles, but this has no effect on the cycle index as the resulting sums in the group algebra are conjugate by the longest element in $`S_n`$. By a result of Sch$`\ddot{u}`$tzenberger exposited as Theorem A1.2.10 in \[SVol2\], conjugation by the longest element also has no effect on RSK shape). The model was introduced for $`k=1`$ (and thus $`y_1=1`$) in \[BayD\]. Let $`E_{n,\stackrel{}{y}}^{}`$ be expectation on $`C_n`$ after the above shuffling method. Let $`N_i(w)`$ be the number of $`i`$-cycles of $`w`$ in $`C_n`$, disregarding signs. It is proved in \[F4\] that

###### Theorem 6

$`1+{\displaystyle \underset{n1}{}}u^n{\displaystyle \underset{wC_n}{}}E_{n,\frac{1}{k},\mathrm{},\frac{1}{k}}^{}({\displaystyle \underset{i1}{}}x_i^{N_i(w)})`$
$`=`$ $`{\displaystyle \underset{m1}{}}({\displaystyle \frac{1+x_mu^m/(2k)^m}{1x_mu^m/(2k)^m}})^{\frac{1}{2m}_{\genfrac{}{}{0pt}{}{d|m}{dodd}}\mu (d)(2k)^{\frac{m}{d}}}.`$
As the paper \[F4\] did not discuss asymptotics of long cycles, before proceeding we note the following corollary, whose proof method is the same as that of Corollary 3.

###### Corollary 4

Fix $`k`$ and let $`L_1,\mathrm{},L_r`$ be the lengths of the $`r`$ longest cycles of $`\pi `$. Then for $`k`$ fixed, or growing with $`n`$ as $`n\mathrm{}`$,

$$|Prob_{n,1/k,\mathrm{},1/k}^{}(L_1/nt_1,\mathrm{},L_r/nt_r)Prob_{S_n}(L_1/nt_1,\mathrm{}L_r/nt_r)|0$$

uniformly in $`t_1,\mathrm{},t_r`$. (Here $`Prob_{S_n}`$ denotes the uniform distribution on $`S_n`$).

A generalization of Theorem 6 will be proved later in this section. To this end, we require the following variation of the RSK correspondence.

Variation of the RSK Correspondence: Order the set of numbers $`\{\pm 1,\mathrm{},\pm k\}`$ by

$$1<1<2<2\mathrm{}<k<k.$$

Given a word on these symbols, run the RSK algorithm as usual, with the amendments that a symbol $`i`$ can’t bump another $`i`$ if $`i`$ is positive, but must bump another $`i`$ if $`i`$ is negative. (This guarantees that positive numbers appear at most once in each column and that negative numbers appear at most once in each row).

For example the word

$$1\mathrm{1\; 2}\mathrm{2\; 1\; 1}\mathrm{1\; 1\; 2\; 2}\mathrm{1\; 2}2$$

has insertion tableau $`P`$ and recording tableau $`Q`$ respectively equal to

$$\begin{array}{ccccccccccc}& & & 1& 1& 1& 1& 1& 2& 2& 2\\ & & & 1& 2& 2& & & & & \\ & & & 1& 2& & & & & & \end{array}$$

$$\begin{array}{ccccccccccc}& & & 1& 2& 3& 4& 9& 10& 12& 13\\ & & & 5& 6& 7& & & & & \\ & & & 8& 11& & & & & & \end{array}$$

The proof of Theorem 7 runs along the same lines as the proof of the RSK correspondence as presented in \[Sa\]. Hence we omit the details.

###### Theorem 7

Order the set of numbers $`\{\pm 1,\mathrm{},\pm k\}`$ by

$$1<1<2<2\mathrm{}<k<k.$$

Then the above variation on the RSK Correspondence is a bijection between length $`n`$ words on the symbols $`\{\pm 1,\mathrm{},\pm k\}`$ and pairs $`(P,Q)`$ where

1. $`P`$ is a tableau on the symbols $`\{\pm 1,\mathrm{},\pm k\}`$ satisfying $`P(a,b)P(a+1,b)`$, $`P(a,b)P(a,b+1)`$ for all $`a,b`$ where $`P(a,b)`$ denotes the entry in the $`a`$th row and $`b`$th column of $`P`$.
2. If $`i`$ is positive then it appears at most once in each column of $`P`$ and if $`i`$ is negative then it appears at most once in each row of $`P`$.
3. $`Q`$ is a standard Young tableau on the symbols $`\{1,\mathrm{},n\}`$.
4. $`P`$ and $`Q`$ have the same shape.

The next result relates the shuffling model of this section with the above variation of the RSK correspondence. For its statement, $`S_\lambda `$ will denote the symmetric functions studied in \[Stem\] (a special case of the extended Schur functions in \[KV\]). One definition of the $`S_\lambda `$ is as the determinant

$$S_\lambda (y)=det(q_{\lambda _ii+j})$$

where $`q_r=0`$ for $`r>0`$ and for $`r0`$, $`q_r`$ is defined by setting

$$\underset{n0}{}q_nt^n=\underset{i1}{}\frac{1+y_it}{1y_it}.$$

We remark that Theorem 8 gives a simple probabilistic interpretation to $`S_\lambda `$, different from the interpretation in \[KV\].

###### Theorem 8

Let $`w`$ be distributed as a shuffle of this section with parameters $`y_1,\mathrm{},y_k`$ after forgetting about signs. Let $`Q`$ be a standard Young tableau of shape $`\lambda `$. Then the probability that the usual RSK correspondence associates recording tableau $`Q`$ to $`w`$ is equal to $`\frac{1}{2^n}S_\lambda (y_1,\mathrm{},y_k)`$. Consequently the probability that $`w`$ has RSK shape $`\lambda `$ is equal to $`\frac{f_\lambda }{2^n}S_\lambda (y_1,\mathrm{},y_k)`$.

Proof: Given a length $`n`$ word $`J`$ on the symbols $`\{\pm 1,\mathrm{},\pm k\}`$, let $`a_i,b_i`$ be the number of occurrences of the symbol $`i,i`$ in $`J`$ respectively. Define a permutation $`w`$ in two line form by putting $`1,\mathrm{},a_1`$ in the positions occupied by the $`1`$’s of $`J`$ from left to right, then putting the next $`b_1`$ numbers (arranged in decreasing order) in the positions occupied by the $`1`$’s of $`J`$ from left to right, then the next $`a_2`$ numbers (arranged in increasing order) in the positions occupied by the $`2`$’s of $`J`$ from left to right, etc. For instance the word

$$1\mathrm{1\; 2}\mathrm{2\; 1\; 1}\mathrm{1\; 1\; 2\; 2}\mathrm{1\; 2}2$$

corresponds to the permutation

$$\mathrm{1\; 7\; 8\; 13\; 2\; 3\; 6\; 4\; 9\; 10\; 5\; 11\; 12}.$$

If the word entries are chosen independently with $`\pm i`$ having probability $`\frac{y_i}{2}`$, the resulting distribution on permutations is the same as performing a $`\stackrel{}{y}`$ shuffle of this section and forgetting about signs.

It is easy to see that the recording tableau of $`w`$ under the RSK algorithm is equal to the recording tableau of $`J`$ under our variant of the RSK algorithm. Let $`\gamma _i(P)`$ be the number of occurrences of symbol $`i`$ in a tableau $`P`$. By Theorem 7, the probability that $`J`$ has recording tableau $`Q`$ under our variant of RSK is equal to

$$\frac{1}{2^n}\underset{P}{}\underset{i1}{}y_i^{\gamma _i(P)+\gamma _i(P)}$$

where $`P`$ has shape $`\lambda `$ and satisfies conditions 1,2 in Theorem 7. Theorem 9.2b of \[Stem\] shows that this sum is equal to $`\frac{1}{2^n}S_\lambda (y_1,\mathrm{},y_k)`$. $`\mathrm{}`$

As mentioned in the introduction, Theorem 8 is relevant to random matrix theory. This is because the first row in the RSK shape of a random permutation $`w`$ is equal to the length of the longest increasing subsequence of $`w`$ and has asymptotically the same distribution as the largest eigenvalue of a random GUE matrix \[BaiDeJ\]. Studying longest increasing subsequences of $`w`$ distributed as a GSR $`k`$-riffle shuffle amounts to studying the longest weakly increasing subsequences in random length $`n`$ words on $`k`$ symbols, which has also been of interest to random matrix theorists \[Sta, TW\]. What Theorem 8 tells us is that studying longest increasing subsequences of $`w`$ distributed as unsigned type $`C`$ shuffles amounts to studying weakly increasing subsequences in random length $`n`$ words on the symbols $`\{\pm 1,\mathrm{},\pm k\}`$, where $`1<1<\mathrm{}<k<k`$ and the subsequence is not allowed to contain a given negative symbol $`i`$ more than once. For $`k`$ fixed and random length $`n`$ words on the symbols $`\{\pm 1,\mathrm{},\pm k\}`$, roughly half the symbols will be positive, and the negative symbols can in total affect the length of the longest weakly increasing subsequence by at most $`k`$. For example, one obtains the following corollary from the analogous results in \[J\] and \[TW\] for weakly increasing subsequences in random words.

###### Corollary 5

For $`k`$ fixed, the RSK shape after an unsigned $`C_n`$ shuffle with $`y_1=\mathrm{}=y_k=\frac{1}{k}`$ has at most $`k`$ rows and $`k`$ columns. For large $`n`$ the expected value of any of the $`k`$ rows or columns is asymptotic to $`\frac{n}{2k}`$.

We hope in future work to study the fluctuations around this limit shape, and to examine the case when both $`n,k`$ are large.

Theorem 9 determines the generating function for cycle structure after performing the generalized shuffling method on $`C_n`$ with parameters $`y_1,\mathrm{},y_k`$ and forgetting about signs.

###### Theorem 9

Let $`E_{n,\stackrel{}{y}}^{}`$ denote expected value under the generalized shuffling method on $`C_n`$ with parameters $`y_1,\mathrm{},y_k`$ after forgetting signs. As usual, let $`N_i(\pi )`$ be the number of cycles of length $`i`$ of the permutation $`\pi `$. Then

$$\underset{n0}{}u^nE_{n,\stackrel{}{y}}^{}(\underset{i}{}x_i^{N_i})=\underset{i1}{}\underset{jodd}{}e^{\frac{(u^ix_i/2^i)^j}{ij}_{\genfrac{}{}{0pt}{}{d|i}{dodd}}\mu (d)(2p_{jd}(y))^{i/d}}.$$

Furthermore, reversing the order of the cards has no effect on the cycle index.

Proof: Let $`w`$ be a fixed permutation such that Des$`(w^1)=D`$ and let Prob$`{}_{\stackrel{}{y}}{}^{}(D)`$ be the probability of obtaining $`w`$ after a $`\stackrel{}{y}`$ unsigned type $`C`$ shuffle.

Using part 1 of Theorem 1 and the fact that the probability of $`w`$ depends only on $`w`$ through Des$`(w^1)`$, it follows that the sought cycle index is

$`{\displaystyle \underset{n0}{}}u^nE_{n,\stackrel{}{y}}^{}({\displaystyle \underset{i}{}}x_i^{N_i})`$
$`=`$ $`{\displaystyle \underset{n0}{}}u^n{\displaystyle \underset{n_i0}{}}({\displaystyle \underset{i}{}}x_i^{n_i}){\displaystyle \underset{D\{1,\mathrm{},n1\}}{}}Prob_\stackrel{}{y}^{}(D)|\{w:Des(w)=D,N_i(w)=n_i\}|`$
$`=`$ $`{\displaystyle \underset{n0}{}}{\displaystyle \underset{D\{1,\mathrm{},n1\}}{}}Prob_\stackrel{}{y}^{}(D){\displaystyle \underset{\lambda n}{}}s_\lambda (z)\beta _\lambda (D),{\displaystyle \underset{i,j1}{}}e^{\frac{(u^ix_i)^j}{ij}_{d|i}\mu (d)p_{jd}(z)^{i/d}}`$
$`=`$ $`{\displaystyle \underset{n0}{}}{\displaystyle \underset{\lambda n}{}}s_\lambda (z){\displaystyle \underset{D\{1,\mathrm{},n1\}}{}}Prob_\stackrel{}{y}^{}(D)\beta _\lambda (D),{\displaystyle \underset{i,j1}{}}e^{\frac{(u^ix_i)^j}{ij}_{d|i}\mu (d)p_{jd}(z)^{i/d}}.`$
Arguing as in Theorem 4 shows that

$$\underset{D\{1,\mathrm{},n1\}}{}Prob_\stackrel{}{y}^{}(D)\beta _\lambda (D)=\frac{1}{2^n}S_\lambda (y).$$

Thus the sought cycle index is simply the inner product

$$\underset{\lambda }{}s_\lambda (z)S_\lambda (y),\underset{i,j1}{}e^{\frac{(u^ix_i/2^i)^j}{ij}_{d|i}\mu (d)p_{jd}(z)^{i/d}}.$$

Applying the third identity in the introduction (due to Stembridge \[Stem\]) yields

$$\underset{\genfrac{}{}{0pt}{}{\lambda }{allpartsodd}}{}\frac{2^{l_\lambda }}{z_\lambda }p_\lambda (z)p_\lambda (y),\underset{i,j1}{}e^{\frac{(u^ix_i/2^i)^j}{ij}_{d|i}\mu (d)p_{jd}(z)^{i/d}}.$$

Since $`p_\lambda ,p_\mu =\delta _{\lambda ,\mu }z_\lambda `$, this simplifies as desired to

$$\underset{i}{}\underset{jodd}{}e^{\frac{(u^ix_i/2^i)^j}{ij}_{\genfrac{}{}{0pt}{}{d|i}{dodd}}\mu (d)(2p_{jd}(y))^{i/d}}.$$

For the second assertion, Theorem 5 shows that the cycle index after reversing the card order at the end is given by

$$\underset{i}{}\underset{jodd}{}e^{\frac{((u)^ix_i/2^i)^j}{ij}_{\genfrac{}{}{0pt}{}{d|i}{dodd}}\mu (d)(2p_{jd}(y))^{i/d}}.$$

It is easy to see that the $``$ signs all drop out. $`\mathrm{}`$

We remark that in the case of greatest interest ($`y_1=\mathrm{}=y_k=\frac{1}{k}`$, all other $`y_i=0`$), one recovers Theorem 6.

A unimodal permutation $`w`$ on the symbols $`\{1,\mathrm{},n\}`$ is defined by requiring that there is some $`i`$ with $`1in`$ such that the following two properties hold:

1. If $`a<bi`$, then $`w(a)<w(b)`$.
2. If $`ia<b`$, then $`w(a)>w(b)`$.

Thus $`i`$ is where the maximum is achieved, and the permutations $`12\mathrm{}n`$ and $`nn1\mathrm{}1`$ are counted as unimodal. For each fixed $`i`$ there are $`\left(\genfrac{}{}{0pt}{}{n1}{i1}\right)`$ unimodal permutations with maximum $`i`$, hence a total of $`2^{n1}`$ such permutations. As noted in \[Gan\], unimodal permutations are those which avoid the patterns $`213`$ and $`312`$.

Unimodal permutations are the shuffles of this section in the case $`k=1`$ after forgetting about signs; hence Theorem 6 (from \[F4\]) gives a cycle index for unimodal permutations. The paper \[Th\], which appeared in between \[F4\] and this paper, obtained a count of unimodal permutations by cycle structure and position of their maximum, denoted by $`max(w)`$. We prove an equation equivalent to Thibon’s result \[Th\]. The proof uses the notation that $`m_i(\lambda )`$ is the number of parts of $`\lambda `$ of size $`i`$.

###### Theorem 10

Let $`N_i(w)`$ be the number of $`i`$-cycles of a permutation $`w`$.

$$1+\underset{n1}{}u^n(1+t)\underset{wunimodal}{}t^{max(w)1}\underset{i}{}x_i^{N_i(w)}=\underset{i,j}{}e^{\frac{(x_iu^i)^j}{ij}_{d|i}\mu (d)(t^{jd}(1)^{jd})^{i/d}}.$$

Proof: A permutation on $`n`$ symbols is unimodal with maximum at position $`k`$ if and only if it has descent set $`k,k+1,\mathrm{},n1`$. Hence Theorem 1 implies that

$`1+{\displaystyle \underset{n1}{}}u^n(1+t){\displaystyle \underset{wunimodal}{}}t^{max(w)1}{\displaystyle \underset{i}{}}x_i^{N_i(w)}`$
$`=`$ $`1+(1+t){\displaystyle \underset{a,b0}{}}s_{(a+1,1^b)}(z)t^au^{a+b+1},{\displaystyle \underset{i,j1}{}}e^{\frac{x_i^j}{ij}_{d|i}\mu (d)p_{jd}(z)^{i/d}}.`$
This can be further simplified using Macdonald’s identity (page 49 of \[Mac\])

$$1+(t+u)\underset{a,b0}{}s_{(a+1,1^b)}(z)t^au^b=\underset{i1}{}\frac{1+uz_i}{1tz_i}$$

with $`t`$ replaced by $`tu`$ to yield

$`{\displaystyle \underset{i1}{}}{\displaystyle \frac{1+uz_i}{1tuz_i}},{\displaystyle \underset{i,j1}{}}e^{\frac{x_i^j}{ij}_{d|i}\mu (d)p_{jd}(z)^{i/d}}`$
$`=`$ $`e^{_{i1}u^ip_i(z)(t^i(1)^i)/i},{\displaystyle \underset{i,j1}{}}e^{\frac{x_i^j}{ij}_{d|i}\mu (d)p_{jd}(z)^{i/d}}`$
$`=`$ $`{\displaystyle \underset{\lambda }{}}{\displaystyle \frac{p_\lambda (z)u^{|\lambda |}_i(t^i(1)^i)^{m_i(\lambda )}}{z_\lambda }},{\displaystyle \underset{i,j1}{}}e^{\frac{x_i^j}{ij}_{d|i}\mu (d)p_{jd}(z)^{i/d}}`$
$`=`$ $`{\displaystyle \underset{i,j}{}}e^{\frac{(x_iu^i)^j}{ij}_{d|i}\mu (d)(t^{jd}(1)^{jd})^{i/d}}.`$
Note that we have used the identity

$$\underset{i1}{}\frac{1}{1uz_i}=e^{_{i1}p_i(z)u^i/i}.$$

$`\mathrm{}`$

## 6 Extended Schur functions

The extended complete symmetric functions $`\stackrel{~}{h}_k(\alpha ,\beta ,\gamma )`$ are defined by the generating function

$$\underset{k=0}{\overset{\mathrm{}}{}}\stackrel{~}{h}_k(\alpha ,\beta ,\gamma )z^k=e^{\gamma z}\underset{i1}{}\frac{1+\beta _iz}{1\alpha _iz}.$$

For $`\lambda =(\lambda _1,\mathrm{},\lambda _n)`$, the extended Schur functions are defined by

$$\stackrel{~}{s}_\lambda =det(\stackrel{~}{h}_{\lambda _ii+j})_{i,j=1}^n.$$

The extended Schur functions give the characters of the infinite symmetric group and are usefully reviewed in \[O\]. Observe that $`\stackrel{~}{s}_\lambda `$ is obtained from taking the expression for $`s_\lambda `$ as a polynomial in the $`h_k`$ and replacing $`h_k`$ by $`\stackrel{~}{h}_k`$. Defining a homomorphism $`\mathrm{\Phi }`$ on symmetric functions by $`\mathrm{\Phi }(h_k)=\stackrel{~}{h}_k`$, one sees that any identity for ordinary symmetric functions gives a corresponding identity for extended symmetric functions. That is how one derives the Cauchy identity

$$\underset{\lambda }{}s_\lambda (x)\stackrel{~}{s}_\lambda (\alpha ,\beta ,\gamma )=\underset{\lambda }{}\frac{1}{z_\lambda }p_\lambda (x)\stackrel{~}{p}_\lambda (\alpha ,\beta ,\gamma )$$

for extended Schur functions from the usual Cauchy identity (e.g. Example 3.23 of \[Mac\] for the case $`\gamma 0`$).

Since probabilities must be positive, one motivation for interpreting extended Schur functions probabilistically is the following positivity result.

###### Theorem 11

(\[E\]) Let $`G(z)=_{k=0}^{\mathrm{}}g_kz^k`$ be such that $`g_0=1`$ and all $`g_k0`$. Then

$$det(g_{\lambda _ii+j})_{i,j=1}^n0$$

for all partitions $`\lambda `$ if and only if

$$G(z)=e^{\gamma z}\underset{i1}{}\frac{1+\beta _iz}{1\alpha _iz}$$

where $`\gamma 0`$ and $`\beta _i,\alpha _i`$ are convergent series of positive numbers.

Next we define $`(\stackrel{}{\alpha },\stackrel{}{\beta },\gamma )`$ shuffles. We suppose that $`\gamma +\alpha _i+\beta _i=1`$ and that $`\gamma 0`$, $`\alpha _i,\beta _i0`$ for all $`i`$. Using these parameters, we define a random permutation on $`n`$ symbols as follows. First, create a word of length $`n`$ by choosing letters $`n`$ times independently according to the rule that one picks $`i>0`$ with probability $`\alpha _i`$, $`i<0`$ with probability $`\beta _i`$, and $`i=0`$ with probability $`\gamma `$. We use the usual ordering $`\mathrm{}<1<0<1<\mathrm{}`$ on the integers. Starting with the smallest negative symbol which appears in the word, let $`m`$ be the number of times it appears. Then write $`\{1,2,\mathrm{},m\}`$ under its appearances in decreasing order from left to write. If the next negative symbol appears $`k`$ times write $`\{m+1,\mathrm{},m+k\}`$ under its appearances, again in decreasing order from left to write. After finishing with the negative symbols, proceed to the $`0`$’s. Letting $`r`$ be the number of $`0`$’s, choose a random permutation of the relevant $`r`$ consecutive integers and write it under the $`0`$’s. Finally, move to the positive symbols. Supposing that the smallest positive symbol appears $`s`$ times, write the relevant $`s`$ consecutive integers under its appearances in increasing order from left to right.

The best way to understand this procedure is through an example. Given the string

$$\mathrm{2\; 0\; 1\; 0\; 0\; 2}12\mathrm{1\; 1}$$

one obtains each of the six permutations

$$\mathrm{2\; 5\; 8\; 6\; 7\; 10\; 4\; 1\; 3\; 9}$$

$$\mathrm{2\; 5\; 8\; 7\; 6\; 10\; 4\; 1\; 3\; 9}$$

$$\mathrm{2\; 6\; 8\; 5\; 7\; 10\; 4\; 1\; 3\; 9}$$

$$\mathrm{2\; 6\; 8\; 7\; 5\; 10\; 4\; 1\; 3\; 9}$$

$$\mathrm{2\; 7\; 8\; 5\; 6\; 10\; 4\; 1\; 3\; 9}$$

$$\mathrm{2\; 7\; 8\; 6\; 5\; 10\; 4\; 1\; 3\; 9}$$

with probability $`1/6`$. In all cases the $`1,2`$ correspond to the $`2`$’s, the $`3,4`$ correspond to the $`1`$’s, the $`8,9`$ correspond to the $`1`$’s and the $`10`$ corresponds to the $`2`$. The symbols $`5,6,7`$ correspond to the $`0`$’s and there are six possible permutations of these symbols. We call this probability measure on permutations a $`(\stackrel{}{\alpha },\stackrel{}{\beta },\gamma )`$ shuffle.

The following elementary result (generalizing results in \[BayD\] and \[DFP\]) gives physical descriptions of these shuffles and explains how they convolve. The proof method follows that of \[BayD\].

###### Proposition 1

1. A $`(\stackrel{}{\alpha },\stackrel{}{\beta },\gamma )`$ shuffle is equivalent to the following procedure. Cut the $`n`$ card deck into piles with sizes $`X_i`$ indexed by the integers, where the probability of having $`X_i=x_i`$ for all $`i`$ is equal to

$$\frac{n!}{_{i=\mathrm{}}^{\mathrm{}}x_i!}\gamma ^{x_0}\underset{i>0}{}\alpha _i^{x_i}\underset{i<0}{}\beta _i^{x_i}.$$

The top cards go to the non-empty pile with smallest index, the next batch of cards goes to the pile with second smallest index, and so on. Then mix the pile indexed by $`0`$ until it is a random permutation, and turn upside down all of the piles with negative indices. Finally, riffle the piles together as in the first paragraph of the introduction and look at the underlying permutation (i.e. ignore the fact that some cards are upside down).
2. The inverse of a $`(\stackrel{}{\alpha },\stackrel{}{\beta },\gamma )`$ shuffle is equivalent to the following procedure. Randomly label each card of the deck, picking label $`0`$ with probability $`\gamma `$, label $`i>0`$ with probability $`\alpha _i`$ and label $`i<0`$ with probability $`\beta _i`$. Deal cards into piles indexed by the labels, where cards with negative or zero label are dealt face down and cards with positive label are dealt face up. Then mix the pile labeled $`0`$ so that it is a random permutation and turn all of the face up piles face down. Finally pick up the piles by keeping piles with smaller labels on top.
3. Performing a $`(\stackrel{}{\alpha },\stackrel{}{\beta },\gamma )`$ shuffle $`k`$ times is the same as performing the following shuffle. One cuts into piles with labels given by $`k`$-tuples of integers $`(z_1,\mathrm{},z_k)`$ ordered according to the following rule:

1. $`(z_1,\mathrm{},z_k)<(z_1^{},\mathrm{},z_k^{})`$ if $`z_1<z_1^{}`$.
    2. $`(z_1,\mathrm{},z_k)<(z_1^{},\mathrm{},z_k^{})`$ if $`z_1=z_1^{}0`$ and $`(z_2,\mathrm{},z_k)<(z_2^{},\mathrm{},z_k^{})`$.
    3. $`(z_1,\mathrm{},z_k)<(z_1^{},\mathrm{},z_k^{})`$ if $`z_1=z_1^{}<0`$ and $`(z_2,\mathrm{},z_k)>(z_2^{},\mathrm{},z_k^{})`$.

The pile is assigned probability equal to the product of the probabilities of the symbols in the $`k`$ tuple. Then the shuffle proceeds as in part 1, where negative piles (piles where the product of the coordinates of the $`k`$ tuple are negative) are turned upside down and piles with some coordinate equal to 0 are perfectly mixed before the piles are all riffled together.

Examples As an example of Proposition 1, consider an $`(\alpha _1,\alpha _2;\beta _1,\beta _2;\gamma )`$ shuffle with $`n=11`$. For part 1, it may turn out that $`X_2=2`$, $`X_1=1`$, $`X_0=3`$, $`X_1=2`$, and $`X_2=3`$. Then the deck is cut into piles $`\{1,2\}`$, $`\{3\}`$, $`\{4,5,6\}`$, $`\{7,8\}`$, $`\{9,10,11\}`$. The first two piles are turned upside down and the third pile is completely randomized, which might yield piles $`\{2,1\}`$, $`\{3\}`$, $`\{5,4,6\}`$, $`\{7,8\}`$, $`\{9,10,11\}`$. Then these piles are riffled together as in the GSR shuffle. This might yield the permutation

$$\mathrm{5\; 2\; 7\; 4\; 8\; 9\; 10\; 3\; 1\; 11\; 6}.$$

The inverse description (part 2) would amount to labeling cards 2,9 with $`2`$, card 8 with $`1`$, cards 1,4,11 with $`0`$, card 3,5 with $`1`$, and cards 6,7,10 with $`2`$, and then mixing the $`0`$ pile as $`4,1,11`$. Note that this leads to the permutation (inverse to the previous permutation)

$$\mathrm{9\; 2\; 8\; 4\; 1\; 11\; 3\; 5\; 6\; 7\; 10}.$$

As an example of part 3, note that doing a $`(\alpha _1;\beta _1;0)`$ shuffle twice does not give a $`(\stackrel{}{\alpha },\stackrel{}{\beta },\gamma )`$ shuffle, but rather gives a shuffle with 4 piles in the order $`(1,1),(1,1),(1,1),(1,1)`$ where pile 1 has probability $`\beta _1\alpha _1`$, pile 2 has probability $`\beta _1\beta _1`$, pile 3 has probability $`\alpha _1\beta _1`$ and pile 4 has probability $`\alpha _1\alpha _1`$. Piles 1 and 3 are turned upside down before the riffling takes place. From Section 5 of this paper one can still analyze the cycle structure and RSK shape of these shuffles even though they aren’t $`(\stackrel{}{\alpha },\stackrel{}{\beta },\gamma )`$ shuffles. (Actually Section 5 of this paper looked at shuffles conjugate to these shuffles by the longest element; this clearly has no effect on the cycle index and has no effect on the RSK shape by a result of Sch$`\ddot{u}`$tzenberger exposited as Theorem A1.2.10 in \[SVol2\]).

As another example of part 3, note that a shuffle with parameters $`(\alpha _1;0;\gamma )`$ repeated twice gives a shuffle with 4 piles in the order $`(0,0),(0,1),(1,0),(1,1)`$ where the first 3 piles are completely mixed before all piles are riffled together. This is clearly the same as a $`(\alpha _1^2;0;1\alpha _1^2)`$ shuffle, agreeing with Lemma 2.1 of \[DFP\].

Berele and Remmel \[BeRe\] and independently Kerov and Vershik \[KV\] consider the following analog of the RSK Correspondence (different from the variation in Section 5 as the BRKV version uses the standard ordering on the integers). Given a word on the symbols $`\{\pm 1,\pm 2,\mathrm{}\}`$ one runs the RSK correspondence with the amendments that a negative symbol is required to bump itself, but that a positive symbol can’t bump itself. For example the word

$$1\mathrm{1\; 2}\mathrm{2\; 1\; 1}2$$

has insertion tableau $`P`$ and recording tableau $`Q`$ respectively equal to

$$\begin{array}{ccccccccccc}& & & 2& 1& 1& & & & & \\ & & & 2& 2& & & & & & \\ & & & 1& & & & & & & \\ & & & 1& & & & & & & \end{array}$$

$$\begin{array}{ccccccccccc}& & & 1& 3& 6& & & & & \\ & & & 2& 5& & & & & & \\ & & & 4& & & & & & & \\ & & & 7& & & & & & & \end{array}$$

###### Theorem 12

(\[BeRe\],\[KV\]) The above variation on the Robinson-Schensted-Knuth correspondence gives a bijection between words of length $`n`$ from the alphabet of integers with the symbol $`i`$ appearing $`n_i`$ times and pairs $`(P,Q)`$ where

1. The symbol $`i`$ occurs $`n_i`$ times in $`P`$.
2. The entries of $`P`$ are weakly increasing in rows and columns.
3. Each positive symbol occurs at most once in each column of $`P`$ and each negative symbol occurs at most once in each row of $`P`$.
4. $`Q`$ is a standard Young tableau on the symbols $`\{1,\mathrm{},n\}`$.

Furthermore,

$$\stackrel{~}{s}_\lambda (\stackrel{}{\alpha },\stackrel{}{\beta },0)=\underset{\genfrac{}{}{0pt}{}{P}{shape(P)=\lambda }}{}\underset{i>0}{}\alpha _i^{n_i(P)}\underset{i<0}{}\beta _i^{n_i(P)}.$$

Theorem 13 and Corollary 6 connect card shuffling to the extended Schur functions. When $`\alpha =0`$, this result is essentially in \[BeRe\] and \[KV\]. The paper \[KV\] states a version of Theorem 12 in which there is also a parameter $`\gamma `$ (their Proposition 3), but it is incorrect for $`\gamma 0`$ as the following counterexample shows. Setting all parameters other than $`\alpha _1=\alpha `$ and $`\gamma =1\alpha `$ equal to 0, it follows from the definitions that the extended Schur function $`\stackrel{~}{s}_2`$ is equal to $`\frac{\alpha ^2+1}{2}`$. But if Proposition 3 of \[KV\] were correct, it would also equal $`\alpha ^2+(1\alpha )\alpha =\alpha `$ since the two words giving a Young tableau with 1 row of length 2 are $`11`$ and $`01`$. In fact as the $`2`$ in the denominator of $`\frac{\alpha ^2+1}{2}`$ shows, one can’t interpret the extended Schur functions with $`\gamma 0`$ in terms of RSK and words on a finite number of symbols. This accounts for the extra randomization step (choosing a random permutation for the symbols corresponding the 0’s) in our definition of $`(\stackrel{}{\alpha },\stackrel{}{\beta },\gamma )`$ shuffles.

Theorem 13 give a probabilistic interpretation of $`\stackrel{~}{s}_\lambda `$ for all values of $`\gamma `$.

###### Theorem 13

Let $`\pi `$ be distributed as a permutation under a $`(\stackrel{}{\alpha },\stackrel{}{\beta },\gamma )`$ shuffle. Let $`Q`$ be any standard Young tableaux of shape $`\lambda `$. Then the probability that $`\pi `$ has Robinson-Schensted-Knuth recording tableau equal to $`Q`$ is $`\stackrel{~}{s}_\lambda (\stackrel{}{\alpha },\stackrel{}{\beta },\gamma )`$.

Proof: First suppose that $`\gamma =0`$. As indicated earlier in this section, each length $`n`$ word $`w`$ on the symbols $`\{\pm 1,\pm 2,\mathrm{}\}`$ defines a permutation $`\pi `$. From this construction, it is easy to see that the recording tableau of $`w`$ under the BRKV variation of the RSK algorithm is equal to the recording tableau of $`\pi `$ under the RSK algorithm. Thus it is enough to prove that the probability that the word $`w`$ has BRKV recording tableau $`Q`$ is $`\stackrel{~}{s}_\lambda (\stackrel{}{\alpha },\stackrel{}{\beta },0)`$. This is immediate from Theorem 12.

Now the case $`\gamma 0`$ can be handled by introducing $`m`$ extra symbols between $`0`$ and $`1`$–call them $`1/(m+1),2/(m+1),\mathrm{},m/(m+1)`$ and choosing each with probability $`\gamma /m`$. Thus the random word is on $`\{\pm 1,\pm 2,\mathrm{}\}`$ and these extra symbols. Each word defines exactly one permutation–the symbols $`1/(m+1),2/(m+1),\mathrm{},m/(m+1)`$ are treated as positive. By the previous paragraph, the probability of obtaining recording tableau $`Q`$ is equal to $`\stackrel{~}{s}_\lambda (\stackrel{}{\alpha },\stackrel{}{\beta })`$ where the associated $`\stackrel{~}{h}_k`$ are defined by

$$\underset{k=0}{\overset{\mathrm{}}{}}\stackrel{~}{h}_k(\alpha ,\beta )z^k=(\frac{1}{1\gamma z/m})^m\underset{i1}{}\frac{1+\beta _iz}{1\alpha _iz}.$$

As $`m\mathrm{}`$, this distribution on permutations converges to that of a $`(\stackrel{}{\alpha },\stackrel{}{\beta },\gamma )`$ shuffle, and the generating function of the $`\stackrel{~}{h}_k`$ converges to

$$\underset{k=0}{\overset{\mathrm{}}{}}\stackrel{~}{h}_k(\alpha ,\beta ,\gamma )z^k=e^{\gamma z}\underset{i1}{}\frac{1+\beta _iz}{1\alpha _iz}.$$

$`\mathrm{}`$

###### Corollary 6

Let $`f_\lambda `$ be the number of standard Young tableau of shape $`\lambda `$. Let $`\pi `$ be distributed as a permutation under a $`(\stackrel{}{\alpha },\stackrel{}{\beta },\gamma )`$ shuffle. Then the probability that $`\pi `$ has Robinson-Schensted-Knuth shape $`\lambda `$ is equal to $`f_\lambda \stackrel{~}{s}_\lambda (\stackrel{}{\alpha },\stackrel{}{\beta },\gamma )`$.

## 7 Convergence Rates and Cycle Index of $`(\alpha ,\beta ,\gamma )`$ shuffles

First we derive an upper bound on the convergence rate of $`(\stackrel{}{\alpha },\stackrel{}{\beta },\gamma )`$ shuffles to randomness using strong uniform times as in \[DFP\]. The separation distance between a probability $`P(\pi )`$ and the uniform distribution $`U(\pi )`$ is defined as $`max_\pi (1\frac{Q(\pi )}{U(\pi )})`$ and gives an upper bound on total variation distance. Examples of the upper bound of Theorem 14 are considered later.

###### Theorem 14

The separation distance between $`k`$ applications of a $`(\stackrel{}{\alpha },\stackrel{}{\beta },\gamma )`$ shuffle and uniform is at most

$$\left(\genfrac{}{}{0pt}{}{n}{2}\right)\left[\underset{i}{}(\alpha _i)^2+\underset{i}{}(\beta _i)^2\right]^k.$$

Thus $`k=2log_{\frac{1}{_i(\alpha _i)^2+_i(\beta _i)^2}}n`$ steps suffice to get close to the uniform distribution.

Proof: For each $`k`$, let $`A^k`$ be a random $`n\times k`$ matrix formed by letting each entry equal $`i>0`$ with probability $`\alpha _i`$, $`i<0`$ with probability $`\beta _i`$, and $`i=0`$ with probability $`\gamma `$. Let $`T`$ be the first time that all rows of $`A^k`$ containing no zeros are distinct; from the inverse description of $`(\stackrel{}{\alpha },\stackrel{}{\beta },\gamma )`$ shuffles this is a strong uniform time in the sense of Sections 4B-4D of Diaconis \[D1\], since if all cards are cut in piles of size one the permutation resulting after riffling them together is random. The separation distance after $`k`$ applications of a $`(\stackrel{}{\alpha },\stackrel{}{\beta },\gamma )`$ shuffle is upper bounded by the probability that $`T>k`$ \[AD\]. Let $`V_{ij}`$ be the event that rows $`i`$ and $`j`$ of $`A^k`$ are the same and contain no zeros. The probability that $`V_{ij}`$ occurs is $`\left[_i(\alpha _i)^2+_i(\beta _i)^2\right]^k`$. The result follows because

$`Prob(T>k)`$ $`=`$ $`Prob(_{1i<jn})V_{ij}`$
$``$ $`{\displaystyle \underset{1i<jn}{}}Prob(V_{ij})`$
$`=`$ $`\left({\displaystyle \genfrac{}{}{0pt}{}{n}{2}}\right)\left[{\displaystyle \underset{i}{}}(\alpha _i)^2+{\displaystyle \underset{i}{}}(\beta _i)^2\right]^k`$
$`\mathrm{}`$

Taking logarithms of the defining identity for $`\stackrel{~}{h}_k`$, one sees that

$$\stackrel{~}{p}_1(\stackrel{}{\alpha },\stackrel{}{\beta },\gamma )=\underset{i}{}\alpha _i+\underset{i}{}\beta _i+\gamma =1$$

and (for $`n2`$)

$$\stackrel{~}{p}_n(\stackrel{}{\alpha },\stackrel{}{\beta },\gamma )=\underset{i}{}(\alpha _i)^n+(1)^{n+1}\underset{i}{}(\beta _i)^n.$$

Theorem 15 gives a cycle index after $`(\stackrel{}{\alpha },\stackrel{}{\beta },\gamma )`$ shuffles.

###### Theorem 15

1. Let $`E_{n,(\stackrel{}{\alpha },\stackrel{}{\beta },\gamma )}`$ denote expected value after a $`(\stackrel{}{\alpha },\stackrel{}{\beta },\gamma )`$ shuffle of an $`n`$ card deck. Let $`N_i(\pi )`$ be the number of $`i`$-cycles of a permutation $`\pi `$. Then

$$\underset{n0}{}u^nE_{n,(\stackrel{}{\alpha },\stackrel{}{\beta },\gamma )}(\underset{i}{}x_i^{N_i})=\underset{i,j}{}e^{\frac{(u^ix_i)^j}{ij}_{d|i}\mu (d)\stackrel{~}{p}_{jd}(\stackrel{}{\alpha },\stackrel{}{\beta },\gamma )^{i/d}}.$$
2. Let $`E_{n,(\stackrel{}{\alpha },\stackrel{}{\beta },\gamma )}^{}`$ denote expected value after a $`(\stackrel{}{\alpha },\stackrel{}{\beta },\gamma )`$ shuffle of an $`n`$ card deck followed by reversing the order of the cards. Then

$$\underset{n0}{}u^nE_{n,(\stackrel{}{\alpha },\stackrel{}{\beta },\gamma )}^{}(\underset{i}{}x_i^{N_i})=\underset{n0}{}u^nE_{n,(\stackrel{}{\beta },\stackrel{}{\alpha },\gamma )}(\underset{i}{}x_i^{N_i}).$$

Proof: Given the results of Section 6, the proof of the first part runs along exactly the same lines as in the proof of Theorem 4. The second assertion follows from the observation that a $`(\stackrel{}{\alpha },\stackrel{}{\beta },\gamma )`$ shuffle followed by reversing the order of the cards is conjugate (by the longest length element in the symmetric group) to a $`(\stackrel{}{\beta },\stackrel{}{\alpha },\gamma )`$ shuffle. Alternatively, arguing as in the proof of Theorem 5, one sees that the effect of reversing the cards on the cycle index of a $`(\stackrel{}{\alpha },\stackrel{}{\beta },\gamma )`$ shuffle is to get

$$\underset{i,j}{}e^{\frac{((u)^ix_i)^j}{ij}_{d|i}\mu (d)(\stackrel{~}{p}_{jd}(\stackrel{}{\alpha },\stackrel{}{\beta },\gamma ))^{i/d}}.$$

$`\mathrm{}`$

Example 1 As a first application of Theorem 15, we derive an expression for the expected number of fixed points, generalizing the expression in \[DMP\]. To get the generating function for fixed points, one sets $`x_2=x_3=\mathrm{}=1`$ in the cycle index. Using the same trick as in \[DMP\], the generating function simplifies to

$$\frac{1}{1u}\frac{e^{ux\gamma }}{e^{ux}}\underset{i1}{}\frac{1u\alpha _i}{1ux\alpha _i}\frac{1+ux\beta _i}{1+u\beta _i}.$$

Taking the derivative with respect to $`x`$ and the coefficient of $`u^n`$, one sees that the expected number of fixed points is

$$\gamma +\underset{j=1}{\overset{n}{}}[\underset{i}{}(\alpha _i)^j+(1)^{j+1}(\beta _i)^j].$$

This is exactly the sum of the first $`n`$ extended power sum functions at the parameters $`(\stackrel{}{\alpha },\stackrel{}{\beta },\gamma )`$.

Example 2 We suppose that $`\stackrel{}{\beta }=\stackrel{}{0}`$ and that $`\alpha _1=\mathrm{}=\alpha _q=\frac{1\gamma }{q}`$. Then the cycle index simplifies to

$$\underset{i1}{}\left(\frac{1}{1x_i(\frac{u(1\gamma )}{q})^i}\right)^{\frac{1}{i}_{d|i}\mu (d)q^{i/d}}\underset{i1}{}e^{\frac{u^ix_i(1(1\gamma )^i)}{i}}.$$

Of particular interest is the further specialization $`q=1`$. Then the cycle index becomes

$$\frac{1}{1x_1u(1\gamma )}\underset{i1}{}e^{\frac{u^ix_i(1(1\gamma )^i)}{i}}.$$

Recall that a $`(1/2,0,1/2)`$ shuffle takes a binomial(n,1/2) number of cards (a binomial(n,1/2) random variable is equal to $`k`$ with probability $`\left(\genfrac{}{}{0pt}{}{n}{k}\right)/2^n`$), thoroughly mixes them, and then riffles them with the remaining cards. Example 3 on page 140 of \[DFP\] proves (in slightly different notation) that the iteration of $`k`$ (1/2,0,1/2) shuffles is the same as a $`((1/2)^k,0,1(1/2)^k)`$ shuffle. They conclude (in agreement with Theorem 14) that a $`(1/2,0,1/2)`$ shuffle takes $`log_2(n)`$ steps to be mixed, as compared to $`\frac{3}{2}log_2(n)`$ for ordinary riffle shuffles. They also establish a cut-off phenomenon. From the computation of Example 1 one sees that the expected number of fixed points also drops and that the mean mixes twice as fast.

As another example, consider a $`(11/n,0,1/n)`$ shuffle. Heuristically this is like top to random and \[DFP\] proves that the convergence rate is the same ($`nlog(n)`$ steps), which agrees with Theorem 14. From page 139 of \[DFP\], performing a $`(11/n,0,1/n)`$ shuffle $`k`$ times is the same as performing a single $`((11/n)^k,0,1(11/n)^k)`$ shuffle. Example 1 gives a formula for the expected number of fixed points. See Example 4 for more discussion of iterations of top to random shuffles.

Next we consider the asymptotics of cycle structure. As usual, $`\mu `$ denotes the Moebius function of elementary number theory. Note that considerable simplifications take place when $`q=1`$ (the interesting case) because $`_{d|i}\mu (d)`$ is $`1`$ if $`i=1`$ and is $`0`$ otherwise. We omit the details of the proof as they are the same as for the corresponding results in Section 4.

###### Corollary 7

Suppose that $`\stackrel{}{\beta }=\stackrel{}{0}`$ and $`\alpha _1=\mathrm{}=\alpha _q=\frac{1\gamma }{q}`$.

1. Fix $`u`$ such that $`0<u<1`$. Choose a random deck size with probability of getting $`n`$ equal to $`(1u)u^n`$. Let $`N_i(\pi )`$ be the number of $`i`$-cycles of $`\pi `$ distributed as a $`(\stackrel{}{\alpha },\stackrel{}{\beta },\gamma )`$. Then the random variables $`N_i`$ are independent, where $`N_i`$ is the convolution of a Poisson$`((u^i(1(1\gamma )^i))/i)`$ with $`\frac{1}{i}_{d|i}\mu (d)q^{i/d}`$ many geometrics with parameter $`(\frac{u(1\gamma )}{q})^i`$.
2. Let $`N_i(\pi )`$ be the number of $`i`$-cycles of $`\pi `$ distributed as a $`(\stackrel{}{\alpha },\stackrel{}{\beta },\gamma )`$ shuffle. Then as $`n\mathrm{}`$ the random variables $`N_i`$ are independent, where $`N_i`$ is the convolution of a Poisson$`((1(1\gamma )^i)/i)`$ with $`\frac{1}{i}_{d|i}\mu (d)q^{i/d}`$ many geometrics with parameter $`(\frac{1\gamma }{q})^i`$.
3. Fix $`k`$ and let $`L_1,\mathrm{},L_r`$ be the lengths of the $`r`$ longest cycles of $`\pi `$. Then for $`k`$ fixed, or growing with $`n`$ as $`n\mathrm{}`$,

$$|Prob_{n,\stackrel{}{\alpha },\stackrel{}{\beta },\gamma }^{}(L_1/nt_1,\mathrm{},L_r/nt_r)Prob_{S_n}(L_1/nt_1,\mathrm{}L_r/nt_r)|0$$

uniformly in $`t_1,\mathrm{},t_r`$. (Here $`Prob_{S_n}`$ denotes the uniform distribution on $`S_n`$).

Example 3 Consider the case when $`\alpha _1=\mathrm{}=\alpha _q=\beta _1=\mathrm{}=b_q=\frac{1}{2q}`$ and all other parameters are $`0`$. Theorems 13 and 15 imply that the distribution on RSK shape and cycle index is the same as for the shuffles in Section 5, though we do not see a simple reason why this should be so.

Example 4 Another generalization of riffle shuffles are random walks coming from real hyperplane arrangements \[BiHR\]. The most interesting such shuffles are those where the weights on faces of the Coxeter complex are invariant under the action of the symmetric group. It is straightforward to see that such shuffles are mixtures of what can be called $`\mu `$ shuffles, where $`\mu `$ is a composition of $`n`$. For a $`\mu `$ shuffle, one breaks the decks into piles of sizes $`\mu _1,\mu _2,\mathrm{}`$ and then chooses uniformly at random one of the $`\left(\genfrac{}{}{0pt}{}{n}{\mu _1,\mu _2,\mathrm{}}\right)`$ possible interleavings. In what follows we also let $`\mu `$ denote the partition of $`n`$ given by ordering the parts of the composition by decreasing size.

For example the top to random shuffle is a $`(1,n1)`$ shuffle. Let $`P(j,k,n)`$ be the probability that when $`k`$ balls are dropped at random into $`n`$ boxes, there are $`j`$ occupied cells (thus by inclusion exclusion $`P(j,k,n)=_{r=j}^n(1)^{rj}\left(\genfrac{}{}{0pt}{}{n}{r}\right)\left(\genfrac{}{}{0pt}{}{r}{j}\right)(1r/n)^k`$). A result of \[DFP\] is that the iteration of $`k`$ top to random shuffles is equivalent to a mixture of $`(nj,1^j)`$ shuffles, where $`(nj,1^j)`$ is chosen with probability $`P(j,k,n)`$. Theorem 16 will give an expression for the increasing subsequence structure after this process. For this a lemma is required. In its statement we use notation in \[Mac\] that $`K_{\lambda \mu }`$ is a Kostka number (the number of semistandard Young tableau of shape $`\lambda `$ where $`i`$ appears $`\mu _i`$ times), and $`\lambda /\mu `$ denotes a tableau of skew shape $`\lambda /\mu `$.

###### Lemma 3

Let $`T`$ be a standard Young tableau of shape $`\lambda `$. The probability that a $`\mu `$ shuffle has recording tableau $`T`$ is equal to $`\frac{K_{\lambda \mu }}{\left(\genfrac{}{}{0pt}{}{n}{\mu _1,\mu _2,\mathrm{}}\right)}`$.

Proof: A $`\mu `$ shuffle corresponds to choosing at random a word where $`i`$ appears $`\mu _i`$ times, and each word has probability $`\left(\genfrac{}{}{0pt}{}{n}{\mu _1,\mu _2,\mathrm{}}\right)`$. It is easy to see that the RSK recording tableau of the word and the corresponding permutation obtained after the shuffle are identical. Now the number of words of length $`n`$ where $`i`$ appears $`\mu _i`$ times and with recording tableau $`T`$ is equal to $`K_{\lambda \mu }`$, since such words biject with the possible insertion tableau which have shape $`\lambda `$ and weight $`\mu `$. $`\mathrm{}`$

###### Theorem 16

Let $`f_{\lambda /\mu }`$ denote the number of standard tableau of shape $`\lambda /\mu `$. Then the chance that the RSK shape after $`k`$ top to random shuffles is $`\lambda `$ is equal to

$$\frac{f_\lambda ^2}{n!}\underset{a=1}{\overset{n}{}}P(a,k,n)(na)!\frac{f_{\lambda /(na)}}{f_\lambda }.$$

Proof: From Lemma 3 and the description of iterations of top to random shuffles as mixtures of $`\mu `$ shuffles, it follows that the sought probability is

$$\frac{f_\lambda }{n!}\underset{a=1}{\overset{n}{}}P(a,k,n)K_{\lambda ,(na,1^a)}(na)!.$$

Finally observe the $`K_{\lambda ,(na,1^a)}=f_{\lambda /(na)}`$, since the $`na`$ ones must appear in the first row and what remains is a standard Young tableau. $`\mathrm{}`$

Note that in Theorem 16, $`\frac{f_\lambda ^2}{n!}`$ corresponds to Plancherel measure and the rest is a correction term (going to 1 as $`k\mathrm{}`$ and $`n`$ is fixed). It would be interesting to determine (both for $`n`$ large and $`n`$ small) how many iterations of top to random are necessary for the length of the longest increasing subsequence to be close to that of a random permutation.

For comparison, one has the following result for ordinary 2-riffle shuffles. The result is an easy Corollary of equation 1.27 of \[J\], together with the fact that k 2-riffle shuffles is the same as one $`2^k`$ riffle shuffle \[BayD\]. Note that the result is for sufficiently large $`n`$ and says nothing for $`n`$ small.

###### Corollary 8

Let $`L_n`$ denote the longest increasing subsequence of a random element of $`S_n`$ and let $`L^(2^k)_n`$ denote the longest increasing subsequence of an element of $`S_n`$ after k 2-riffle shuffles. Then

$$lim_n\mathrm{}Prob.(\frac{L_n2n^{1/2}}{n^{1/6}}t)=F(t)$$

and

$$lim_n\mathrm{}Prob.(\frac{L_n^{2^k}2n^{1/2}}{n^{1/6}}t)=F(te^c)$$

where $`2^k=e^cn^{5/6}`$ and $`F(t)`$ is the Tracy-Widom distribution. Thus for sufficiently large $`n`$, $`5/6log_2(n)+c`$ 2-riffle shuffles are necessary and suffice for the longest increasing subsequence to be that of a random permutation .

## Acknowledgements

This research was supported by an NSF Postdoctoral Fellowship. The author thanks Persi Diaconis and a referee for helpful remarks.