Complexity Explorer Santa Few Institute

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.