38 1. Preparatory material

Remark 1.2.1. The dominated convergence theorem does not immediately

give any effective rate on the decay o(1) (though such a rate can eventually

be extracted by a quantitative version of the above argument. But one can

combine (1.50) with (1.47) to show that the error rate is of the form O(1/n).

By using fancier versions of the trapezoid rule (e.g., Simpson’s rule) one can

obtain an asymptotic expansion of the error term in 1/n; see [KeVa2007].

Remark 1.2.2. The derivation of (1.50) demonstrates some general prin-

ciples concerning the estimation of exponential integrals

eφ(x)

dx when φ

is large. First, the integral is dominated by the local maxima of φ. Then,

near these maxima,

eφ(x)

usually behaves like a rescaled Gaussian, as can

be seen by Taylor expansion (though more complicated behaviour emerges

if the second derivative of φ degenerates). So one can often understand the

asymptotics of such integrals by a change of variables designed to reveal the

Gaussian behaviour. This technique is known as Laplace’s method. A simi-

lar set of principles also holds for oscillatory exponential integrals

eiφ(x)

dx;

these principles are collectively referred to as the method of stationary phase.

One can use Stirling’s formula to estimate binomial coeﬃcients. Here is

a crude bound:

Exercise 1.2.1 (Entropy formula). Let n be large, let 0 γ 1 be fixed,

and let 1 ≤ m ≤ n be an integer of the form m = (γ + o(1))n. Show that

(

n

m

)

= exp((h(γ) + o(1))n), where h(γ) is the entropy function

h(γ) := γ log

1

γ

+ (1 − γ) log

1

1 − γ

.

For m near n/2, one also has the following more precise bound:

Exercise 1.2.2 (Refined entropy formula). Let n be large, and let 1 ≤ m ≤

n be an integer of the form m = n/2 + k for some k =

o(n2/3).

Show that

(1.51)

n

m

= (

2

π

+ o(1))√

2n

n

exp(−2k2/n).

Note the Gaussian-type behaviour in k. This can be viewed as an il-

lustration of the central limit theorem (see Section 2.2) when summing iid

Bernoulli variables X1,...,Xn ∈ {0, 1}, where each Xi has a 1/2 probability

of being either 0 or 1. Indeed, from (1.51) we see that

P(X1 + · · · + Xn = n/2 + k) = (

2

π

+

o(1))√

1

n

exp(−2k2/n)

when k =

o(n2/3),

which suggests that X1 + · · · + Xn is distributed roughly

like the Gaussian N(n/2,n/4) with mean n/2 and variance n/4.