Entropy, stirling's approximation

307 Views Asked by At

Given that the $\Omega$ is the total theoretical information encoded in a string of characrs let's say, we can express it in the bit-manner:

$$\Omega=2^G$$

Therefore $G=\log_2 \Omega$

We know that $$\Omega = \frac{T!}{n_1!n_2!...n_A!}$$

Where $T$ is the length of the string,for example, in which the message is encoded. And each $n_i$ is the number of repetitions of a single unique character.

We have that stirling's approximation is:

$$\log_2 n! \approx n\log_2 n - n$$

So applying this to $\log_2 \Omega$ I have:

$$-(n_1 \log_2 n_1 + n_2 \log_2 n_2 + ... + n_A\log_2n_A -n_1 -n_2 -... -n_A) -T\log_2 T + T$$

and so I have

$$-\sum_{i=1}^A n_i \log_2 \frac{n_i}{T^T} -\sum_{i=1}^A n_i +T$$

Whereas my notes quote the following result:

$$G = -\sum_{i=1}^A n_i \log_2 \frac{n_i}{T}$$

EDIT: Actually, even the result that I derived here is probably wrong because $n_1 \log_2 n_1 - T\log_2 T \neq \log_2 \frac{n_i}{T^T}$ but is rather: $\log_2 \frac{n_1^{n_1}}{T^T}$

1

There are 1 best solutions below

1
On BEST ANSWER

$T = n_1 + \ldots + n_A$, so $$\eqalign{-n_1 \log_2 n_1 &- \ldots - n_A \log_2 n_A + T \log_2 T = -n_1 (\log_2 n_1 - \log_2 T) - \ldots - n_A (\log_2 n_A - \log_2 T)\cr &= -n_1 \log_2(n_1/T) - \ldots - n_A \log_2(n_A/T)} $$ This, together with $-n_1 - \ldots - n_A + T = 0$, gives the notes' result.

Your answer would be $-n_1 \log_2 n_1 - \ldots - n_A \log_2 n_A + n_1 T \log_2 T + \ldots + n_A T \log_2 T$.