1Classical probability
IA Probability
1.3 Stirling’s formula
Before we state and prove Stirling’s formula, we prove a weaker (but examinable)
version:
Proposition. log n! ∼ n log n
Proof. Note that
log n! =
n
X
k=1
log k.
Now we claim that
Z
n
1
log x dx ≤
n
X
1
log k ≤
Z
n+1
1
log x dx.
This is true by considering the diagram:
x
y
ln x
ln(x − 1)
We actually evaluate the integral to obtain
n log n −n + 1 ≤ log n! ≤ (n + 1) log(n + 1) − n;
Divide both sides by n log n and let n → ∞. Both sides tend to 1. So
log n!
n log n
→ 1.
Now we prove Stirling’s Formula:
Theorem (Stirling’s formula). As n → ∞,
log
n!e
n
n
n+
1
2
= log
√
2π + O
1
n
Corollary.
n! ∼
√
2πn
n+
1
2
e
−n
Proof. (non-examinable) Define
d
n
= log
n!e
n
n
n+1/2
= log n! − (n + 1/2) log n + n
Then
d
n
− d
n+1
= (n + 1/2) log
n + 1
n
− 1.
Write t = 1/(2n + 1). Then
d
n
− d
n+1
=
1
2t
log
1 + t
1 − t
− 1.
We can simplifying by noting that
log(1 + t) − t = −
1
2
t
2
+
1
3
t
3
−
1
4
t
4
+ ···
log(1 − t) + t = −
1
2
t
2
−
1
3
t
3
−
1
4
t
4
− ···
Then if we subtract the equations and divide by 2t, we obtain
d
n
− d
n+1
=
1
3
t
2
+
1
5
t
4
+
1
7
t
6
+ ···
<
1
3
t
2
+
1
3
t
4
+
1
3
t
6
+ ···
=
1
3
t
2
1 − t
2
=
1
3
1
(2n + 1)
2
− 1
=
1
12
1
n
−
1
n + 1
By summing these bounds, we know that
d
1
− d
n
<
1
12
1 −
1
n
Then we know that
d
n
is bounded below by
d
1
+ something, and is decreasing
since
d
n
− d
n+1
is positive. So it converges to a limit
A
. We know
A
is a lower
bound for d
n
since (d
n
) is decreasing.
Suppose
m > n
. Then
d
n
−d
m
<
1
n
−
1
m
1
12
. So taking the limit as
m → ∞
,
we obtain an upper bound for d
n
: d
n
< A + 1/(12n). Hence we know that
A < d
n
< A +
1
12n
.
However, all these results are useless if we don’t know what
A
is. To find
A
, we
have a small detour to prove a formula:
Take
I
n
=
R
π/2
0
sin
n
θ
d
θ
. This is decreasing for increasing
n
as
sin
n
θ
gets
smaller. We also know that
I
n
=
Z
π/2
0
sin
n
θ dθ
=
−cos θ sin
n−1
θ
π/2
0
+
Z
π/2
0
(n − 1) cos
2
θ sin
n−2
θ dθ
= 0 +
Z
π/2
0
(n − 1)(1 − sin
2
θ) sin
n−2
θ dθ
= (n − 1)(I
n−2
− I
n
)
So
I
n
=
n − 1
n
I
n−2
.
We can directly evaluate the integral to obtain I
0
= π/2, I
1
= 1. Then
I
2n
=
1
2
·
3
4
···
2n − 1
2n
π/2 =
(2n)!
(2
n
n!)
2
π
2
I
2n+1
=
2
3
·
4
5
···
2n
2n + 1
=
(2
n
n!)
2
(2n + 1)!
So using the fact that I
n
is decreasing, we know that
1 ≤
I
2n
I
2n+1
≤
I
2n−1
I
2n+1
= 1 +
1
2n
→ 1.
Using the approximation
n
!
∼ n
n+1/2
e
−n+A
, where
A
is the limit we want to
find, we can approximate
I
2n
I
2n+1
= π(2n + 1)
((2n)!)
2
2
4n+1
(n!)
4
∼ π(2n + 1)
1
ne
2A
→
2π
e
2A
.
Since the last expression is equal to 1, we know that
A
=
log
√
2π
. Hooray for
magic!
This approximation can be improved:
Proposition (non-examinable). We use the 1
/
12
n
term from the proof above
to get a better approximation:
√
2πn
n+1/2
e
−n+
1
12n+1
≤ n! ≤
√
2πn
n+1/2
e
−n+
1
12n
.
Example. Suppose we toss a coin 2
n
times. What is the probability of equal
number of heads and tails? The probability is
2n
n
2
2n
=
(2n)!
(n!)
2
2
2n
∼
1
√
nπ
Example. Suppose we draw 26 cards from 52. What is the probability of getting
13 reds and 13 blacks? The probability is
26
13
26
13
52
26
= 0.2181.