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

coeﬃcients)

(

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