# Derivation of information entropy using Stirling's approximation

I'm currently studying the textbook Pattern Recognition and Machine Learning (Bishop, 2006) and am studying the information entropy in chapter 1.

In the book, the author derives the definition of information entropy for discrete random variable cases by giving the analogy of "considering a set of $$N$$ objects that are to be divided amongst a set of bins, such that there are $$n_i$$ objects in the $$i$$th bin.

The total number of ways to allocate the $$N$$ objects is:

$$W = \frac{N!}{\prod_i n_i !}$$

and the entropy is based on the logarithm of this scaled by a constant:

$$H = \frac{1}{N} \ln (W)$$

The author then uses Stirling's approximation to make a derivation, but I'm getting stuck midway from how the author derived the final result. Here's my derivation:

\begin{align} H & = \frac{1}{N} \ln (W) \\ & = \frac{1}{N} \ln \left( \frac{N!}{\prod_i n_i !}\right) \\ & = \frac{1}{N} \left( \ln(N!) - \ln \left( \prod_i n_i! \right) \right) \\ & = \frac{1}{N} \left( \ln(N!) - \sum_i \ln (n_i!) \right) \\ & = \frac{1}{N} \left( (N \ln(N) - N) - \left( \sum_i (n_i \ln (n_i) - n_i )\right) \right) \\ & = \left( \ln(N) - 1 \right) - \frac{1}{N} \left( \sum_i n_i\ln(n_i) - \sum_in_i \right) \\ & = (\ln(N) - 1) -\frac{1}{N} \sum_i n_i \ln(n_i) + 1 \\ & = \ln(N) - \frac{1}{N} \sum_i n_i \ln(n_i) \end{align}

The author's final result states that:

\begin{align} H & = -\lim_{N \rightarrow \infty} \sum_i \left( \frac{n_i}{N} \right) \ln \left( \frac{n_i}{N} \right) \\ & = -\sum_i p_i \ln(p_i) \end{align}

I'm a bit confused as to how the author jumped from the derivation to suddenly using a limit, and also how using the limit on those values gives the values of $$p_i$$. My initial thought was that $$p_i = \frac{n_i}{N}$$ and so I'm not sure what purpose the limit serves here.

Would anybody be kind enough to give me some tips or pointers as to how this result was derived? Thanks in advance.

For figuring out why two (given) things are equal it's often useful to burn the candle at both ends. Start at the line that seems "jumped" to and work backwards to fill in the gap:

$$\sum_i \frac{n_i}{N}\ln\frac{n_i}{N} = \frac{1}{N}\sum_i n_i \big[\ln n_i - \ln N\big]=\cdots$$

Can you take it from here? (Note ($$\sum n_i = N$$.)

As for why the author is taking the limit, that's probably a matter of explaining how the notion of entropy is being generalized from set partitions to discrete random variables. In simple situations, a discrete random variable can be described as a finite set of outcomes and a bunch of "events" which are sets of outcomes (so, a set partition), and the probability of the events are $$n/N$$ (where $$n$$ is the number of outcomes in the event and $$N$$ is the total number of outcomes). Situations aren't always that simple, and probabilities don't have to be rational numbers, and this taking the limit business is the path to generalizing the notion of entropy to arbitrary discrete random variables.

• Yes, thanks for the tip! And also thanks for explaining the "limit business," I've seen it quite frequently but could never understand the intuition behind why it was used.
– Sean
Nov 24, 2019 at 3:01
• It does seem like it would have been a bit more straightforward had the author scaled with $-\frac{1}{N}$ rather than $\frac{1}{N}$.
– Sean
Nov 24, 2019 at 3:07

Derivation of 1.97 in Pattern recognition and machine learning (PRML) by Christopher M. Bishop:

$$W=\frac{N!}{\prod{}N_{i}!}$$

$$H = \frac{1}{N}lnW = \frac{1}{N}lnN!-\frac{1}{N}\sum lnN_{i}!$$

Stirling's approximation = $$lnN! = NlnN-N$$

Using Stirling's approximation we attain:

$$H = \frac{1}{N}(NlnN -N)-\frac{1}{N}\sum (N_{i}lnN_{i}-N_{i})$$

$$= \frac{1}{N}(NlnN -N)-\frac{1}{N}\sum N_{i}lnN_{i} + \frac{1}{N}\sum N_{i}$$

Using the fact that the $$\sum N_{i}=N$$ (The sum of all items in each bin must be equal to the total number of items)

$$= \frac{1}{N}(NlnN -N)-\frac{1}{N}\sum N_{i}lnN_{i} + \frac{1}{N}N$$

$$= \frac{1}{N}(NlnN -N)-\frac{1}{N}\sum N_{i}lnN_{i} + 1$$

$$= \frac{1}{N}NlnN -\frac{1}{N}N-\frac{1}{N}\sum N_{i}lnN_{i} + 1$$

$$= \frac{1}{N}NlnN -1-\frac{1}{N}\sum N_{i}lnN_{i} + 1$$

$$= \frac{1}{N}NlnN -\frac{1}{N}\sum N_{i}lnN_{i}$$

Now using the fact that $$p_{i}= \frac{N_{i}}{N}$$ (the probability of being in bin $$N_{i}$$) and therefore $$N_{i}=p_{i}N$$

$$= \frac{1}{N}NlnN -\frac{1}{N}\sum p_{i}Nlnp_{i}N$$

Using log properties of multiplication we can rewrite as

$$= \frac{1}{N}NlnN -(\frac{1}{N}\sum p_{i}NlnN +\frac{1}{N}\sum p_{i}Nlnp_{i})$$

$$NlnN$$ is a constant wrt. summation over $$i$$

$$= \frac{1}{N}NlnN -(\frac{1}{N}NlnN\sum p_{i} +\frac{1}{N}\sum p_{i}Nlnp_{i})$$

$$\sum p_{i} = 1$$ so

$$= \frac{1}{N}NlnN -\frac{1}{N}NlnN -\frac{1}{N}\sum p_{i}Nlnp_{i}$$

$$= -\frac{1}{N}\sum p_{i}Nlnp_{i}$$

$$= -\frac{1}{N}N\sum p_{i}lnp_{i}$$

$$= -\sum p_{i}lnp_{i}$$