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
n1
θ
π/2
0
+
Z
π/2
0
(n 1) cos
2
θ sin
n2
θ dθ
= 0 +
Z
π/2
0
(n 1)(1 sin
2
θ) sin
n2
θ dθ
= (n 1)(I
n2
I
n
)
So
I
n
=
n 1
n
I
n2
.
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
2n1
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
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.