LINEBURG

r

N (r1 , . . . , rk )z11 · · · zkk = 2 ’

F (z1 , . . . , zk ) = (1 + zj ) . (13.5)

j=1

r1 ,...,rk ≥0

We have f (k, n) = N (n, . . . , n), and so we need the diagonal terms of F = F (z 1 , . . . , zk ). The

function F is rational, so its singularity is small. Moreover, the singularities of F are di¬cult

131

to visualize. However, in any single variable F is simple. We take advantage of this feature.

Let

k’1

A(z) = (1 + zj ) , (13.6)

j=1

k’1 ,

where z stands for (z1 , . . . , zk’1 ) ∈ and expand

£

’1

«

k ∞

A(z)m zk

m

’1

2 ’ (1 + zj ) = (2 ’ A(z)(1 + zk )) = . (13.7)

(2 ’ A(z))m+1

m=0

j=1

Therefore

A(z)m

1 dz1 dzk’1

N (r1 , . . . , rk’1 , m) = ··· · · · rk’1 . (13.8)

(2 ’ A(z))m+1 z11 +1

r

(2πi)k’1 zk’1

The function whose coe¬cients we are trying to extract is now A(z) m /(2 ’ A(z))m+1 , which is

still rational. However, the interesting case for us is m ’ ∞, which transforms the singularity

into a large one. We are interested in the case r 1 = r2 = · · · = rk’1 = r = n. Then the integral

in (13.8) can be shown to have a saddle point at z j = ρ, 1 ¤ j ¤ k ’ 1, where ρ = 21/k ’ 1,

and one obtains the estimate [178]

2 ’1)/(2k)

