LINEBURG


<< . .

 16
( 24)



. . >>

unique, at least for large n. (If there are several r ∈ (R 0 , R) for which r ’n f (r) achieves its
minimum value, then f (z) is pathological, and the standard saddle point method will not be
applicable. For functions f (z) with nonnegative coe¬cients, it is easy to show uniqueness of
the minimizing r, as was already discussed in Section 8.1.) Cauchy™s formula (10.6) is then
applied with the contour |z| = r0 . The reason for this choice is that for many functions, on
this contour the integrand is large only near z = r 0 , the contributions from the region near
z = r0 do not cancel each other, and remaining regions contribute little. This is in contrast
to the behavior of the integrand on other contours. By Cauchy™s theorem, any simple closed
contour enclosing the origin gives the correct answer. However, on most of them the integrand
is large, and there is so much cancellation that it is hard to derive any estimates. The circle
going through the saddle point, on the other hand, yields an integral that can be controlled
well by techniques related to Laplace™s method and the method of stationary phase that were
mentioned in Section 5.5. We illustrate with an example, which is a totally self-contained
application of the saddle point method to an extremely simple situation.

Example 12.1. Stirling™s formula. We estimate (n!) ’1 = [z n ] exp(z). The saddle point,
+ that minimizes r ’n exp(r), which is clearly
according to our de¬nition above, is that r ∈ ¡




r = n. Consider the contour |z| = n, and set z = n exp(iθ), ’π ¤ θ ¤ π. Then

1 exp(z)
[z n ] exp(z) = dz
z n+1
2πi |z|=n
π
1 ’n
exp(neiθ ’ niθ)dθ .
= n (12.2)
2π ’π

Since | exp(z)| = exp(Re(z)), the absolute value of the integrand in (12.2) is n ’n exp(n cos θ),
which is maximized for θ = 0. Now

eiθ = cos θ + i sin θ = 1 ’ θ 2 /2 + iθ + O(|θ|3 ) ,

so for any θ0 ∈ (0, π),
θ0 θ0
’n iθ
n’n exp(n ’ nθ 2 /2 + O(n|θ|3 ))dθ .
n exp(ne ’ niθ)dθ = (12.3)
’θ0 ’θ0



116
(It is the cancellation of the niθ term coming from ne iθ and the ’niθ term that came from
change of variables in z ’n that is primarily responsible for the success of the saddle point
method.) The O(n|θ|3 ) term in (12.3) could cause problems if it became too large, so we will
select θ0 = n’2/5 , so that n|θ|3 ¤ n’1/5 for |θ| ¤ θ0 , and therefore

exp(n ’ nθ 2 /2 + O(n|θ|3 )) = exp(n ’ nθ 2 /2)(1 + O(n’1/5 )) . (12.4)

Hence
θ0 θ
’n iθ ’1/5 ’n n
exp(’nθ 2 /2)dθ .
n exp(ne ’ niθ)dθ = (1 + O(n ))n e
’θ0 ’θ0

But
θ0 ∞ ∞
2 2
exp(’nθ 2 /2)dθ
exp(’nθ /2)dθ = exp(’nθ /2)dθ ’ 2
’θ0 ’∞ θ0
= (2π/n)1/2 ’ O(exp(’n1/5 /2)) ,

so
θ0
n’n exp(neiθ ’ niθ)dθ = (1 + O(n’1/5 ))(2π/n)1/2 n’n en . (12.5)
’θ0
On the other hand, for θ0 < |θ| ¤ π,

2 4
cos θ ¤ cos θ0 = 1 ’ θ0 /2 + O(θ0 ) ,

so
n cos θ ¤ n ’ n1/5 /2 + O(n’3/5 ) ,

and therefore for large n
π
n’n exp(neiθ ’ niθ)dθ ¤ n’n exp(n ’ n1/5 /3) ,
θ0

and similarly for the integral from ’π to ’θ 0 . Combining all these estimates we therefore ¬nd
that
(n!)’1 = [z n ] exp(z) = (1 + O(n’1/5 ))(2πn)’1/2 n’n en , (12.6)

which is a weak form of Stirling™s formula (4.3). (The full formula can be derived by using
more precise expansions for the integrand.)

