LINEBURG


<< . .

 18
( 24)



. . >>

r
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.

<< . .

 18
( 24)



. . >>

Copyright Design by: Sunlight webdesign