# Complexity Explorer Santa Fe Institute

Your progress is not being saved! Enroll now or log in to track your progress or submit homework. ## Introduction to Information Theory

• Measuring Information: Bits
• Adding Up Bits
• Using Bits to Count and Label
• Physical Forms of Information
• Fundamental Formula of Information
• Computation and Logic: Information Processing
• Mutual Information
• Communication Capacity in a Noisy Channel
• Shannon's Coding Theorem
• Homework Solutions

#### 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.