Suppose we try to push through a similar argument using the contour |z| = 2n. This time,
instead of Eq. (12.2), we ¬nd
π
1
n
2’n n’n exp(2neiθ ’ niθ)dθ .
[z ] exp(z) = (12.7)
2π ’π


117
At θ = 0, the integrand is 2’n n’n exp(2n), which is exp(n) times as large as the value of the
integrand in (12.2). Since the two integrals do produce the same answer, and from the analysis
above we see that this answer is close to n ’n exp(n) in value, the integral in (12.7) must involve
tremendous cancellation. That is indeed what we see in the neighborhood of θ = 0. We ¬nd
that
exp(2neiθ ’ niθ) = exp(2n ’ nθ 2 + niθ + O(n|θ|3 )) , (12.8)

and the exp(niθ) term produces wild oscillations of the integrand even over small ranges of
θ. Trying to work with the integral (12.7) and proving that it equals something exponentially
smaller than the maximal value of its integrand is not a promising approach. By contrast, the
saddle point contour used to produce Eq. (12.2) gives nice behavior of the integrand, so that
it can be evaluated.
 




The estimates for n! obtained in Example 10.1 came from a simple application of the
saddle point method. The motivation for the choice of the contour |z| = n is provided by the
discussion at the end of the example; other choices lead to oscillating integrands that cannot
be approximated by a Gaussian, nor by any other nice function. The example above treated
only the exponential function, but it is easy to see that this phenomenon is general; a rapidly
oscillating term exp(ni±) for ± = 0 is present unless the contour passes through the saddle
point. When we do use this contour, and the Gaussian approximation is valid, we ¬nd that
for functions f (z) satisfying our assumptions we have the following estimate.

Saddle point approximation

’n
[z n ]f (z) ∼ (2πb(r0 ))’1/2 f (r0 )r0 as n ’ ∞ , (12.9)

where r0 is the saddle point (where r ’n f (r) is minimized, so that r0 f (r0 )/f (r0 ) = n)
and
2
f (r) f (r) f (r) f (r)
+ r2 ’ r2
b(r) = r =r r . (12.10)
f (r) f (r) f (r) f (r)


Example 12.2. Bell numbers. Example 5.4 showed how to estimate the Bell number B n
by elementary methods, starting with the representation (5.38). The exponential generating
function

zn
B(z) = Bn (12.11)
n!
n=0




118
satis¬es
B(z) = exp(exp(z) ’ 1) ,

as can be seen from (5.38) or by other methods (cf. [81]). The saddle point occurs at that
r0 > 0 that satis¬es
r0 exp(r0 ) = n , (12.12)

and
b(r0 ) = r0 (1 + r0 ) exp(r0 ) , (12.13)

so the saddle point approximation says that as n ’ ∞,

Bn ∼ n!(2πr0 exp(r0 ))’1/2 exp(exp(r0 ) ’ 1)r0 .
2 ’n
(12.14)

The saddle point approximation can be justi¬ed even more easily than for the Stirling estimate
of n!.
 




The above approximation is widely applicable and extremely useful, but care has to be
exercised is applying it. This is shown by the next example.

Example 12.3. Invalid application of the saddle point method. Consider the trivial example
f (z) = (1 ’ z)’1 , so that [z n ]f (z) = 1 for all n ≥ 0. Then f (r)/f (r) = (1 ’ r)’1 , and so
the saddle point is r0 = n/(n + 1), and b(r0 ) = r0 /(1 ’ r0 )2 = n(n + 1). Therefore if the
approximation (12.9) were valid, it would give
n
1
n ’1/2
[z ]f (z) ∼ (2πn(n + 1)) (n + 1) 1 +
n
∼ (2π)’1/2 e as n’∞. (12.15)

Since (2π)’1/2 e = 1.0844 . . . = 1 = [z n ]f (z), something is wrong, and the estimate (12.9) does
not apply to this function.
 




The estimate (12.9) gave the wrong result in Example 12.3 because the Gaussian approxi-
mation on the saddle point method contour used so e¬ectively in Example 12.1 (and in almost
all cases where the saddle point method applies) does not hold over a su¬ciently large re-
gion for f (z) = (1 ’ z)’1 . In Example 12.1 we used without detailed explanation the choice
θ0 = n’2/5 , which gave the approximation (12.5) for |θ| ¤ θ 0 , and yet led to an estimate for the
integral over θ0 < |θ| ¤ π that was negligible. This was possible because the third order term


