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
L´ 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!).