f (k, n) = r n n’(k’1)/2 {(ρπ (k’1)/2 k 1/2 )’1 2(k + O(n’1/2 )} as n ’ ∞ . (13.9)

The examples above of applications of the multidimensional saddle point method all dealt

with problems in a ¬xed dimension as various other parameters increase. A much more chal-

lenging problem is to apply this method when the dimension varies. A noteworthy case where

this has been done successfully is the asymptotic enumeration of graphs with a given degree

sequence by McKay and Wormald [279].

Example 13.3. Simple labeled graphs of high degree. Let G(n; d 1 , . . . , dn ) be the number of

labeled simple graphs on n vertices with degree sequence d 1 , d2 , . . . , dn . Then G(n; d1 , . . . , dn )

dd d

is the coe¬cient of z1 1 z2 2 · · · znn in

n

F= (1 + zj zk ) , (13.10)

j,k=1

j<k

and so by Cauchy™s theorem

F z1 1 ’1 · · · zn n ’1 dz1 · · · dzn ,

’d

G(n; d1 , . . . , dN ) = (2πi)’n ’d

··· (13.11)

132

where each integral is on a circle centered at the origin. Let all the radii be equal to some r > 0.

The integrand takes on its maximum absolute value on the product of these circles at precisely

the two points z1 = z2 = · · · = zn = r and z1 = z2 = · · · = zn = ’r. If d1 = d2 = · · · = dn , so

that we consider only regular graphs, McKay and Wormald [279] show that for an appropriate

choice of the radius r, these two points are saddle points of the integrand, and succeed through

careful analysis in proving that if dn is even, and min(d, n ’ d ’ 1) > cn(log n) ’1 for some

c > 2/3, then

’1 + 10» ’ 10»2

1/2 d+1 n’d ’n/2

+ O(n’ζ )

G(n, d, d, . . . , d) = 2 (2πn» (1 ’ ») ) exp (13.12)

12»(1 ’ »)

as n ’ ∞ for any ζ < min(1/4, 1/2 ’ 1/(3c)), where » = d/(n ’ 1).

McKay and Wormald [279] also succeed in estimating the number of irregular graphs,

provided that all the degrees dj are close to a ¬xed d that satis¬es conditions similar to those

above. The proof is more challenging because di¬erent radii are used for di¬erent variables

and the result is complicated to state. .

The McKay-Wormald estimate of Example 13.3 is a true tour de force. The problem is

that the number of variables is n and so grows rapidly, whereas the integrand grows only like

exp(cn2 ) at its peak. More precisely, after transformations that remove obvious symmetries

2

are applied the integrand near the saddle point drops o¬ like exp(’n θj ). This is just barely

to allow the saddle point method to work, and the symmetries in the problem are exploited

to push the estimates through. This approach can be applied to other problems (cf. [278]),

but it is hard to do. On the other hand, when the number of variables grows more slowly,

multidimensional saddle point contributions can be estimated without much trouble.

So far this section has been devoted primarily to multivariate functions with large singu-

larities. However, there is also an extensive literature on small singularities. The main thread

connecting most of these works is that of central and local limit theorems. Bender [32] initiated

this development in the setting of two-variable problems. We present some of his results, since

they are simpler than the later and more general ones that will be mentioned at the end of

this section.

Consider a double sequence of numbers a n,k ≥ 0. (Usually the an,k are = 0 only for

0 ¤ k ¤ n.) We will assume that

An = an,k < ∞ (13.13)

k

133

for all n, and de¬ne the normalized double sequence

pn (k) = an,k /An . (13.14)

We will say that an,k satis¬es a central limit theorem if there exist functions σ n and µn such

that

x

’1/2

exp(’t2 /2)dt = 0 .

lim sup pn (k) ’ (2π) (13.15)

n’∞ x ’∞

k¤σn x+µn

2

Equivalently, pn (k) is asymptotically normal with mean µ n and variance σn .

Theorem 13.1. [32]. Let an,k ≥ 0, and set

an,k z n wk .

f (z, w) = (13.16)

n,k≥0

Suppose that there are (i) a function g(s) that is continuous and = 0 near s = 0, (ii) a function

r(s) with bounded third derivative near s = 0, (iii) an integer m ≥ 0, and (iv) , δ > 0 such

that

m

z g(z)

f (z, es ) ’

1’ (13.17)

r(s) 1 ’ z/r(s)

is analytic and bounded for

|z| < , |z| < |r(0)| + δ . (13.18)

Let

σ 2 = µ2 ’ r (0)/r(0) .

µ = ’r (0)/r(0), (13.19)

If σ = 0, then (13.15) holds with µn = nµ and σn = nσ 2 .

2

A central limit theorem is useful, but it only gives information about the cumulative sums

of the an,k . It is much better to have estimates for the individual a n,k . We say that pn (k) (and

an,k ) satisfy a local limit theorem if

lim sup σn pn ( σn x + µn ) ’ (2π)’1/2 exp(’x2 /2) = 0 . (13.20)

n’∞ x

In general, we cannot derive (13.20) from (13.15) without some additional conditions on the

an,k , such as unimodality (see [32]). The other approach one can take is to derive (13.20) from

conditions on the generating function f (z, w).

134

Theorem 13.2. [32]. Suppose that an.k ≥ 0, and let f (z, w) be de¬ned by (13.16). Let

’∞ < a < b < ∞. De¬ne

R( ) = {z : a ¤ Re(z) ¤ b, |Im(z)| ¤ } . (13.21)

Suppose there exist > 0, δ > 0, an integer m ≥ 0, and function g(s) and r(s) such that

(i) g(s) is continuous and = 0 for s ∈ R( ),

(ii) r(s) = 0 and has a bounded third derivative for s ∈ R( ),

(iii) for s ∈ R( ) and |z| ¤ |r(s)|(1 + δ), the function de¬ned by (13.17) is analytic and

bounded,

(iv)

2

r (±) r (±)

= for a¤±¤b , (13.22)

r(±) r(±)

(v) f (z, es ) is analytic and bounded for

|z| ¤ |r(Re(s))|(1 + δ) and s ¤ |Im(s)| ¤ π .

Then

nm e’±k g(±)

an,k ∼ as n’∞ (13.23)

m!r(±)m σ± (2π)1/2

uniformly for a ¤ ± ¤ b, where

k r (±)

=’ , (13.24)

n r(±)

2

k r (±)

2

σ± = ’ . (13.25)

n r(±)

There have been many further developments of central and local limit theorems for asymp-

totic enumeration since Bender™s original work [32]. Currently the most powerful and general

results are those of Gao and Richmond [155]. They apply to general multivariate problems,

not only two-variable ones. Other papers that deal with central and local limit theorems or

other multivariate problems with small singularities are [38, 42, 65, 96, 142, 143, 183, 227].

14. Mellin and other integral transforms

When the best generating function that one can obtain is an in¬nite sum, integral trans-

forms can sometimes help. There is a large variety of integral transforms, such as those of

135

Fourier and Laplace. The one that is most commonly used in asymptotic enumeration and

analysis of algorithms is the Mellin transform, and it is the only one we will discuss exten-

an xn /n! is an

sively below. The other transforms do occur, though. For example, if f (x) =

exponential generating function of the sequence a n , then the ordinary generating function of

an can be derived from it using the Laplace transform

∞ ∞

n ’1

xn exp(’x)dx

f (xy) exp(’x)dx = an y (n!)

0 0

n

(14.1)

n

= an y .

n

(This assumes that the an are small enough to assure the integrals above converge and the

interchange of summation and integration is valid.) Related integral transforms can be used

to transform generating functions into other forms. For example, to transform an ordinary

an un into an exponential one, we can use

generating function F (u) =

1

F (u) exp(w/u)du . (14.2)

2πi |u|=r

The basic references for asymptotics of integral transforms are [89, 95, 299, 347]. This

section will only highlight some of the main properties of Mellin transforms and illustrate how

they are used. For a more detailed survey, especially to analysis of algorithms, see [137].

Let f (t) be a measurable function de¬ned for real t ≥ 0. The Mellin transform f — (z) of

f (t) is a function of the complex variable z de¬ned by

∞

—

f (t)tz’1 dt .

f (z) = (14.3)

0

If f (t) = O(t± ) as t ’ 0+ and f (t) = O(tβ ) as t ’ ∞, then the integral in (14.3) converges and

de¬nes f — (z) to be an analytic function inside the “fundamental domain” ’± < Re(z) < ’β.

As an example, for f (t) = exp(’t), we have f — (z) = “(z) and ± = 0, β = ’∞. There is an

inversion formula for Mellin transforms which states that

c+i∞

1

f — (z)t’z dz ,

f (t) = (14.4)

2πi c’i∞

and the integral is over the vertical line with Re(z) = c. The inversion formula (14.4) is valid

for ’± < c < ’β, but much of its strength in applications comes from the ability to shift the

contour of integration into wider domains to which f — (z) can be analytically continued.

The advantage of the Mellin transform is due largely to a simple property, namely that if

g(t) = af (bx) for b real, b > 0, then

g — (z) = ab’z f — (z) . (14.5)

136

This readily extends to show that if

F (t) = »k f (·k t) (14.6)

k

(where the »k and ·k > 0 are such that the sum converges and F (t) is well behaved), then

’z

F — (z) = f — (z) .

»k ·k (14.7)

k

In particular, if

∞

F (t) = f (kt) , (14.8)

k=1

then

∞

—

k ’z f — (z) = ζ(z)f — (z) ,

F (z) = (14.9)

k=1

where ζ(z) is the Riemann zeta function.

Example 14.1. Runs of heads in coin tosses. What is R n , the expected length of the longest

run of heads in n tosses of a fair coin? Let p(n, k) be the probability that there is no run of k

heads in a coin tosses. Then

n

Rn = k(p(n, k + 1) ’ p(n, k)) . (14.10)

k=1

We now apply the estimates of Example 9.2. To determine p(n, k), we take A = 00 · · · 0, and

then CA (z) = z k’1 + z k’2 + · · · + z + 1, so CA (1/2) = 1 ’ 2’k . Hence (9.19) shows easily that

in the important ranges where k is of order log n, we have

p(n, k) ∼ exp(’n2’k ) , (14.11)

=

and there Rn is approximated well by

∞

k(exp(’n2’k’1 ) ’ exp(’n2’k )) .

r(n) = (14.12)

k=0

The function r(t) is of the form (14.6) with

»k = k, ·k = 2’k , f (t) = exp(’t/2) ’ exp(’t) , (14.13)

is easily seen to be well behaved, and so for ’1 < Re(z) < 0,

∞

—

k2kz f — (z) = 2z (1 ’ 2z )’2 f — (z) .

r (z) = (14.14)

k=0

137

Next, to determine f — (z), we note that for Re(z) > 0 we have

∞ ∞ ∞

— z’1 ’t/2 z’1

e’t tz’1 dt

f (z) = f (t)t dt = e t dt ’

0 0 0

z

= (2 ’ 1)“(z) . (14.15)

By analytic continuation this relation holds for ’1 < Re(z), and we ¬nd that for ’1 < Re(z) <

0,

r — (z) = 2z (2z ’ 1)’1 “(z) . (14.16)

We now apply the inversion formula to obtain

’1/2+i∞

1

2z (2z ’ 1)’1 “(z)t’z dz .

r(t) = (14.17)

2πi ’1/2’i∞

The integrand is a meromorphic function in the whole complex plane that drops o¬ rapidly on

any vertical line. We move the contour of integration to the line Re(z) = 1. The new integral

is O(t’1 ), and the residues at the poles (all on Re(z) = 0) will give the main contribution to

\ {0} coming from 2 z = 1, and

r(t). There are ¬rst order poles at z = 2πim log 2 for m ∈ ¢

a single second order pole at z = 0, since “(z) has a ¬rst order pole there as well. A short

computation of the residues gives

∞

(log 2)’1 “(’2πih(log 2)’1 ) exp(2πih log 2 t) + O(t’1 ) .

r(t) = log 2 t ’ (14.18)

h=’∞

There are other ways to obtain the same expansion (14.18) for r(t) (cf. [181]). The periodic

oscillating component in r(t) is common in problems involving recurrences over powers of 2.

This happens, for example, in studies of register allocation and digital trees [136, 138, 141].

The periodic function is almost always the same as the one in Eq. (14.18), even when the

combinatorics of the problem varies. Technically this is easy to explain, because of the closely

related recurrences leading to similar Mellin transforms for the generating functions.

Copyright Design by: Sunlight webdesign