119
(i.e., n|θ|3 ) in Eq. (12.5) was small. When we try to imitate this approach for f (z) = (1 ’ z) ’1 ,
we fail, because the third order term is too large. Instead of ne iθ ’ niθ, we now have

1 i
’ log(1 ’ r0 eiθ ) ’ niθ = ’ log(1 ’ r0 ) ’ n(n + 1)θ 2 ’ n2 (n + 1)θ 3 + · · · . (12.16)
2 6

More fundamentally, the saddle point method fails here because the function f (z) = (1 ’ z) ’1
does not have a large enough singularity at z = 1, so that when one traverses the saddle point
contour |z| = r0 , the integrand does not drop o¬ rapidly enough for a small region near the
real axis to provide the dominant contribution.
When can one apply the saddle point approximation (12.9)? Perhaps the simplest, yet still
general, set of su¬cient conditions for the validity of (12.9) is provided by requiring that the
function f (z) be Hayman-admissible. Hayman admissibility is described in De¬nition 12.1, in
the following subsection. Generally speaking, though, for the saddle point method to apply we
need the function f (z) to have a large dominant singularity at R, so that f (r) grows at least
as fast as exp((log(R ’ r))2 ) as r ’ R’ for R < ∞, and as fast as exp((log r)2 ) as r ’ ∞
for R = ∞. The faster the growth rate, the easier it usually is to apply the method, so that
exp(1/(1 ’ z)) or exp(exp(1/(1 ’ z))) can be treated easily.
In our application of the saddle point method to exp(z) in Example 12.1 we were content
to obtain a poor error term, 1 + O(n’1/5 ), in Stirling™s formula for n!. This was done to
simplify the presentation and concentrate only on the main factors that make the saddle point
method successful. With more care devoted to the integral one can obtain the full asymptotic
expansion of n!. (Only the range |θ| ¤ θ 0 has to be considered carefully.) This is usually true
when the saddle point method is applicable.
This section provided a sketchy introduction to the saddle point method. For a much more
thorough presentation, including a discussion of the topographical view of the integrand and
the “hill-climbing” interpretation of the contour of integration, see [63].

12.2. Admissible functions

The saddle point method is a powerful and ¬‚exible tool, but in its full generality it is often
cumbersome to apply. In many situations it is possible to apply general theorems derived
using the saddle point method that give asymptotic approximations that are not the sharpest
possible, but which allow one to avoid the drudgery of applying the method step by step. The
general theorems that we present were proved by Hayman [204] and by Harris and Schoenfeld


120
[198]. We next describe the classes of functions to which these theorems apply, and then present
the estimates one obtains for them. It is not always easy to verify that these de¬nitions hold,
but it is almost always easier to do this than to apply the saddle point method from scratch.
It is worth mentioning, furthermore, that for many generating functions, there are conditions
that guarantee that they satisfy the hypotheses of the Hayman and the Harris-Schoenfeld
theorems. These conditions are discussed later in this section.
The de¬nition below is stated somewhat di¬erently than the original one in [204], but can
be shown to be equivalent to it.

De¬nition 12.1. A function

fn z n
f (z) = (12.17)
n=0
is admissible in the sense of Hayman (or H-admissible) if

i) f (z) is analytic in |z| < R for some 0 < R ¤ ∞,

ii) f (z) is real for z real, |z| < R,

iii) for R0 < r < R,
max |f (z)| = f (r) , (12.18)
|z|=r

iv) for

f (r)
a(r) = r , (12.19)
f (r)
2
f (r) f (r) f (r)
+ r2 ’ r2
b(r) = ra (r) = r , (12.20)
f (r) f (r) f (r)

and for some function δ(r), de¬ned in the range R 0 < r < R to satisfy 0 < δ(r) < π, the
following three conditions hold:

f (reiθ ) ∼ f (r) exp(iθa(r) ’ θ 2 b(r)/2)
a)

as r ’ R uniformly for |θ| < δ(r), (12.21)



f (reiθ ) = o(f (r)b(r)’1/2 )
b)

as r ’ R uniformly for |θ| < δ(r), (12.22)



c) b(r) ’ ∞ as r ’ R. (12.23)

