Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

The notations follow those in Cover&Thomas, "Elements of Information Theory", 2ed.

I saw from a paper that the size of type class $T(P)$ can be expressed as $|T(P)|=2^{nH(P)-\frac{|\mathcal{X}|-1}{2}\log n+O(1)}$. I could not understand how this equation comes out. Could you please help me with it? Thanks a lot.

For those not familiar with information theory or method of types, the above equation can be formulated as:

Assume $(x_1,x_2,...,x_m)$ conforms to multinomial distribution. Conduct $n$ iid experiments, then $\sum\limits_{i=1}^mx_i=n$ and $P=\{\frac{x_1}{n},\frac{x_2}{n},...,\frac{x_m}{n}\}$ forms a pmf. Prove that the multinomial coefficient $\left(\begin{array}{c}n\\x_1,x_2,\ldots,x_m\end{array}\right)=2^{nH(P)-\frac{m-1}{2}\log n+O(1)}$ where $H(P)$ is the entropy of the pmf $P$. Thanks a lot!

share|cite|improve this question
It seems that we can use Stirling's approximation $n!\approx\sqrt{2\pi n}(n/e)^n$. But this is only an approximation and a big-O term $O(\ldots(n))$ or something is needed for the equation to hold exactly. I don't know what form of $O(\ldots(n))$ is. Any comment is welcome! ... I have to go to bed now:-( – Zhou Heng Mar 2 '13 at 16:11
up vote 0 down vote accepted

Plug the Stirling's approximation ( $n!=\sqrt{2\pi n}\left(\frac{n}{e}\right)^n\left(1+O\left(\frac{1}{n}\right)\right)$ into the expression of the multinomial coefficient.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.