Applications of Symmetric Functions to Cycle and Increasing Subsequence Structure
after Shuffles
∗JASON FULMAN fulman@math.pitt.edu
Department of Mathematics, University of Pittsburgh, 301 Thackeray Hall, Pittsburgh, PA 15260, USA Received March 9, 2001; Revised February 6, 2002
Abstract. Using symmetric function theory, we study the cycle structure and increasing subsequence structure of permutations after iterations of various shuffling methods. We emphasize the role of Cauchy type identities and variations of the Robinson-Schensted-Knuth correspondence.
Keywords: card shuffling, RSK correspondence, cycle index, increasing subsequence
1. Introduction
In an unpublished effort to study the way real people shuffle cards, Gilbert-Shannon-Reeds introduced the following model, calledk-riffle shuffling. Given a deck ofncards, one cuts it intokpiles with probability of pile sizes j1, . . . ,jkgiven by
(j1, . . . ,n jk) kn
.
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 A1, . . . ,Ak, the next card is dropped from pile i with probability A Ai
1+···+Ak).
The theory of riffle shuffling is relevant to many parts of mathematics. One area of mathematics influenced by shuffling is Markov chain theory [11]. For instance Bayer and Diaconis [5] proved that32log2(n) 2-shuffles are necessary and sufficient to mix up a deck of ncards and observed a cut-off phenomenon. The paper [23] gives applications of shuffling to Hochschild homology and the paper [8] describes the relation with explicit versions of the Poincar´e-Birkhoff-Witt theorem. Section 3.8 of [34] describes GSR shuffles in the lan- guage of Hopf algebras. In recent work, Stanley [35] 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 [5] and [15] using quasisym- metric functions. Connections of riffle shuffling with dynamical systems appear in [5, 18, 28, 29]. Generalizations of the GSR shuffles to other Coxeter groups appear in [7, 16–19].
∗The article was written when author was at Stanford University.
It is useful to recall one of the most remarkable properties of GSRk-shuffles. Sincek- shuffles induce a probability measure on conjugacy classes ofSn, they induce a probability measure on partitionsλofn. Consider the factorization of random degreenpolynomials over a field Fq into irreducibles. The degrees of the irreducible factors of a randomly chosen degreen polynomial also give a random partition ofn. The fundamental result of Diaconis-McGrath-Pitman (DMP) [13] is that this measure on partitions ofnagrees with the measure induced by card shuffling whenk=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 [16–18].
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 [30] and background will appear in Section 2). For the DMP theorem itself Stanley [35] 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
λ
sλ(x)sλ(y)=
λ
1
zλpλ(x)pλ(y).
Heresλandpλdenote the Schur functions and power sum symmetric functions respectively, andzλdenotes the centralizer size of a permutation of typeλ.
Given Section 3, it was very natural to seek card shuffling interpretations for the Cauchy type identities
λ
sλ(x)sλ(y)=
λ
λ
zλpλ(x)pλ(y)
λ
sλ(x)Sλ(y)=
all parts oddλ
2l(λ)
zλ pλ(x)pλ(y)
λ
sλ(x)Sλ(y)=
all parts oddλ
2l(λ)λ
zλ pλ(x)pλ(y)
λ
sλ(x)˜sλ(α, β, γ)=
λ
1
zλpλ(x) ˜pλ(α, β, γ)
Hereλdenotes the transpose of a partition andλ=(−1)|λ|−l(λ)wherel(λ) is the number of parts ofλ.Sλis a symmetric function studied for instance by Stembridge [37] and defined in Section 5. The symmetric function ˜sλ(α, β, γ) 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 [18] and proves a more general assertion. Although there is some overlap with the preprint [38] 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 [20] 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 (α,β, γ) 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 ofncards, cut the deck into two piles where the sizes arek,n−kwith probability(
n k)
2n; then shuffle the sizekpile thoroughly and riffle it with the remaining cards. This special case was first studied in [12] (their work was on convergence rates, not about cycle structure or increasing subsequence structure). Section 6 proves that if one applies the usual RSK correspondence to a permutation distributed as a (α,β, γ) shuffle, then the probability of getting any recording tableau of shape λis the extended Schur function ˜sλ( α,β, γ). (When γ = 0 this is equivalent to a result of Kerov/Vershik [26] and Berele/Remmel [6]. However the caseγ =0 (which arises for the shuffle in this paragraph), is treated incorrectly in [26] and not at all in [6]).
Section 7 applies the results of Sections 3 and 6 to find formulas for cycle structure after ( α,β, γ) shuffles; for instance it is proved that after such a shuffle on a deck of sizen, the expected number of fixed points is the sum of the firstnextended 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 largen, 5/6 log2(n)+c log2(e) 2-riffle shuffles bring the longest increasing subsequence to its limit distribution.
Currently we are working on analyzing the Toeplitz determinants which arise in the analysis of longest increasing subsequences after (α,β, γ) shuffles. We also note that there are many shuffles of interest (e.g. iterations of top to random, iterations of riffle shuffles followed by cuts) for which Toeplitz determinant expressions are unavailable. Analysis of these shuffles should be of interest to computational biology.
2. Background
This section collects the facts from symmetric function theory which will be needed later.
Chapter 1 of [30] is a superb introduction to symmetric functions. We review a few essentials here.
The power sum symmetric functionspλare an orthogonal basis of the ring of symmetric functions. Lettingzλ=
iinini! be the centralizer size of the conjugacy ofSnindexed by the partitionλwithniparts of sizei, one has that
pλ,pµ =δλµzλ.
The descent set of a permutationwis defined as the set ofiwith 1≤i ≤n−1 such that w(i)> w(i+1); the ascent set is the set ofiwith 1≤i ≤n−1 such thatw(i)< w(i+1).
The descent set of a standard Young tableauT is the set ofisuch thati+1 is in a lower row ofT thani. The RSK correspondence (carefully exposited in [33, 36]) associates to a permutationwa pair of standard Young tableau (its insertion tableauP(w) and its recording tableau Q(w)) and the descent set ofwis equal to the descent set of Q(w). Further the descent set ofw−1is equal to the descent set ofP(w), sinceQ(w−1)=P(w). Des(w) and Asc(w) will denote the descent and ascent set ofwrespectively. The notationλnmeans thatλis a partition ofn. The symbol fλdenotes the number of standard Young tableau of shapeλ.
The following result is a simple consequence of work of Gessel and Reutenauer [22] and Garsia [21].
Theorem 1 Letβλ(D)be the number of standard Young tableau of shapeλwith descent set D. Let Ni(w)be the number of i -cycles of a permutationw. Then
1.
w∈Sn Des(w)=D
i≥1
xiNi(w)=
λn
sλ(y)βλ(D),
i,j≥1
e
xj i i j
d|iµ(d)pj d(y)i/d
2.
w∈Sn
Asc(w)=D
i≥1
xiNi(w)=
λn
sλ(y)βλ(D),
i,j≥1
e
xj i i j
d|iµ(d)pj d(y)i/d
.
Proof: The number ofwinSn with descent setD andni i-cycles is the coefficient of
ixiNi(w) on the left hand side of the first equation. Letτ be the partition withni parts of sizei and let Lieτ(y) be the symmetric function associated with the corresponding Lie character (for background on Lie characters and relevant symmetric function theory see [32]). By [22], the number ofwinSn with descent set Dandni i-cycles is equal to the inner product
λn
sλ(y)βλ(D),Lieτ(y)
.
From [21] it follows that Lieτ(y) is the coefficient of
ixini in
i,j≥1
e
xj i i j
d|iµ(d)pj d(y)i/d.
This proves the first assertion.
For the second assertion, note thatβλ(D)=βλ({1, . . . ,n−1} −D). This follows from the fact that if a permutationwhas RSK shapeλand descent setD, then its reversal has RSK shapeλand ascent setD. Thus
λn
sλ(y)βλ(D),
i,j≥1
e
xj i i j
d|iµ(d)pj d(y)i/d
=
λn
sλ(y)βλ({1, . . . ,n−1} −D),
i,j≥1
e
xj i i j
d|iµ(d)pj d(y)i/d
as desired.
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 [15] and then in work of Stanley [35]. It was first proved for ordinary riffle shuffles in [13]. The value of the current argument is that it underscores the role of RSK and the Cauchy identity
λ
sλ(x)sλ(y)=
λ
1
zλpλ(x)pλ(y)
(the sums are over all partitions of all natural numbers).
Biased riffle shuffles were introduced in [12] and studied further in [15]. A biased riffle shuffle with parametersq =(q1,q2, . . .) where
qi =1 is defined as follows. First cut the deck into piles of sizesk1,k2, . . .by picking thek’s according to the distribution
n k1,k2, . . .
i
qiki.
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 permutationwdepends onwonly through Des(w−1). The main case of interest isq1= · · · =qk=1/kall otherqi =0 and corresponds to ordinary riffle shuffles [5].
To determine the cycle structure after a biased riffle shuffle we could make use of the following result of Stanley [35].
Theorem 2 Letwbe distributed as a biased riffle shuffle with parametersq. Let T be a standard Young tableau of shapeλ. Then the probability that the RSK algorithm associates insertion tableau T towis equal to sλ(q).
Instead (to simplify later sections) we will use the following similar result, which we record for completeness.
Theorem 3 Letwbe distributed as a biased riffle shuffle with parametersq. Let T be a standard Young tableau of shapeλ. Then the probability that the RSK algorithm associates recording tableau T towis equal to sλ(q).
Proof: Given a lengthn word J with positive integers as letters, letai be the number of occurrences of symboli inJrespectively. Define a permutationwin two line form by putting 1, . . . ,a1 in the positions occupied by the 1’s of Jfrom left to right,then putting the nexta2numbers in the positions occupied by the 2’s ofJfrom left to right,and so on.
For instance the word
1 3 2 1 2 2 1 3 1 2
corresponds to the permutation
1 9 5 2 6 7 3 10 4 8.
It is easy to see that in general the recording tableau ofwunder the RSK algorithm is equal to the recording tableau of J under the RSK algorithm. Arguing as in [5], if the entries of the random wordJ are chosen independently with probabilityqi of symboli, then the resulting distribution on permutationswis the same as performing aqbiased riffle shuffle.
As in [26], the combinatorial definition of the Schur function immediately implies that the chance thatJhas recording tableauT issλ(q).
Lemma 1 could be simplified via Theorem 2 but we prefer not to take this path.
Lemma 1 Letβλ(D)be the number of standard Young tableau of shapeλwith descent set D. Ifβλ(D)=0,then the probability that a biasedq-shuffle produces a specific permutation wwithDes(w−1)=D and RSK shapeλis equal to the probability that a biasedq-shuffle produces a permutation with(P,Q)tableaux satisfyingDes(P(w))=D,shape(Q(w))=λ divided byβλ(D)fλ.
Proof: Fix any permutationwsuch that Des(w−1)=Dand such thatwhas RSK shape λ(this is possible if βλ(D) = 0). Letx be the probability of obtainingwafter a biased q shuffle. Since allw with Des(w−1) = D are equally likely,x = y/z where y is the probability that a biasedq shuffle leads to a permutation with inverse descent set Dand RSK shapeλ, andz is the number of permutations with inverse descent set Dand RSK shapeλ. Nowyis the probability that after a biasedqshuffle one obtains a permutationw with Des(P(w))=D, shape(Q(w))=λ. Note thatzis simplyβλ(D)fλ, since the insertion tableau can be any standard Young tableau of shapeλand descent setD, and the recording tableau can be any standard Young tableau of shapeλ.
Now we prove the main result in this subsection.
Theorem 4 Let En,q denote expected value under the biased riffle shuffle measure with parametersq. Let Ni(w)be the number of i -cycles of the permutationw. Then
n≥0
unEn,q
i
xiNi
=
i,j
e
(ui xi)j i j
d|iµ(d)pj d(q)i/d.
Proof: Letwbe a fixed permutation such that Des(w−1)=D; then Probq(D) will denote the probability of obtainingwafter a biased riffle shuffle with parametersq. Using part 1 of Theorem 1 one concludes that the sought cycle index is
n≥0
unEn,q
i
xiNi
=
n≥0
un
ni≥0
i
xini
D⊆{1,...,n−1}
Probq(D)|{w: Des(w)=D,Ni(w)=ni}|
=
n≥0
D⊆{1,...,n−1}
Probq(D)
λn
sλ(y)βλ(D),
i,j≥1
e(ui xi)
j i j
d|iµ(d)pj d(y)i/d
=
n≥0
λn
sλ(y)
D⊆{1,...,n−1}
Probq(D)βλ(D),
i,j≥1
e
(ui xi)j i j
d|iµ(d)pj d(y)i/d
Lemma 1 implies that
D⊆{1,...,n−1}
Probq(D)βλ(D)
is f1
λmultiplied by the probability that the recording tableau of a permutation obtained after a biasedqshuffle has shapeλ. By Theorem 3, this latter probability issλ(q)fλ. Hence the sought cycle index is simply the inner product
λ
sλ(y)sλ(q),
i,j≥1
e
(ui xi)j i j
d|iµ(d)pj d(y)i/d
. Applying the Cauchy identity yields
λ
1
zλpλ(y)pλ(q),
i,j≥1
e
(ui xi)j i j
d|iµ(d)pj d(y)i/d
.
Sincepλ,pµ =δλ,µzλthis simplifies to
i,j≥1
e(ui xi)
j i j
d|iµ(d)pj d(q)i/d.
We remark that fork-riffle shuffles the cycle index simplifies to
i≥1
1 1−ukixii
1 i
d|iµ(d)ki/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. Forthcoming work relates this section to unitary groups.
Letλdenote the transpose ofλ. Letl(λ) be the number of parts ofλand letλdenote (−1)|λ|−l(λ). Whereas the previous section used the Cauchy identity, this section uses the dual Cauchy identity
λ
sλ(x)sλ(y)=
λ
λ
zλpλ(x)pλ(y)
(the sums are over all partitions of all natural numbers).
Theorem 5 Let En,q denote expected value under the biased riffle shuffle measure with parametersq followed by reversing the order of the cards. Then
n≥0
unEn,q
i
xiNi
=
i,j
e
((−u)i xi)j i j
d|iµ(d)(−pj d(q))i/d.
Proof: Letwbe a fixed permutation such that Asc(w−1)=D; then Probq(D) will denote the probability of obtainingwafter aqbiased riffle shuffle followed by reversing the order of the cards.
Using part 2 of Theorem 1 one concludes that the sought cycle index is
n≥0
unEn,q
i
xiNi
=
n≥0
un
ni≥0
i
xini
D⊆{1,...,n−1}
Probq(D)|{w: Asc(w)=D,Ni(w)=ni}|
=
n≥0
D⊆{1,...,n−1}
Probq(D)
λn
sλ(y)βλ(D),
i,j≥1
e(ui xi)
j i j
d|iµ(d)pj d(y)i/d
=
n≥0
λn
sλ(y)
D⊆{1,...,n−1}
Probq(D)βλ(D),
i,j≥1
e
(ui xi)j i j
d|iµ(d)pj d(y)i/d
.
From the proof of Theorem 4,
D⊆{1,...,n−1}
Probq(D)βλ(D)=
D⊆{1,...,n−1}
Probq(D)βλ(D)=sλ(q).
Consequently the sought cycle index is simply the inner product
λ
sλ(y)sλ(q),
i,j≥1
e
(ui xi)j i j
d|iµ(d)pj d(y)i/d
. Applying the dual Cauchy identity yields
λ
λ
zλpλ(y)pλ(q),
i,j≥1
e
(ui xi)j i j
d|iµ(d)pj d(y)i/d
.
Sincepλ,pµ =δλ,µzλthis simplifies to
i,j≥1
e
(ui xi)j i j
d|iµ(d)(−1)j i−i/dpj d(q)i/d.
The case of most interest isq1 = · · · = qk = 1k and all otherqi = 0. Then the cycle index simplifies to
i≥1
1 1−(−u)kiixi
1id|iµ(d)(−k)i/d
.
Much information can be gleaned from this cycle index in analogy with results in [13] 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−1 k+ 1
k2· · · +(−1)n−1 kn−1 .
Proof: The generating function for fixed points is given by settingxi =1 for alli >1 in the cycle index. This yields
(1+x1u/k)k
i=1
1 1−(−ku)i i
1id|iµ(d)(−k)i/d
.
Multiplying and dividing by (1+u/k)kgives (1+x1u/k)k
(1+u/k)k
i
1 1−(−ku)i i
1id|iµ(d)(−k)i/d
.
Observe that 1
1−u =
i≥1
1 1−(−ku)i i
1id|iµ(d)(−k)i/d
since this is what one obtains by setting allxi=1 in the cycle index. Hence the generating function for fixed points is
(1+x1u/k)k (1+u/k)k(1−u).
Then one differentiates with respect tox1, setsx1=1, and takes the coefficient ofun. We remark that [13] showed that the expected number of fixed points fork-riffle shuffles on ann-card deck is
1+1 k+ 1
k2· · · + 1 kn−1.
It is straightforward to compute higher moments forkshuffles 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
n≥0anun which converges at u = 1,then the n → ∞limit of the coefficient of unin 1f−(u)u is f(1).
Proof: This follows because the coefficient ofunin 1f−(u)u isa0+ · · · +an.
Recall that a binomial(n,p) random variable assumes the value x with probability (nx)px(1−p)n−x. Recall also that a geometric (α) random variable assumes the valuex with probability (1−α)αx.
Corollary 2
1. Fix u such that 0 < u < 1. Choose a random deck size with probability of getting n equal to (1−u)un. Let Ni(w) be the number of i -cycles of w distributed as the reversal of a k riffle shuffle. Then the random variables Ni are independent,where Ni
(i odd)is a binomial(1i
d|iµ(d)ki/d,ui/(ki+ui))and Ni (i even)is the convolution of1i
d|iµ(d)(−k)i/d many geometrics with parameter ui/ki.
2. Let Ni(w) be the number of i -cycles of w distributed as the reversal of a k riffle shuffle. Then as n→ ∞the random variables Ni converge in finite dimensional dis- tribution to independent random variables, where Ni (i odd) becomes a binomial (1i
d|iµ(d)ki/d,1/(ki +1))and Ni (i even)becomes the convolution of 1i
d|iµ(d) (−k)i/dmany geometrics with parameter1/ki.
Proof: As noted after Theorem 5, the cycle index of ak-shuffle followed by reversing the order of the cards is
i≥1
1 1−(−u)kiixi
1id|iµ(d)(−k)i/d
.
The proof of Corollary 1 gives that 1
1−u =
i≥1
1 1−(−ku)i i
1id|iµ(d)(−k)i/d
. Dividing these equations implies that
n≥0
(1−u)unEn,1/k,...,1/k
i
xiNi
=
iodd
1+uixi/ki 1+ui/ki
1/i
d|iµ(d)ki/d
ieven
1−ui/ki 1−uixi/ki
1/i
d|iµ(d)(−k)i/d
. This proves the first assertion of the theorem. The second assertion follows from dividing both sides of this equation by 1−u and applying Lemma 2. (Note that if all but finitely manyxi =1, only finitely many terms in the generating function remain. Sincek≥2 the Taylor series converges atu = 1 provided that the remainingx’s aren’t too much larger than 1).
We remark that ask→ ∞, the distribution ofNiin parts 1 and 2 converges to Poisson(ui/i) and Poisson(1/i) respectively.
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 largeiterms of the cycle index converge to those of random permutations. The same happens for ordinary riffle shuffles (Proposition 5.5 of [13]). The distribution of large cycles in random permutations has been broadly studied ([40] and the references therein).
Corollary 3 Fix k and let L1, . . . ,Lrbe the lengths of the r longest cycles ofπ. Then for k fixed,or growing with n as n→ ∞,
Probn,1/k,...,1/k(L1/n≤t1, . . . ,Lr/n≤tr)−ProbSn(L1/n≤t1, . . . ,Lr/n≤tr)→0 uniformly in t1, . . . ,tr.(HereProbSn denotes the uniform distribution on Sn).
Proof: Given the cycle index fork-shuffles followed by a reversal, this follows from minor modifications of either the arguments in [24] or [2].
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.
5.1. Generalized shuffling method on Cn
Step 1: Start with a deck of n cards face down. Let 0 ≤ y1, . . . ,yk ≤ 1 be such that yi = 1. Choose numbers j1, . . . ,j2k multinomially with the probability of getting j1, . . . ,j2kequal to (j1,...,nj2k)k
i=1yij2i−1+j2i. Make 2kstacks of cards of sizes j1, . . . ,j2k
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 (j1,...,nj2k) interleavings of the packets.
Cycle structure of this model of shuffling was analyzed for equalyin [18]. (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 Sn. By a result of Sch¨utzenberger exposited as Theorem A1.2.10 in [36], conjugation by the longest element also has no effect on RSK shape). The model was introduced fork=1 (and thusy1=1) in [5]. LetEn∗, ybe expectation onCnafter the above shuffling method.
LetNi(w) be the number ofi-cycles ofwinCn, disregarding signs. It is proved in [18]
that Theorem 6
1+
n≥1
un
w∈Cn
E∗n,1 k,...,1k
i≥1
xiNi(w)
=
m≥1
1+xmum/(2k)m 1−xmum/(2k)m
1 2m
d|m
doddµ(d)(2k)md
. As the paper [18] 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 L1, . . . ,Lrbe the lengths of the r longest cycles ofπ. Then for k fixed,or growing with n as n→ ∞,
Prob∗n,1/k,...,1/k(L1/n≤t1, . . . ,Lr/n≤tr)−ProbSn(L1/n≤t1, . . . ,Lr/n≤tr)→0
uniformly in t1, . . . ,tr.(HereProbSn denotes the uniform distribution on Sn)
A generalization of Theorem 6 will be proved later in this section. To this end, we require the following variation of the RSK correspondence.
5.1.1. Variation of the RSK correspondence. Order the set of numbers{±1, . . . ,±k}by 1<−1<2<−2· · ·<k<−k.
Given a word on these symbols, run the RSK algorithm as usual, with the amendments that a symboli can’t bump anotheri ifi is positive, but must bump anotheri ifi 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 −1 2 −2 1 1 −1 1 2 2 −1 2 −2
has insertion tableauPand recording tableau Qrespectively equal to
1 1 1 1 −1 2 2 −2
−1 2 2
−1 −2
1 2 3 4 9 10 12 13
5 6 7
8 11
The proof of Theorem 7 runs along the same lines as the proof of the RSK correspondence as presented in [33]. Hence we omit the details.
Theorem 7 Order the set of numbers{±1, . . . ,±k}by 1<−1<2<−2· · ·<k<−k.
Then the above variation on the RSK Correspondence is a bijection between length n words on the symbols{±1, . . . ,±k}and pairs(P,Q)where
1. P is a tableau on the symbols{±1, . . . ,±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 ath row and bth 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, . . . ,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λwill denote the symmetric functions studied in [37] (a special case of the extended Schur functions in [26]). One definition of theSλis as the determinant
Sλ(y)=det qλi−i+j
whereq−r =0 forr>0 and forr ≥0,qris defined by setting
n≥0
qntn =
i≥1
1+yit 1−yit.
We remark that Theorem 8 gives a simple probabilistic interpretation toSλ, different from the interpretation in [26]. Of course one can letk→ ∞as well.
Theorem 8 Letwbe distributed as a shuffle of this section with parameters y1, . . . ,ykaf- ter disregarding the up/down pattern of the cards so thatwis an unsigned permutation. Let Q be a standard Young tableau of shapeλ. Then the probability that the usual RSK corre- spondence associates recording tableau Q towis equal to21nSλ(y1, . . . ,yk). Consequently the probability thatwhas RSK shapeλis equal to 2fnλSλ(y1, . . . ,yk).
Proof: Given a lengthn wordJon the symbols{±1, . . . ,±k}, letai,bi be the number of occurrences of the symboli,−i in J respectively. Define a permutationwin two line form by putting 1, . . . ,a1in the positions occupied by the 1’s of Jfrom left to right, then putting the nextb1numbers (arranged in decreasing order) in the positions occupied by the
−1’s ofJfrom left to right, then the nexta2numbers (arranged in increasing order) in the positions occupied by the 2’s ofJfrom left to right, etc. For instance the word
1 −1 2 −2 1 1 −1 1 2 2 −1 2 −2
corresponds to the permutation
1 7 8 13 2 3 6 4 9 10 5 11 12.
If the word entries are chosen independently with±i having probability y2i, the resulting distribution on permutations is the same as performing a y shuffle of this section and forgetting about signs.
It is easy to see that the recording tableau ofwunder the RSK algorithm is equal to the recording tableau ofJunder our variant of the RSK algorithm. Letγi(P) be the number of occurrences of symboliin a tableauP. By Theorem 7, the probability thatJhas recording tableauQunder our variant of RSK is equal to
1 2n
P
i≥1
yiγi(P)+γ−i(P)
wherePhas shapeλand satisfies conditions 1, 2 in Theorem 7. Theorem 9.2b of [37] shows that this sum is equal to21nSλ(y1, . . . ,yk).
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 permutationwis equal to the length of the longest increasing subsequence ofwand has asymptotically the same distribution as the largest eigenvalue of a random GUE matrix [3]. Studying longest increasing subsequences ofwdistributed as a GSRk-riffle shuffle amounts to studying the longest weakly increasing
subsequences in random length n words onk symbols, which has also been of interest to random matrix theorists [35, 39]. What Theorem 8 tells us is that studying longest increasing subsequences ofwdistributed as unsigned typeCshuffles amounts to studying weakly increasing subsequences in random lengthnwords on the symbols{±1, . . . ,±k}, where 1 <−1 <· · · <k < −k and the subsequence is not allowed to contain a given negative symboli more than once. Forkfixed and random lengthnwords on the symbols {±1, . . . ,±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 mostk. For example, one obtains the following corollary from the analogous results in [25] and [39]
for weakly increasing subsequences in random words.
Corollary 5 For k fixed,the RSK shape after an unsigned Cn shuffle with y1 = · · · = yk = 1k has at most k rows and k columns. For large n the expected value of any of the k rows or columns is asymptotic to2kn.
We hope in future work to study the fluctuations around this limit shape, and to examine the case when bothn,kare large.
Theorem 9 determines the generating function for cycle structure after performing the generalized shuffling method onCnwith parametersy1, . . . ,ykand forgetting about signs.
Theorem 9 Let En∗, y denote expected value under the generalized shuffling method on Cnwith parameters y1, . . . ,ykafter forgetting signs. As usual,let Ni(π)be the number of cycles of length i of the permutationπ. Then
n≥0
unEn∗, y
i
xiNi
=
i≥1
jodd
e
(ui xi/2i)j i j
d|i
doddµ(d)(2pj d(y))i/d
.
Furthermore,reversing the order of the cards has no effect on the cycle index.
Proof: Letwbe a fixed permutation such that Des(w−1) = Dand let Prob∗y(D) be the probability of obtainingwafter ayunsigned typeCshuffle.
Using part 1 of Theorem 1 and the fact that the probability ofw depends only onw through Des(w−1), it follows that the sought cycle index is
n≥0
unEn∗, y
i
xiNi
=
n≥0
un
ni≥0
i
xini
D⊆{1,...,n−1}
Prob∗y(D)|{w: Des(w)=D,Ni(w)=ni}|
=
n≥0
D⊆{1,...,n−1}
Prob∗y(D)
λn
sλ(z)βλ(D),
i,j≥1
e(ui xi)
j i j
d|iµ(d)pj d(z)i/d
=
n≥0
λn
sλ(z)
D⊆{1,...,n−1}
Prob∗y(D)βλ(D),
i,j≥1
e
(ui xi)j i j
d|iµ(d)pj d(z)i/d
.