121
For H-admissible functions, Hayman [204] proved a basic result that gives the asymptotics
of the coe¬cients.

Theorem 12.1. If f (z), de¬ned by Eq. (12.17), is H-admissible in |z| < R, then

(a(r) ’ n)2
’1/2 ’n
fn = (2πb(r)) f (r)r exp ’ + o(1) (12.24)
b(r)

as r ’ R, with the o(1) term uniform in n.

If we choose r = rn to be a solution to a(rn ) = n, then we obtain from Theorem 12.1 a
simpler result. (The uniqueness of r n follows from a result of Hayman [204] which shows that
a(r) is positive increasing in some range R 1 < r < R, R1 > R0 .)

Corollary 12.1. If f (z), de¬ned by Eq. (12.17), is H-admissible in |z| < R, then

fn ∼ (2πb(rn ))’1/2 f (rn )rn as n ’ ∞ ,
’n
(12.25)

where rn is de¬ned uniquely for large n by a(r n ) = n, R0 < rn < R.

Corollary 12.1 is adequate for most situations. The advantage of Theorem 12.1 is that
b(r) 1/2 . (Note that the
it gives a uniform estimate over the approximate range |a(r) ’ n| ¤




estimate (12.24) is vacuous for |a(r) ’ n| b(r) ’1/2 ’ ∞.) Theorem 12.1 shows that the fn r n
are approximately Gaussian in the central region.
There are many direct applications of the above results.

Example 12.4. Stirling™s formula. Let f (z) = exp(z). Then f (z) is H-admissible for R = ∞;
conditions i)“iii) of De¬nition 12.1 are trivially satis¬ed, while a(r) = r, b(r) = r, so iv) also
holds for R0 = 0, δ(r) = r ’1/3 , say. Corollary 12.1 then shows that

1
∼ (2πn)’1/2 en n’n as n ’ ∞ ,
fn = (12.26)
n!

since rn = n, which gives a weak form of Stirling™s approximation to n!.
 




In many situations the conditions of H-admissibility are much harder to verify than for
f (z) = exp(z), and even in that case there is a little work to be done to verify that condition
iv) holds. However, many of the generating functions one encounters are built up from other,
simpler generating functions, and Hayman [204] has shown that often the resulting functions
are guaranteed to be H-admissible. We summarize some of Hayman™s results in the following
theorem.

122
Theorem 12.2. Let f (z) and g(z) be H-admissible for |z| < R ¤ ∞. Let h(z) be analytic in
|z| < R and real for real z. Let p(z) be a polynomial with real coe¬cients.

i) If the coe¬cients an of the Taylor series of exp(p(z)) are positive for all su¬ciently large
n, then exp(p(z))) is H-admissible in |z| < ∞.

ii) exp(f (z)) and f (z)g(z) are H-admissible in |z| < R.

iii) If, for some · > 0, and R1 < r < R,

max |h(z)| = O(f (r)1’· ) , (12.27)
|z|=r

then f (z) + h(z) is H-admissible in |z| < R. In particular, f (z) + p(z) is H-admissible
in |z| < R and, if the leading coe¬cient of p(z) is positive, p(f (z)) is H-admissible in
|z| < R.


Example 12.5. H-admissible functions. a) By i) Theorem 12.2, exp(z) is H-admissible, so
we immediately obtain the estimate (12.26), which yields Stirling™s formula. b) Since exp(z)
is H-admissible, part iii) of Theorem 12.2 shows that exp(z) ’ 1 is H-admissible. c) Applying
part ii) of Theorem 12.2, we next ¬nd that exp(exp(z) ’ 1) is H-admissible, which yields the
asymptotics of the Bell numbers.
 




Hayman™s results give only ¬rst order approximations for the coe¬cients of H-admissible
functions. In some circumstances it is desirable to obtain full asymptotic expansions. This is
possible if we impose additional restrictions on the generating function. We next state some
results of Harris and Schoenfeld [198].

De¬nition 12.2. A function f (z) de¬ned by Eq. (12.17) is HS-admissible provided it is ana-
lytic in |z| < R, 0 < R ¤ ∞, is real for real x, and satis¬es the following conditions:

<< . .

 16
( 24)



. . >>

Copyright Design by: Sunlight webdesign