Introduction to Information Theory
Lead instructor: Seth Lloyd
4.1 Fundamental Formula of Information » A note on Stirling's Approximation
During the lecture, it is stated that
2mmh=m-q(h)2q(h)-q(t)2q(t),
where q(h)=mh/m is the probability of heads and q(t)=(m-mh)/m is the probability of tails.
In fact, the above statement is an approximation, based on the so-called “Stirling’s approximation” for the factorial, which states that
log2 n! ≈ n log2 n - (log2 e)*n
where e is “Eurler’s number” and equal to approximately 2.71828.
To understand the derivation, recall the formula ab=a!b!(a-b)!, and note that logarithms obey
log2 a*b = log2 a + log2 b
and
log2 a/b = log2 a - log2 b.
We can now re-derive the approximation mentioned in the lecture:
2mmh
=2m!mh!(m-mh)!
=log2 m! - log2 mh! - log2 (m-mh)!
≈ m log2 m - (log2 e)*m - mh log2 mh + (log2 e)*mh - (m-mh) log2 (m-mh) + (log2 e)*(m-mh)
= m log2 m - mh log2 mh - (m-mh) log2 (m-mh)
=- mh (log2 mh - log2 m) - (m-mh) (log2 (m-mh) - log2 m)
= - mh log2 (mh/m) - (m-mh) log2 ((m-mh)/m)
= m-q(h)2q(h)-q(t)2q(t)
Note that this approximation becomes almost exact when m, mh, and (m-mh) are all very large.
See the Wikipedia page for more information on Stirling’s approximation.