The number of inversions in permutations Median versus A A large for a Luria Delbruck like distribution with parameter A Sum of positions of records in random permutations Merten's theorem for toral automorphisms Representations of numbers as ∑n

Guy Louchard

Description

The number of inversions in permutations Median versus A (A large) for a Luria-Delbruck-like distribution, with parameter A Sum of positions of records in random permutations Merten's theorem for toral automorphisms Representations of numbers as ∑n k=?n ?kk The q-Catalan numbers A simple case of the Mahonian statistic Asymptotics of the Stirling numbers of the first kind revisited The Saddle point method in combinatorics asymptotic analysis: successes and failures (A personal view) Guy Louchard May 31, 2011 Guy Louchard The Saddle point method in combinatorics asymptotic analysis: successes and failures (A personal view)

• random permutations


• lindeberg-levy conditions


• ?n ?kk


• lower order


• xn characterized


• limit

Informations

• Publié par: profil-urra-2012
• Nombre de lectures: 3
• Langue: English
• Poids de l'ouvrage: 2 Mo

Extrait

The number of inversions in permutations

The asy

Median versusA(

Saddle point method in combinatorics mptotic analysis: successes and failures (A personal view)

Guy

May

Guy Louchard

Louchard

31,

2011

The Saddle point method in combinatorics asymptotic analysis:

The number of inversions in permutations Outline

1

2

3

4

5

6

7

8

The

Median versusA(

number of inversions in permutations

Median versusA(Alarge) for a Luria-Delbruck-like distribution, with parameterA

Sum of positions of records in random permutations

Merten’ th m for toral automorphisms s eore Representations of numbers as P n k=−n ε k k

The

q-Catalan numbers

A simple case of the Mahonian statistic

Asymptotics

of the

Stirling numbers of the first kind

Guy Louchard

revisited

The Saddle point method in combinatorics asymptotic analysis:

The number of inversions in permutationsMedian versusA( The number of inversions in permutations

Leta 1 . . .a n be a permutation of the set{1, . . . ,n}. Ifa i >a k and i<k, the pair (a i ,a k ) is called aninversion;I n (j) is the number of permutations of lengthnwithjinversions. Here, we show how to extend previous results using thesaddle point method to asymptotics for g., leads, e.. ThisI αn+β (γn+δ), for integer constantsα,β,γ,δand more general ones as well. With this technique, we will also show the known result thatI n (j) isasymptotically normal, with additional corrections. The generating function for the numbersI n (j) is given by n Φ n (z) = X I n (j)z j = (1−z) −n Y (1−z i ). j≥0i=1

By Cauchy’s theorem, I n (j)= 1 2πi Z C whereCis, say, a circle around t Guy Louchard

Φ n (z) d z j z +1 ,

The Saddle point method in

combinatorics asymptotic analysis:

The number of inversions in permutationsMedian versusA( The Gaussian limit,j=m+xσ,m=n(n−1)/4

Actually, we obtain here local limit theorems with some corrections (=lower order terms). The Gaussian limit ofI n (j) is easily derived from the generating function Φ n (zisthee,dI.dnoisndntiv)yc(ou-L´etbheerLgisnindge generating function corresponds to a sum fori= 1, . . . ,nof independent, uniform [0..i− an exercise,1] random variables. As let us recover this result with thesaddle point method,with an additional correctionof order 1/n. We have, for the random variableX n characterized by

withJ n :=I n /n!,

P(X n =j) =J n

(j),

m:=E(X n ) =n(n−1)/4, σ 2 :=V(X n ) =n(2n+ 5)(n−1)/72.

Guy Louchard

The Saddle point method in combinatorics asymptotic analysis:

The number of inversions in permutations

Median versusA(

We know that I n (j 1 2 )= πi Z Ω e S(z) dz where Ω is inside the analyticity domain of the integrand, the origin, passes through the saddle pointz˜ and

z ˜

is

the

solution of

S

= ln(Φ n (z))−(j+ 1) lnz,

S (1) (z) = ˜

0.

Figure 1 shows the real part ofS(z) together with a path through the saddle point.

Guy Louchard

encircles

Ω

(1)

The Saddle point method in combinatorics asymptotic analysis:

The number of inversions in permutations

Figure

1:

Real

Median versusA(

part

of

S(z).

Guy Louchard

Saddle-point

and

path,

n

= 10

The Saddle point method in combinatorics asymptotic analysis:

The number of inversions in permutationsMedian versusA(

We have J n (j) = n!2 1 πi Z Ω exp h S(z˜)+S (2) (z˜)(z−˜z) 2 /2!+ X ∞ l=3

S (l) (z˜)(z−z˜) l /l! i dz

(note carefully that the linear term vanishes). Setz=z˜ +iτ. This gives

J n (j) = n 1 !2π exp[S(˜z)] Z ∞ −∞ exp h S (2) (z˜)(iτ) 2 /2!+ ∞ X S (l) (z˜)(iτ) l /l! i dτ. l=3 (2) We can now compute (2), for instance by using the classical trick of setting

∞ S (2) (z˜)(iτ) 2 /2! + X S (l) (˜z)(iτ) l /l! =−u 2 /2. l=3

Guy Louchard

The Saddle point method in combinatorics asymptotic analysis:

The number of inversions in permutations

Median versusA(

eps (to simplify, we

To justify this procedure, we proceed in three st usez˜ = 1). settingz=e iθ , we must show that the tail Z 2π−θ 0 S(z)

e dθ θ 0

isnegligiblefor someθ 0 , we must insure that acentral Gaussian

S(z)∼S(z˜) +S (2) (z˜)(z

integral

approximation

−˜z) 2 /2!

holds:

in the integration domain|θ| ≤θ 0 , by chosing for instance S (2) (˜z)θ 02 → ∞,S (3) (z˜)θ 3 0 →0,n→ ∞, me must have atail completion incomplete Gaussian: the integral must be asymptotic to a complete one.

Guy Louchard

The Saddle point method in combinatorics asymptotic analysis:

The number of inversions in permutationsMedian versusA(

We

splitthe exponent of the integrand

S

S 1

S 2

:=

:=

:=

S 1 +S 2 , n

as

X ln(1−z i ), i=1 −nln(1−z)−(j+ 1) lnz.

(3)

Set d i S = S (i) : dz i . Set ˜z:=z ∗ −ε, wherez ∗ = lim n→∞ z˜. Here,z ∗  (This= 1. notation always means thatz ∗ is the approximate saddle point and z˜ is the exact saddle point; they differ by a quantity that has to be computed to some degree of accuracy.) This leads, to first order, to

(n+ 1) 2 /4−3n/4−5/4−j] + [−(n+ 1) 3 /36 + 7(n+ 1) 2 /24−49n/72−91/72−j]ε= 0. (4)

Guy Louchard

The Saddle point method in combinatorics asymptotic analysis:

The number of inversions in permutations

Median versusA(

Setj=m+xσ shows that, asymptotically, Thisin (4).εis given by aPuiseux seriesof powers ofn −1/2 , starting with−6x/n 3/2 . To obtain the next terms, we compute the next terms in the expansion of (1), i.e., we first obtain

[(n+ 1) 2 /4−3n/4−5/4−j] + [−(n+ 1) 3 /36 + 7(n+ 1) 2 /24−49n/72−91/72−j]ε + [−j−61/48−(n+ 1) 3 /24 + 5(n+ 1) 2 /16−31n/48]ε 2 = 0. (5)

Guy Louchard

The Saddle point method in combinatorics asymptotic analysis: