1.2. Stirling’s formula 35
There are other interesting modes of convergence on random variables
and on distributions, such as convergence in total variation norm, in the
evy-Prokhorov metric, or in Wasserstein metric, but we will not need these
concepts in this text.
1.2. Stirling’s formula
In this section we derive Stirling’s formula, which is a useful approximation
for n! when n is large. This formula (and related formulae for binomial
coefficients)
(
n
m
)
will be useful for estimating a number of combinatorial
quantities in this text, and also in allowing one to analyse discrete random
walks accurately.
From Taylor expansion we have
xn/n!

ex
for any x 0. Specialising
this to x = n we obtain a crude lower bound
(1.44) n!
nne−n.
In the other direction, we trivially have
(1.45) n!
nn,
so we know already that n! is
within8
an exponential factor of
nn.
One can do better by starting with the identity
log n! =
n
m=1
log m
and viewing the right-hand side as a Riemann integral approximation to
n
1
log x dx. Indeed, a simple area comparison (cf. the integral test) yields
the inequalities
n
1
log x dx
n
m=1
log m log n +
n
1
log x dx
which leads to the inequalities
(1.46)
enne−n
n! en ×
nne−n,
so the lower bound in (1.44) was only
off9
by a factor of n or so.
One can improve these bounds further by using the trapezoid rule as
follows. On any interval [m, m+1], log x has a second derivative of
O(1/m2),
8One
can also obtain a cruder version of this fact that avoids Taylor expansion, by observing
the trivial lower bound n! (n/2)
n/2
coming from considering the second half of the product
n! = 1 · · · · · n.
9This illustrates a general principle, namely that one can often get a non-terrible bound for
a series (in this case, the Taylor series for en) by using the largest term in that series (which is
nn/n!).
Previous Page Next Page