Ordered Cycle Lengths In A Random Permutation
Transcript Of Ordered Cycle Lengths In A Random Permutation
ORDERED CYCLE LENGTHS IN A RANDOM PERMUTATION
BY
L. A. SHEPP AND S. P. LLOYD
1. Introduction. Problems involving a random permutation are often concerned with the cycle structure of the permutation. Let SfBbe the n ! permutation operators on n numbered places, and let a(7t) = (a1(7i),a2(7t),••■,a„(7r)) designate the cycle class of n e £f„ ; that is, permutation n has a,in) cycles of length 1, a2in) cycles of length 2, •••. Suppose the elements of Sr°aare assigned probability 1/n! each. In a variety of problems one seeks limiting (large n) properties of random variables which depend on n only by way of a(7r). In the matching problem, for instance, the result lim„ prob {a, =0} = e_1 is an old one [1, p. 50]. Goncharov in [2], [3] gives limiting forms for the distribution of each a¡, of So,-, and of the longest cycle. In [4], [5] Golombalso investigates the longest cycle. With /„ the expected length of the longest cycle, Golomb shows that IJn is monotone decreasing, and gives the numerical value 0.62432965 ••• for the limit. Answering in part a question raised by Golomb, we give a closed form for this limit (Equation (14)); in fact, we give in §4 the corresponding result for the mth moment of the length of the rth longest cycle for m = 1,2, ••• and r = 1,2, •••, and we give the limiting distribution for the length of the rth longest cycle. In §5 we give asymptotics for the distribution and all moments of the length of the rth shortest cycle, r = 1,2, •••. The results and proofs are more complicated for the moments of the rth shortest cycle than for the rth longest. Our methods are straightforward: we set up generating functions, get leading terms in closed form, and use Tauberian methods to recover the asymptotic dependence on n. The Tauberian side conditions needed are based on the combinatorial arguments of §6.
2. A model. For given n the distribution of a is obtained by dividing the number of permutations in class a by n !:
P{a, = a,,a2 = a2,---, a„ = a„}
= 0 otherwise,
the a's being any nonnegative integers [1, p. 67]. It will prove natural to include
Presented to the Society, September 2,1965 ; received by the edittors April 7,1965.
340
License or copyright restrictions may apply to redistribution; see https://www.ams.org/journal-terms-of-use
1966]
ORDERED LENGTHS IN A RANDOM PERMUTATION
341
the case n = 0; S?0 consists of 0! elements, namely, the identity permutation on the empty set (all oc's are 0).
The oc's above would be independent if it were not for the condition on Hjaj. Consider then a sequence a = (a„a2, ■■■o) f mutually independent nonnegative integer valued random variables, where for j = 1,2, ••• the random variable a¡ has the Poisson distribution of mean zJlj, viz. :
(2)
Pz{aj= a} = exp[ - (z^)] SeM., a . 0,1, - .
Here, the parameter z which has been introduced is such that 0 < z < 1 and is the same for each j = 1,2, •••. From now on, probabilities and expectation based on the family (2) will carry subscript z, while those based on (1) will carry subscript n.
We have Pz{a} # 0} = 1 - exp [ - zJ¡j] < zJ/j, so that Zf=1 Pz{«j # 0} is finite. By the Borel-Cantelli lemma, Pz{o/ # 0 for infinitely many j} = 0. Thus the random variable v(a) = S^v"«,- is finite with probability 1, and the joint distribution of the a's may be written meaningfully as
Pz{a, = a„ a2 - a2, •••} - (1 - z}z*> U ^~T
for all sequences a = ia„ a2, •••) of nonnegative integers eventually 0. It is easy to see that the conditional distribution of the a's given v does not depend on z; it is just
-P*{«i = a„ a2 = a2, ••• | v(a) = n}
= n(^T- ¡tija,-*
= 0 otherwise,
so that we have recovered (1). On the other hand, the distribution of v is Pz{v(a) = n} = (1 —z)z", n = 0,1, •■■; the degree of a random permutation under Pz is a geometrically distributed random variable. Its expected value is Ez{v} = z/(l —z), so that z -» 1 will correspond to n -» oo.
Suppose í> =
£z{<5} = Fz{Fz{4>|v}}
CO
(3)
= S Pz{v = n} Ez{4>| v - «},
n = 0
oo
= I (1 - z)z"£n{<5},
B=0
License or copyright restrictions may apply to redistribution; see https://www.ams.org/journal-terms-of-use
342
L. A. SHEPP AND S. P. LLOYD
[February
where £„(0) is the expected value of <5for the distribution (1). Thus FZ()/(1—z) is the generating function for the sequence F„{
£2{exp[iia,.]} = exp [(zy//)(e" - 1)], - co < t < oo.
Using our basic relation (3), it is straightforward that
E„{explitaj]} = I - -—- ,
p =0 P- \ J ) lim£„{exp[iia;]} = exp[(l//)(e" - 1)],
- oo < t < oo.
This last is the characteristic function of the Poisson distribution of mean 1/y. Since Pn{aj-is an integer} = 1, the theorem of Paul Levy gives
limP„{aj. = a} = exp[-(l/;)] i-^-,
a = 0,1,-,
for the limiting distribution of a,-. Consider next the total number of cycles a(x) = Z^a^. Under Pz, the a's are Poisson and independent, so a is Poisson with mean Y^iz^j) = log(1/(1 - z)). Hence
*■<-«[t'"e>r](exp[i(]-l) , — CO < Í < CO,
and the coefficient of z "in Fz{e'"r}/(1 —z) is the binomial coefficient
E^'a}=Y¡^r'
-co<í<00'
» = o,i,-.
Using a Binet form of the Stirling approximation [6, p. 249] we obtain easily
(«p[;r]-l) r
Q (Al
(4) £.{«*}-g-_
[l+^j,
-oo
n = 2,3,-,
with | on(í)| Ú M < co uniformly in the range indicated. The mean and variance of a under P„ are
E„{a}= Î l = logn+ 0(l),
p=i P
En{a2} - E2n{a} = ¿ £¿i
p=i P
= log n + Oil),
and for the normalized variable (cr - log n)j yj log n we obtain from (4)
License or copyright restrictions may apply to redistribution; see https://www.ams.org/journal-terms-of-use
1966]
ORDERED LENGTHS IN A RANDOM PERMUTATION
343
¡SíM^ÍteSt)} =exp[~^2]' -co
We apply the Levy theorem and have Goncharov's result
,. _ iff-log« , \ Ç'
[ 1 2] du
hm P. { —y-—— < x} =
exp - - tr ——,
— oo < x < oo.
In the same vein, let o ' = a2 4- a4 4- •••be the total number of odd cycles. (That is,
( — 1)" is the character of the alternating representation.) Just as above, we
obtain
Ez{e»°'} =
—Ïl(expU0-l)/2
l-z2J
r(ke*+i)+p)
En{e"a'} = —Vî-r-^-
.
r(i2(.-+i)),!
- oo < t < co,
n = 2p or 2p 4- 1,
p = 0,1,-,
and(o-' —^ log n)/^/(i log n) is standard Gaussian in the limit.
3. The model extended. The following setting for the probability measure Pz will render transparent the formulas for generating functions involving the rth longest and rth shortest cycles. Let a Poisson process take place on T = {— oo
<2(z) = j, z z2
hiz) = J + -,
J-l zk
tjiz)= Z -k
zk .
1
tjz) = I -Î- = log
, k 61- z'
License or copyright restrictions may apply to redistribution; see https://www.ams.org/journal-terms-of-use
344
L. A. SHEPP AND S. P. LLOYD
[February
andthey'th interval is {i: i/z) ^ t < i, + 1(z)}, y'= l,2, —. Let Xz(t), - oo < í < oo, be the function whose value is / on the j'th interval, j = 1,2, —, and 0 if t < 0 or t = iœ(z). Then for each ;' = 1,2, ■■•the interval {t:Xzit) =j} has length z'lj, the probability that a¡ jumps of the Poisson process occur in this interval is exp[ —izJlj)]izJlj)ajlaj\, aj = 0,1,•••, and these various events for /= 1,2, — are mutually independent; we are back to Pz. Tobe quite explicit, here is how we may choose a random permutation according to Pz. We take a sample function of the Poisson process ; the jumps in the interval [0, iœ(z)) are finite in number with probability 1, occurring at the times x, ^ x2 ^ ••• ;£ xa, say (with a random, of course). We take the positive integers Xz(x,) ^ Xz(t2) ^ ••• = X2(zj) as the lengths of the a cycles of a permutation on v = Z°= i Xz(zj) places, and in this class of SPVwe choose a permutation at random with uniform distribution.
We will see now that this machinery is well adapted to investigating the rth longest and rth shortest cycles for any given r = 1,2, —. Let Sr = Sr(a) be the length of the rth shortest cycle in a permutation of cycle class a; we define S¿a) = 0 if Za, < r. The probability density at t of the rth jump of the Poisson process counting to the right from t,iz) is tr~1e~t\ir — 1)!, 0 = t < co, as is well known. If this rth jump occurs at t, then the value of Sr is Xz(i), according to our model. It follows that the distribution of Sr under Pz is
rrt'Jj ++1i(z)
ÁS,=j} = Jtjiz)
j—1
(r-1) je ' dt,
.7= 1,2,-,
(5)
/• oo
f r— 1
e~* dt, ; = o.
We will treat this in more detail in §5. Let Lr = Lr(a) be the length of the rth longest cycle in a permutation of cycle
class a; we define Lr(a) = 0 if Za; < r. The probability density at t of the rth jump of the Poisson process counting to the left from iœ(z) is
itjz) -tj'1 exp [ - [Uz) - t]]Hr - 1)! , - co < t = tjz).
As with (5) then,
(6)
Pz{Lr = ;}=
V^z tJ exp[-[f,(z)-«]]*,
Jt3(z)
(r-l)l
; = 1,2,-
=J-l[aZ(r-T)!«1p[-[<»co-*]]*;=. o.
We consider this in detail in the next section. We conclude the present section with some analytical preliminaries regarding
the tjiz). With z = e_s, 0
License or copyright restrictions may apply to redistribution; see https://www.ams.org/journal-terms-of-use
1966]
ORDERED LENGTHS IN A RANDOM PERMUTATION
345
tœie's)-tjie-s)=
£ e~ks
Z -r-f,e '
y-1,2,.».
On the interval {y: fes< y < (fe4- í)s} there obtains
e-ks
e-y
e-(*+i)S
ks >-> y (k 4- l)s and
e-*s
/• (fc+l)s g-j>
e-(fc+l)s
—r— >
k ]ks
— <^y > —i—t->
y
k+ l
Summing on fe, we have bounds
£ e~ks
(7)
Eijs) < Z -t- < £((J - l)s), / = 1,2,.
where
£(*) =
jx
- dy,
y
0 < x < co,
( = + co, x = 0),
is the exponential integral. The mapping x -* £(x) is an order reversing homeomorphism of 0 < x < co onto itself, so for each j = 1,2,— and each 0 < s < oo the equation
(8)
Z ^ = £(x/S))
has a unique root 0 < x7(s) < co. Using (7), we obtain ij — l)s < Xjis)
In §5 we will need a closer estimate for x¡(s). From the well-known identity
Cx 1 - e~y
(9)
£(x) = -
dy -logx-y,
0 < x < oo,
Jo y
(wherey = 0.577 ••• is Euler's constant) we obtain, since Eix,is)) = log(1/(1 —z)),
do)
Xi(s) = (1_z)e Vexp[J0 —y—dy\
= il-z)e~y + Oi\-z)2, z-»l.
For the last expression we have used the bound
*l(s) 1 - e y
- dy < x,is) < s Jo
given in the preceding paragraph. Although we do not use it, the following expression for x/s) may be of interest.
We find Xjis) = Zp =1Apij)sp, convergent for all s, with the first few coefficients
License or copyright restrictions may apply to redistribution; see https://www.ams.org/journal-terms-of-use
346
L. A. SHEPP AND S. P. LLOYD
[February
A,íj)= exp[r'Ü)/rO)]= exp[-y+ ¿ (l/fe)J
11 1 J -^ 2 ++ K247;T++ 478öjä2+-'>
A2(j)= A,ÍJ)^A,ÍJ)-j+1^
1 0 2-Ï4X + —j +
1_
A3U) = -^ { [ Alij) ~j + 2~] [5AlU) - 3 (j - ï)
12
~ °-9W+ -•
^Ü)~ -281Ö+--
We omit the proof.
4. The rth longest cycle. According of the rth longest cycle under Pz is
<*> fO+iW rt c_\ _ tf-i
£z{(Lr)"} = Z JM
7 = 1 J/j(z)
fan,
v ~ U!
to (6), the mth moment **P [ - [*„(*) -«]]<**,
of the length m, r = 1,2, - .
Under the change of variable iœ(z) —í = £(x), this becomes
£z{(L,n= Sfp
VW'1 e-™Çdx,
with z = e~' again and x/s) given by (8). Now xj(s)
quantity sm£z{(Lr)m} is bounded above by Z; = i [*/+i(5XTty and below by
l£i [*/«)]% with
/•»,»♦«(»)
i"j =
dp(x),
These bounds are just the upper and lower Darboux sums for the Darboux-Stieltjes
integral jj°ús)xmdpíx) based on the mesh determined by x/s), j = 1,2, — . From
ij — i)s < Xjis)
ass->0.As z-> 1 then, we have s = log(l/z)->0, s/(l-z)^l,x1(s)->0,
and hence
(11)
lim (í-^LEz{ÍLrr}
z-t,
mi
where the constants Gr m are
= Gr,m,
"i?'}'""'
r — i,¿, ■••,
License or copyright restrictions may apply to redistribution; see https://www.ams.org/journal-terms-of-use
1966]
ORDERED LENGTHS IN A RANDOM PERMUTATION
347
r•xo™o „m-1— 1 rlrE/',AjxT),"]i-1
...
(12)
Jr,m= Jo ~^T (r - 1)! CXP[~ {X)~ ^
In §6 we prove that £„{(Lr)m} is monotone nondecreasing in n. If we apply the Karamata-Hardy-Littlewood Tauberian theorem [7, p. 143], [8, p. 203] to (11) we obtain
(13)
UMB.^'j-G....
«-►00
—«•••••
» B= ^5 -^-5 " * J
for the limiting form of the moments of LJn. Thecasem = 1, r = 1 is the limit of Golomb mentioned in the Introduction:
(14) lim£„(A) = f'expr-x-r^-'/^dy dx).
n->oo \ n )
JO
I
Jx
The numbers Grm have the property
lim im + l)rGrm =-¡—,
m = 0,1, — .
We sketch the proof. The change of variable £(x) = x in (12) gives
J0 m! (r-1)!
where £(t) is the function inverse to £(x): ^(£(x)) = x, 0 < x < oo. For large r the density i'-1e~zj(r — 1)! is negligible if t is not large. From the identity (9) we obtain easily £(t) ~ e~T~y, t-> oo, for the asymptotic form of £(t). We substitute this in the expression for Grm and the result follows. (The argument can be made rigorous; we omit the details.)
For the limiting distribution of LJn we seek a distribution Fr(£)> 0 ;£ f g 1, with the property J0' £m dFXQ = Gr m, m = 0,1, •••. If such an Fr exists then
IkíJf^lí^F^
n->oo
0SÍS1,
is obtained according to the method of moments [9, p. 27]. From (12) it is straightforward that if there is an Fr such that
(15)
s ( - îrTjEOo]'
rr (r-l)!(p-r)!p'
0 < y < oo,
License or copyright restrictions may apply to redistribution; see https://www.ams.org/journal-terms-of-use
348
L. A. SHEPP AND S. P. LLOYD
[February
Mrs. L. A. Needham of our organization has obtained the following numerical values for the first moments Gr,.
r
Grl
2VGr>1
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 (sum)
0.62432997 0.20958090 0.08831609 0.04034198 0.01914548 0.00927494 0.00454696 0.00224518 0.00111357 0.00055387 0.00027599 0.00013768 0.00006874 0.00003434 0.00001716 0.00000857 0.00000429 0.00000214 0.00000107 0.00000054 0.00000027 0.00000013 0.00000007 0.99999993
2.2239538 1.4931151 1.2583788 1.1496320 1.0911837 1.0572380 1.0366046 1.0236979 1.0154706 1.0101584 1.0066977 1.0044290 1.0029350 1.0019480 1.0012943 1.0008607 1.0005727 1.0003812 1.0002538 1.0001690 1.0001125 1.0000749 1.0000498
Table 1. Grl and 2reyGr_,forr= 1(1)23.
then F, will have moments Gr m. Now, £(y) is the Laplace transform £(y)
- So e~yufiu)du of
fiu) =0, 0 ^ u < 1,
= —, 1 g U < 00,
License or copyright restrictions may apply to redistribution; see https://www.ams.org/journal-terms-of-use
1966]
ORDERED LENGTHS IN A RANDOM PERMUTATION
349
so that the rightmost member of (15) is indeed a Laplace transform. Inverting, we obtain
, Pffl-/v/{ (-W"
f
f du, dup
1
Ul+...+Upál/í
= 0, - ^ Í < CO, r
for the limiting distribution of LJn. We observe that for given r, 1 —£/£) is the sum of q — r+l elementary integrals on the interval iq + 1)_1 < Ç :£ q'1, q = r,r + l, — . When r = 1 the above is Goncharov's formula for the limiting distribution of L,/n [2].
5. The rth shortest limiting positions
i,. =
cycle. As z -*1,
3!
limi/z)
z-fl
J-i
= Z 1
the endpoints iy(z) of our
i
-rr, J= 2,3,-,
K
model
move to
= 0,
j = 1,
and Sr has the z limiting distribution
(16) limPz{Sr=j}= f—Íl—-C-' dt,
In §6 we will show that the Tauberian side condition
¿«1,2,-.
\Pn{Sr=j}-Pn-,{Sr=j}\^
-|,
n = l,2,-,
holds, so from (16) and the KHLT theorem we have
lim Pn{Sr=j} = fJ ' f_ e"' di, ¿ = 1,2,-.
The tail of this distribution is asymptotically
c-'pog/j |r-l
(r-1)!;2 '
using the well-known estimate
*-? 4=1o^'+^+o(t)-
We see that the limiting distribution of Sr has infinite mean.
License or copyright restrictions may apply to redistribution; see https://www.ams.org/journal-terms-of-use
BY
L. A. SHEPP AND S. P. LLOYD
1. Introduction. Problems involving a random permutation are often concerned with the cycle structure of the permutation. Let SfBbe the n ! permutation operators on n numbered places, and let a(7t) = (a1(7i),a2(7t),••■,a„(7r)) designate the cycle class of n e £f„ ; that is, permutation n has a,in) cycles of length 1, a2in) cycles of length 2, •••. Suppose the elements of Sr°aare assigned probability 1/n! each. In a variety of problems one seeks limiting (large n) properties of random variables which depend on n only by way of a(7r). In the matching problem, for instance, the result lim„ prob {a, =0} = e_1 is an old one [1, p. 50]. Goncharov in [2], [3] gives limiting forms for the distribution of each a¡, of So,-, and of the longest cycle. In [4], [5] Golombalso investigates the longest cycle. With /„ the expected length of the longest cycle, Golomb shows that IJn is monotone decreasing, and gives the numerical value 0.62432965 ••• for the limit. Answering in part a question raised by Golomb, we give a closed form for this limit (Equation (14)); in fact, we give in §4 the corresponding result for the mth moment of the length of the rth longest cycle for m = 1,2, ••• and r = 1,2, •••, and we give the limiting distribution for the length of the rth longest cycle. In §5 we give asymptotics for the distribution and all moments of the length of the rth shortest cycle, r = 1,2, •••. The results and proofs are more complicated for the moments of the rth shortest cycle than for the rth longest. Our methods are straightforward: we set up generating functions, get leading terms in closed form, and use Tauberian methods to recover the asymptotic dependence on n. The Tauberian side conditions needed are based on the combinatorial arguments of §6.
2. A model. For given n the distribution of a is obtained by dividing the number of permutations in class a by n !:
P{a, = a,,a2 = a2,---, a„ = a„}
= 0 otherwise,
the a's being any nonnegative integers [1, p. 67]. It will prove natural to include
Presented to the Society, September 2,1965 ; received by the edittors April 7,1965.
340
License or copyright restrictions may apply to redistribution; see https://www.ams.org/journal-terms-of-use
1966]
ORDERED LENGTHS IN A RANDOM PERMUTATION
341
the case n = 0; S?0 consists of 0! elements, namely, the identity permutation on the empty set (all oc's are 0).
The oc's above would be independent if it were not for the condition on Hjaj. Consider then a sequence a = (a„a2, ■■■o) f mutually independent nonnegative integer valued random variables, where for j = 1,2, ••• the random variable a¡ has the Poisson distribution of mean zJlj, viz. :
(2)
Pz{aj= a} = exp[ - (z^)] SeM., a . 0,1, - .
Here, the parameter z which has been introduced is such that 0 < z < 1 and is the same for each j = 1,2, •••. From now on, probabilities and expectation based on the family (2) will carry subscript z, while those based on (1) will carry subscript n.
We have Pz{a} # 0} = 1 - exp [ - zJ¡j] < zJ/j, so that Zf=1 Pz{«j # 0} is finite. By the Borel-Cantelli lemma, Pz{o/ # 0 for infinitely many j} = 0. Thus the random variable v(a) = S^v"«,- is finite with probability 1, and the joint distribution of the a's may be written meaningfully as
Pz{a, = a„ a2 - a2, •••} - (1 - z}z*> U ^~T
for all sequences a = ia„ a2, •••) of nonnegative integers eventually 0. It is easy to see that the conditional distribution of the a's given v does not depend on z; it is just
-P*{«i = a„ a2 = a2, ••• | v(a) = n}
= n(^T- ¡tija,-*
= 0 otherwise,
so that we have recovered (1). On the other hand, the distribution of v is Pz{v(a) = n} = (1 —z)z", n = 0,1, •■■; the degree of a random permutation under Pz is a geometrically distributed random variable. Its expected value is Ez{v} = z/(l —z), so that z -» 1 will correspond to n -» oo.
Suppose í> =
£z{<5} = Fz{Fz{4>|v}}
CO
(3)
= S Pz{v = n} Ez{4>| v - «},
n = 0
oo
= I (1 - z)z"£n{<5},
B=0
License or copyright restrictions may apply to redistribution; see https://www.ams.org/journal-terms-of-use
342
L. A. SHEPP AND S. P. LLOYD
[February
where £„(0) is the expected value of <5for the distribution (1). Thus FZ(
£2{exp[iia,.]} = exp [(zy//)(e" - 1)], - co < t < oo.
Using our basic relation (3), it is straightforward that
E„{explitaj]} = I - -—- ,
p =0 P- \ J ) lim£„{exp[iia;]} = exp[(l//)(e" - 1)],
- oo < t < oo.
This last is the characteristic function of the Poisson distribution of mean 1/y. Since Pn{aj-is an integer} = 1, the theorem of Paul Levy gives
limP„{aj. = a} = exp[-(l/;)] i-^-,
a = 0,1,-,
for the limiting distribution of a,-. Consider next the total number of cycles a(x) = Z^a^. Under Pz, the a's are Poisson and independent, so a is Poisson with mean Y^iz^j) = log(1/(1 - z)). Hence
*■<-«[t'"e>r](exp[i(]-l) , — CO < Í < CO,
and the coefficient of z "in Fz{e'"r}/(1 —z) is the binomial coefficient
E^'a}=Y¡^r'
-co<í<00'
» = o,i,-.
Using a Binet form of the Stirling approximation [6, p. 249] we obtain easily
(«p[;r]-l) r
Q (Al
(4) £.{«*}-g-_
[l+^j,
-oo
n = 2,3,-,
with | on(í)| Ú M < co uniformly in the range indicated. The mean and variance of a under P„ are
E„{a}= Î l = logn+ 0(l),
p=i P
En{a2} - E2n{a} = ¿ £¿i
p=i P
= log n + Oil),
and for the normalized variable (cr - log n)j yj log n we obtain from (4)
License or copyright restrictions may apply to redistribution; see https://www.ams.org/journal-terms-of-use
1966]
ORDERED LENGTHS IN A RANDOM PERMUTATION
343
¡SíM^ÍteSt)} =exp[~^2]' -co
We apply the Levy theorem and have Goncharov's result
,. _ iff-log« , \ Ç'
[ 1 2] du
hm P. { —y-—— < x} =
exp - - tr ——,
— oo < x < oo.
In the same vein, let o ' = a2 4- a4 4- •••be the total number of odd cycles. (That is,
( — 1)" is the character of the alternating representation.) Just as above, we
obtain
Ez{e»°'} =
—Ïl(expU0-l)/2
l-z2J
r(ke*+i)+p)
En{e"a'} = —Vî-r-^-
.
r(i2(.-+i)),!
- oo < t < co,
n = 2p or 2p 4- 1,
p = 0,1,-,
and(o-' —^ log n)/^/(i log n) is standard Gaussian in the limit.
3. The model extended. The following setting for the probability measure Pz will render transparent the formulas for generating functions involving the rth longest and rth shortest cycles. Let a Poisson process take place on T = {— oo
<2(z) = j, z z2
hiz) = J + -,
J-l zk
tjiz)= Z -k
zk .
1
tjz) = I -Î- = log
, k 61- z'
License or copyright restrictions may apply to redistribution; see https://www.ams.org/journal-terms-of-use
344
L. A. SHEPP AND S. P. LLOYD
[February
andthey'th interval is {i: i/z) ^ t < i, + 1(z)}, y'= l,2, —. Let Xz(t), - oo < í < oo, be the function whose value is / on the j'th interval, j = 1,2, —, and 0 if t < 0 or t = iœ(z). Then for each ;' = 1,2, ■■•the interval {t:Xzit) =j} has length z'lj, the probability that a¡ jumps of the Poisson process occur in this interval is exp[ —izJlj)]izJlj)ajlaj\, aj = 0,1,•••, and these various events for /= 1,2, — are mutually independent; we are back to Pz. Tobe quite explicit, here is how we may choose a random permutation according to Pz. We take a sample function of the Poisson process ; the jumps in the interval [0, iœ(z)) are finite in number with probability 1, occurring at the times x, ^ x2 ^ ••• ;£ xa, say (with a random, of course). We take the positive integers Xz(x,) ^ Xz(t2) ^ ••• = X2(zj) as the lengths of the a cycles of a permutation on v = Z°= i Xz(zj) places, and in this class of SPVwe choose a permutation at random with uniform distribution.
We will see now that this machinery is well adapted to investigating the rth longest and rth shortest cycles for any given r = 1,2, —. Let Sr = Sr(a) be the length of the rth shortest cycle in a permutation of cycle class a; we define S¿a) = 0 if Za, < r. The probability density at t of the rth jump of the Poisson process counting to the right from t,iz) is tr~1e~t\ir — 1)!, 0 = t < co, as is well known. If this rth jump occurs at t, then the value of Sr is Xz(i), according to our model. It follows that the distribution of Sr under Pz is
rrt'Jj ++1i(z)
ÁS,=j} = Jtjiz)
j—1
(r-1) je ' dt,
.7= 1,2,-,
(5)
/• oo
f r— 1
e~* dt, ; = o.
We will treat this in more detail in §5. Let Lr = Lr(a) be the length of the rth longest cycle in a permutation of cycle
class a; we define Lr(a) = 0 if Za; < r. The probability density at t of the rth jump of the Poisson process counting to the left from iœ(z) is
itjz) -tj'1 exp [ - [Uz) - t]]Hr - 1)! , - co < t = tjz).
As with (5) then,
(6)
Pz{Lr = ;}=
V^z tJ exp[-[f,(z)-«]]*,
Jt3(z)
(r-l)l
; = 1,2,-
=J-l[aZ(r-T)!«1p[-[<»co-*]]*;=. o.
We consider this in detail in the next section. We conclude the present section with some analytical preliminaries regarding
the tjiz). With z = e_s, 0
License or copyright restrictions may apply to redistribution; see https://www.ams.org/journal-terms-of-use
1966]
ORDERED LENGTHS IN A RANDOM PERMUTATION
345
tœie's)-tjie-s)=
£ e~ks
Z -r-f,e '
y-1,2,.».
On the interval {y: fes< y < (fe4- í)s} there obtains
e-ks
e-y
e-(*+i)S
ks >-> y (k 4- l)s and
e-*s
/• (fc+l)s g-j>
e-(fc+l)s
—r— >
k ]ks
— <^y > —i—t->
y
k+ l
Summing on fe, we have bounds
£ e~ks
(7)
Eijs) < Z -t- < £((J - l)s), / = 1,2,.
where
£(*) =
jx
- dy,
y
0 < x < co,
( = + co, x = 0),
is the exponential integral. The mapping x -* £(x) is an order reversing homeomorphism of 0 < x < co onto itself, so for each j = 1,2,— and each 0 < s < oo the equation
(8)
Z ^ = £(x/S))
has a unique root 0 < x7(s) < co. Using (7), we obtain ij — l)s < Xjis)
In §5 we will need a closer estimate for x¡(s). From the well-known identity
Cx 1 - e~y
(9)
£(x) = -
dy -logx-y,
0 < x < oo,
Jo y
(wherey = 0.577 ••• is Euler's constant) we obtain, since Eix,is)) = log(1/(1 —z)),
do)
Xi(s) = (1_z)e Vexp[J0 —y—dy\
= il-z)e~y + Oi\-z)2, z-»l.
For the last expression we have used the bound
*l(s) 1 - e y
- dy < x,is) < s Jo
given in the preceding paragraph. Although we do not use it, the following expression for x/s) may be of interest.
We find Xjis) = Zp =1Apij)sp, convergent for all s, with the first few coefficients
License or copyright restrictions may apply to redistribution; see https://www.ams.org/journal-terms-of-use
346
L. A. SHEPP AND S. P. LLOYD
[February
A,íj)= exp[r'Ü)/rO)]= exp[-y+ ¿ (l/fe)J
11 1 J -^ 2 ++ K247;T++ 478öjä2+-'>
A2(j)= A,ÍJ)^A,ÍJ)-j+1^
1 0 2-Ï4X + —j +
1_
A3U) = -^ { [ Alij) ~j + 2~] [5AlU) - 3 (j - ï)
12
~ °-9W+ -•
^Ü)~ -281Ö+--
We omit the proof.
4. The rth longest cycle. According of the rth longest cycle under Pz is
<*> fO+iW rt c_\ _ tf-i
£z{(Lr)"} = Z JM
7 = 1 J/j(z)
fan,
v ~ U!
to (6), the mth moment **P [ - [*„(*) -«]]<**,
of the length m, r = 1,2, - .
Under the change of variable iœ(z) —í = £(x), this becomes
£z{(L,n= Sfp
VW'1 e-™Çdx,
with z = e~' again and x/s) given by (8). Now xj(s)
quantity sm£z{(Lr)m} is bounded above by Z; = i [*/+i(5XTty and below by
l£i [*/«)]% with
/•»,»♦«(»)
i"j =
dp(x),
These bounds are just the upper and lower Darboux sums for the Darboux-Stieltjes
integral jj°ús)xmdpíx) based on the mesh determined by x/s), j = 1,2, — . From
ij — i)s < Xjis)
ass->0.As z-> 1 then, we have s = log(l/z)->0, s/(l-z)^l,x1(s)->0,
and hence
(11)
lim (í-^LEz{ÍLrr}
z-t,
mi
where the constants Gr m are
= Gr,m,
"i?'}'""'
r — i,¿, ■••,
License or copyright restrictions may apply to redistribution; see https://www.ams.org/journal-terms-of-use
1966]
ORDERED LENGTHS IN A RANDOM PERMUTATION
347
r•xo™o „m-1— 1 rlrE/',AjxT),"]i-1
...
(12)
Jr,m= Jo ~^T (r - 1)! CXP[~ {X)~ ^
In §6 we prove that £„{(Lr)m} is monotone nondecreasing in n. If we apply the Karamata-Hardy-Littlewood Tauberian theorem [7, p. 143], [8, p. 203] to (11) we obtain
(13)
UMB.^'j-G....
«-►00
—«•••••
» B= ^5 -^-5 " * J
for the limiting form of the moments of LJn. Thecasem = 1, r = 1 is the limit of Golomb mentioned in the Introduction:
(14) lim£„(A) = f'expr-x-r^-'/^dy dx).
n->oo \ n )
JO
I
Jx
The numbers Grm have the property
lim im + l)rGrm =-¡—,
m = 0,1, — .
We sketch the proof. The change of variable £(x) = x in (12) gives
J0 m! (r-1)!
where £(t) is the function inverse to £(x): ^(£(x)) = x, 0 < x < oo. For large r the density i'-1e~zj(r — 1)! is negligible if t is not large. From the identity (9) we obtain easily £(t) ~ e~T~y, t-> oo, for the asymptotic form of £(t). We substitute this in the expression for Grm and the result follows. (The argument can be made rigorous; we omit the details.)
For the limiting distribution of LJn we seek a distribution Fr(£)> 0 ;£ f g 1, with the property J0' £m dFXQ = Gr m, m = 0,1, •••. If such an Fr exists then
IkíJf^lí^F^
n->oo
0SÍS1,
is obtained according to the method of moments [9, p. 27]. From (12) it is straightforward that if there is an Fr such that
(15)
s ( - îrTjEOo]'
rr (r-l)!(p-r)!p'
0 < y < oo,
License or copyright restrictions may apply to redistribution; see https://www.ams.org/journal-terms-of-use
348
L. A. SHEPP AND S. P. LLOYD
[February
Mrs. L. A. Needham of our organization has obtained the following numerical values for the first moments Gr,.
r
Grl
2VGr>1
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 (sum)
0.62432997 0.20958090 0.08831609 0.04034198 0.01914548 0.00927494 0.00454696 0.00224518 0.00111357 0.00055387 0.00027599 0.00013768 0.00006874 0.00003434 0.00001716 0.00000857 0.00000429 0.00000214 0.00000107 0.00000054 0.00000027 0.00000013 0.00000007 0.99999993
2.2239538 1.4931151 1.2583788 1.1496320 1.0911837 1.0572380 1.0366046 1.0236979 1.0154706 1.0101584 1.0066977 1.0044290 1.0029350 1.0019480 1.0012943 1.0008607 1.0005727 1.0003812 1.0002538 1.0001690 1.0001125 1.0000749 1.0000498
Table 1. Grl and 2reyGr_,forr= 1(1)23.
then F, will have moments Gr m. Now, £(y) is the Laplace transform £(y)
- So e~yufiu)du of
fiu) =0, 0 ^ u < 1,
= —, 1 g U < 00,
License or copyright restrictions may apply to redistribution; see https://www.ams.org/journal-terms-of-use
1966]
ORDERED LENGTHS IN A RANDOM PERMUTATION
349
so that the rightmost member of (15) is indeed a Laplace transform. Inverting, we obtain
, Pffl-/v/{ (-W"
f
f du, dup
1
Ul+...+Upál/í
= 0, - ^ Í < CO, r
for the limiting distribution of LJn. We observe that for given r, 1 —£/£) is the sum of q — r+l elementary integrals on the interval iq + 1)_1 < Ç :£ q'1, q = r,r + l, — . When r = 1 the above is Goncharov's formula for the limiting distribution of L,/n [2].
5. The rth shortest limiting positions
i,. =
cycle. As z -*1,
3!
limi/z)
z-fl
J-i
= Z 1
the endpoints iy(z) of our
i
-rr, J= 2,3,-,
K
model
move to
= 0,
j = 1,
and Sr has the z limiting distribution
(16) limPz{Sr=j}= f—Íl—-C-' dt,
In §6 we will show that the Tauberian side condition
¿«1,2,-.
\Pn{Sr=j}-Pn-,{Sr=j}\^
-|,
n = l,2,-,
holds, so from (16) and the KHLT theorem we have
lim Pn{Sr=j} = fJ ' f_ e"' di, ¿ = 1,2,-.
The tail of this distribution is asymptotically
c-'pog/j |r-l
(r-1)!;2 '
using the well-known estimate
*-? 4=1o^'+^+o(t)-
We see that the limiting distribution of Sr has infinite mean.
License or copyright restrictions may apply to redistribution; see https://www.ams.org/journal-terms-of-use