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 coefficients. 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.
Previous Page Next Page