Shannon's entropy

From what we have just seen we can introduce a more general definition of entropy for a generic system that can be found in $\Omega$$\Omega$ different discrete states, each with probability $p_{i}$$p_{i}$ (and $i=1,\dots ,\Omega$$i=1,\dots ,\Omega$). This is known as Shannon's entropy, which is defined as:

$$S_{S}=-k_{S}\left\langle \ln p_{i}\right\rangle =-k_{S}\sum _{i=1}^{\Omega }p_{i}\ln p_{i}$$

$$S_{S}=-k_{S}\left\langle \ln p_{i}\right\rangle =-k_{S}\sum _{i=1}^{\Omega }p_{i}\ln p_{i}$$

the constant $k_{S}$$k_{S}$ is used instead of Boltzmann's constant because in general the connection to temperature can be irrelevant, and it is defined as $k_{S}=1/\ln 2$$k_{S}=1/\ln 2$ so that Shannon's entropy can be also rewritten as:

$$S_{S}=-\sum _{i=1}^{\Omega }p_{i}\log _{2}p_{i}$$

$$S_{S}=-\sum _{i=1}^{\Omega }p_{i}\log _{2}p_{i}$$

The unit of measure of this entropy is the bit. Shannon's entropy is particularly useful because it is the only one that satisfies three important properties, which we now show.

Theorem

Let $p_{1},\dots ,p_{\Omega }$$p_{1},\dots ,p_{\Omega }$ be a set of stochastic variables (they are probabilities, therefore such that $p_{i}\geq 0$$p_{i}\geq 0$ and $\sum _{i}p_{i}=1$$\sum _{i}p_{i}=1$). Then Shannon's entropy $S$$S$ (which is a function of this set of variables) as defined in satisfies the following properties:

• (Property zero) It is a continuous function

• (Property 1) $S(p_{1},\dots ,p_{\Omega })$$S(p_{1},\dots ,p_{\Omega })$ is maximized when all the $p_{i}$$p_{i}$-s are uniform:

$$S(p_{i},\dots ,p_{\Omega })<S\left({\frac {1}{\Omega }},\dots ,{\frac {1}{\Omega }}\right)$$

$$S(p_{i},\dots ,p_{\Omega })<S\left({\frac {1}{\Omega }},\dots ,{\frac {1}{\Omega }}\right)$$

• (Property 2) $S$$S$ is not affected by extra states of zero probability:

$$S(p_{1},\dots ,p_{\Omega },0)=S(p_{1},\dots ,p_{\Omega })$$

$$S(p_{1},\dots ,p_{\Omega },0)=S(p_{1},\dots ,p_{\Omega })$$

(where on the left side $S$$S$ has $\Omega +1$$\Omega +1$ arguments)

• (Property 3) $S$$S$ changes for conditional probabilities.

Let $A=\lbrace A_{i}\rbrace$$A=\lbrace A_{i}\rbrace$ and $B=\lbrace B_{k}\rbrace$$B=\lbrace B_{k}\rbrace$ be two sets of events (with $i=1,\dots ,\Omega$$i=1,\dots ,\Omega$ and $k=1,\dots ,M$$k=1,\dots ,M$), each with probability $p_{i}=p(A_{i})$$p_{i}=p(A_{i})$ and $q_{k}=p(B_{k})$$q_{k}=p(B_{k})$. If we define:

$$r_{ik}=p(A_{i}B_{k})\quad \qquad c_{ik}=p(A_{i}|B_{k})={\frac {p(A_{i}B_{k})}{p(B_{k})}}={\frac {r_{ik}}{q_{k}}}$$

$$r_{ik}=p(A_{i}B_{k})\quad \qquad c_{ik}=p(A_{i}|B_{k})={\frac {p(A_{i}B_{k})}{p(B_{k})}}={\frac {r_{ik}}{q_{k}}}$$

which, by definition, satisfy:

$$\sum _{i=1}^{\Omega }c_{ik}=1\quad \qquad \sum _{i=1}^{\Omega }\sum _{k=1}^{M}r_{ik}=1$$

$$\sum _{i=1}^{\Omega }c_{ik}=1\quad \qquad \sum _{i=1}^{\Omega }\sum _{k=1}^{M}r_{ik}=1$$

then we can introduce:

$$S(AB)=-k_{S}\sum _{i,k}r_{ik}\ln r_{ik}\quad \qquad S(B)=-k_{S}\sum _{k=1}^{M}q_{k}\ln q_{k}$$

$$S(AB)=-k_{S}\sum _{i,k}r_{ik}\ln r_{ik}\quad \qquad S(B)=-k_{S}\sum _{k=1}^{M}q_{k}\ln q_{k}$$

$$S(A|B_{\ell })=-k_{S}\sum _{i=1}^{\Omega }c_{i\ell }\ln c_{i\ell }$$

$$S(A|B_{\ell })=-k_{S}\sum _{i=1}^{\Omega }c_{i\ell }\ln c_{i\ell }$$

which are, respectively, the total entropy associated to the occurrence of events $A$$A$and$B$$B$, the entropy associated to the occurrence of events $B$$B$ and the entropy associated to the occurrence of events $A$$A$given$B_{\ell }$$B_{\ell }$. Therefore, defining:

$$\left\langle S(A|B_{\ell })\right\rangle =\sum _{\ell }q_{\ell }S(A|B_{\ell })=-k_{S}\sum _{i,\ell }q_{\ell }c_{i\ell }\ln c_{i\ell }$$

$$\left\langle S(A|B_{\ell })\right\rangle =\sum _{\ell }q_{\ell }S(A|B_{\ell })=-k_{S}\sum _{i,\ell }q_{\ell }c_{i\ell }\ln c_{i\ell }$$

we have that $S$$S$ satisfies:

$$\left\langle S(A|B_{\ell })\right\rangle =S(AB)-S(B)$$

$$\left\langle S(A|B_{\ell })\right\rangle =S(AB)-S(B)$$

 

Proof

• (Property zero) It is immediate from its definition.

• (Property 1) First of all, let us note that the function $f(x):=-x\ln x$$f(x):=-x\ln x$ is concave since $f''(x)=-1/x$$f''(x)=-1/x$ (and in our case $x\geq 0$$x\geq 0$ since it represents a probability).

In general, from the definition of concave function we have:

$$f(\lambda a+(1-\lambda )b)\geq \lambda f(a)+(1-\lambda )f(b)\qquad \qquad \lambda <1$$

$$f(\lambda a+(1-\lambda )b)\geq \lambda f(a)+(1-\lambda )f(b)\qquad \qquad \lambda <1$$

From this we can prove by induction that:

$$f\left({\frac {1}{\Omega }}\sum _{i=1}^{\Omega }p_{i}\right)\geq \sum _{i=1}^{\Omega }{\frac {1}{\Omega }}f(p_{i})$$

$$f\left({\frac {1}{\Omega }}\sum _{i=1}^{\Omega }p_{i}\right)\geq \sum _{i=1}^{\Omega }{\frac {1}{\Omega }}f(p_{i})$$

This is surely true for $\Omega =2$$\Omega =2$:

$$f\left({\frac {p_{1}+p_{2}}{2}}\right)\geq {\frac {1}{2}}\left(f(p_{1})+f(p_{2})\right)$$

$$f\left({\frac {p_{1}+p_{2}}{2}}\right)\geq {\frac {1}{2}}\left(f(p_{1})+f(p_{2})\right)$$

since it follows directly from with $p_{1}=a$$p_{1}=a$, $p_{2}=b$$p_{2}=b$ and $\lambda =1/2$$\lambda =1/2$. If we now suppose that the inequality holds for $\Omega -1$$\Omega -1$ probabilities:

$$f\left({\frac {1}{\Omega -1}}\sum _{i=1}^{\Omega -1}p_{i}\right)\geq {\frac {1}{\Omega -1}}\sum _{i=1}^{\Omega -1}f(p_{i})$$

$$f\left({\frac {1}{\Omega -1}}\sum _{i=1}^{\Omega -1}p_{i}\right)\geq {\frac {1}{\Omega -1}}\sum _{i=1}^{\Omega -1}f(p_{i})$$

it follows that it holds also for $\Omega$$\Omega$. In fact:

$$f\left({\frac {1}{\Omega }}\sum _{i=1}^{\Omega }p_{i}\right)=f\left({\frac {\Omega -1}{\Omega }}{\frac {1}{\Omega -1}}\sum _{i=1}^{\Omega -1}p_{i}+{\frac {p_{\Omega }}{\Omega }}\right)$$

$$f\left({\frac {1}{\Omega }}\sum _{i=1}^{\Omega }p_{i}\right)=f\left({\frac {\Omega -1}{\Omega }}{\frac {1}{\Omega -1}}\sum _{i=1}^{\Omega -1}p_{i}+{\frac {p_{\Omega }}{\Omega }}\right)$$

and choosing $(\Omega -1)/\Omega =\lambda$$(\Omega -1)/\Omega =\lambda$:

$${\begin{aligned}f\left({\frac {1}{\Omega }}\sum _{i=1}^{\Omega }p_{i}\right)\geq {\frac {\Omega -1}{\Omega }}f\left({\frac {1}{\Omega -1}}\sum _{i=1}^{\Omega -1}p_{i}\right)+{\frac {1}{\Omega }}f(p_{\Omega })\geq \\\geq {\frac {\Omega -1}{\Omega }}{\frac {1}{\Omega -1}}\sum _{i=1}^{\Omega -1}f(p_{i})+{\frac {1}{\Omega }}f(p_{\Omega })\end{aligned}}$$

$${\begin{aligned}f\left({\frac {1}{\Omega }}\sum _{i=1}^{\Omega }p_{i}\right)\geq {\frac {\Omega -1}{\Omega }}f\left({\frac {1}{\Omega -1}}\sum _{i=1}^{\Omega -1}p_{i}\right)+{\frac {1}{\Omega }}f(p_{\Omega })\geq \\\geq {\frac {\Omega -1}{\Omega }}{\frac {1}{\Omega -1}}\sum _{i=1}^{\Omega -1}f(p_{i})+{\frac {1}{\Omega }}f(p_{\Omega })\end{aligned}}$$

Therefore:

$$f\left({\frac {1}{\Omega }}\sum _{i=1}^{\Omega }p_{i}\right)\geq {\frac {1}{\Omega }}\sum _{i=1}^{\Omega }f(p_{i})$$

$$f\left({\frac {1}{\Omega }}\sum _{i=1}^{\Omega }p_{i}\right)\geq {\frac {1}{\Omega }}\sum _{i=1}^{\Omega }f(p_{i})$$

Now, considering the case $f(x)=-x\ln x$$f(x)=-x\ln x$ we will have that:

$${\begin{aligned}S(p_{1},\dots ,p_{\Omega })=k_{S}\sum _{i=1}^{\Omega }f(p_{i})=k_{S}\Omega {\frac {1}{\Omega }}\sum _{i=1}^{\Omega }f(p_{i})<k_{S}\Omega f\left({\frac {1}{\Omega }}\sum _{i=1}^{\Omega }p_{i}\right)=\\=k_{S}\Omega f\left({\frac {1}{\Omega }}\right)=-k_{S}\sum _{i=1}^{\Omega }{\frac {1}{\Omega }}\ln {\frac {1}{\Omega }}=S\left({\frac {1}{\Omega }},\dots ,{\frac {1}{\Omega }}\right)\end{aligned}}$$

$${\begin{aligned}S(p_{1},\dots ,p_{\Omega })=k_{S}\sum _{i=1}^{\Omega }f(p_{i})=k_{S}\Omega {\frac {1}{\Omega }}\sum _{i=1}^{\Omega }f(p_{i})<k_{S}\Omega f\left({\frac {1}{\Omega }}\sum _{i=1}^{\Omega }p_{i}\right)=\\=k_{S}\Omega f\left({\frac {1}{\Omega }}\right)=-k_{S}\sum _{i=1}^{\Omega }{\frac {1}{\Omega }}\ln {\frac {1}{\Omega }}=S\left({\frac {1}{\Omega }},\dots ,{\frac {1}{\Omega }}\right)\end{aligned}}$$

where the inequality is strict because in this case $f''(x)<0$$f''(x)<0$ .

• (Property 2) This follows immediately from the fact that $f(x)$$f(x)$ can be continuously extended in $x=0$$x=0$, so that $f(0)=0$$f(0)=0$ (as we have previously stated). Therefore if we add $p_{\Omega +1}=0$$p_{\Omega +1}=0$ to $S$$S$, it will not contribute to $S$$S$ since by definition $p_{\Omega +1}\ln p_{\Omega +1}=0$$p_{\Omega +1}\ln p_{\Omega +1}=0$.

• (Property 3) Since $r_{ik}=q_{k}c_{ik}$$r_{ik}=q_{k}c_{ik}$, we have:

$${\begin{aligned}S(AB)=-k_{S}\sum _{i,k}q_{k}c_{ik}\ln(q_{k}c_{ik})=-k_{S}\sum _{i,k}q_{k}c_{ik}(\ln q_{k}+\ln c_{ik})=\\=-k_{S}\left(\sum _{i,k}q_{k}c_{ik}\ln q_{k}+\sum _{i,k}q_{k}c_{ik}\ln c_{ik}\right)\end{aligned}}$$

$${\begin{aligned}S(AB)=-k_{S}\sum _{i,k}q_{k}c_{ik}\ln(q_{k}c_{ik})=-k_{S}\sum _{i,k}q_{k}c_{ik}(\ln q_{k}+\ln c_{ik})=\\=-k_{S}\left(\sum _{i,k}q_{k}c_{ik}\ln q_{k}+\sum _{i,k}q_{k}c_{ik}\ln c_{ik}\right)\end{aligned}}$$

However:

$$\sum _{i,k}q_{k}c_{ik}\ln q_{k}=\sum _{k}q_{k}\ln q_{k}\sum _{i}c_{ik}=\sum _{k}q_{k}\ln q_{k}$$

$$\sum _{i,k}q_{k}c_{ik}\ln q_{k}=\sum _{k}q_{k}\ln q_{k}\sum _{i}c_{ik}=\sum _{k}q_{k}\ln q_{k}$$

and therefore:

$$S(AB)=-k_{S}\sum _{k}q_{k}\ln q_{k}-k_{S}\sum _{i,k}q_{k}c_{ik}\ln c_{ik}=S(B)+\left\langle S(A|B_{\ell })\right\rangle$$

$$S(AB)=-k_{S}\sum _{k}q_{k}\ln q_{k}-k_{S}\sum _{i,k}q_{k}c_{ik}\ln c_{ik}=S(B)+\left\langle S(A|B_{\ell })\right\rangle$$

from which we have immediately:

$$\left\langle S(A|B_{\ell })\right\rangle =S(AB)-S(B)$$

$$\left\langle S(A|B_{\ell })\right\rangle =S(AB)-S(B)$$

 

Let us note an interesting consequence of the last property of the entropy: if we suppose $A_{i}$$A_{i}$ and $B_{k}$$B_{k}$ to be independent then $S(A|B_{\ell })=S(A)$$S(A|B_{\ell })=S(A)$ and we get $S(AB)=S(A)+S(B)$$S(AB)=S(A)+S(B)$: we have thus found that entropy is extensive! Therefore, the last property of $S$$S$ is a generalization of the extensivity of the entropy for correlated events.

Now, since these properties are a little bit obscure as we have stated them, let us make a simple example to illustrate their meaning. To make things more comprehensible, we use the same notation of the proof. Suppose you have lost your house keys, and want to find them; you can measure your progress in finding them by measuring your ignorance with some function$S$$S$. Suppose there are $\Omega$$\Omega$ possible places $A_{i}$$A_{i}$ where you have might left the keys, each one with an estimated probability $p_{i}$$p_{i}$; the three properties of the entropy $S$$S$ can thus be interpreted as follows:

• without further information, your ignorance is maximal and the keys could be in any of the possible places, each with the same probability
• if there is no possibility that the keys might be in a particular place $A_{\Omega }$$A_{\Omega }$ (your shoe, for example), then your ignorance is no larger than what it would have been if you had not included that place in the list of possible sites
• to improve the research, you are likely to look where you have last seen the keys; let us call these $M$$M$ places $B_{k}$$B_{k}$, each with probability $q_{k}$$q_{k}$ that the keys are indeed there.

Before thinking where you have last seen the keys, your ignorance about their location is $S(A)=S(p_{1},\dots ,p_{\Omega })$$S(A)=S(p_{1},\dots ,p_{\Omega })$ and the one about where you have last seen them is $S(B)=S(q_{i},\dots ,q_{M})$$S(B)=S(q_{i},\dots ,q_{M})$; therefore you also have the joint ignorance $S(AB)$$S(AB)$. If the location where you last seen them is $B_{\ell }$$B_{\ell }$ then your ignorance about the location of the keys is $S(A|B_{\ell })$$S(A|B_{\ell })$, and so your combined ignorance has reduced from $S(AB)$$S(AB)$ to $S(A|B_{\ell })$$S(A|B_{\ell })$. You can now measure the usefulness of your guess by determining how much it will reduce your ignorance about where the keys are: the expected ignorance after you have guessed where the keys might have been is given by weighting the ignorance after each guess $B_{\ell }$$B_{\ell }$ by the probability of that guess, namely it is $\left\langle S(A|B_{\ell })\right\rangle$$\left\langle S(A|B_{\ell })\right\rangle$. The last property of the entropy thus states that after a guess your expected ignorance decreases exactly by the amount $S(B)$$S(B)$.

Now, what makes Shannon's entropy as defined in Entropy as ignorance: information entropy so special is the fact that it is unique (of course up to a proportionality constant) and this follows only by the properties that we have just shown it satisfies.

Theorem

Shannon's entropy, defined as:

$$S_{S}=-k_{S}\sum _{i}p_{i}\ln p_{i}$$

$$S_{S}=-k_{S}\sum _{i}p_{i}\ln p_{i}$$

and satisfying the properties shown in theorem , is unique up to a normalization constant. In other words, the properties shown in theorem uniquely identify Shannon's entropy.

 

The idea of the proof is the following: we prove that from those properties we have that $S_{S}=S({\vec {p}})$$S_{S}=S({\vec {p}})$ has indeed the expression of Shannon's entropy when$p_{i}\in \mathbb {Q} ^{+}$$p_{i}\in \mathbb {Q} ^{+}$. Then, since $S$$S$ is a continuous function (property 0 of theorem ) we have that $S({\vec {p}})$$S({\vec {p}})$ has the same expression also for $p_{i}\in \mathbb {R} ^{+}$$p_{i}\in \mathbb {R} ^{+}$.

Proof

Let us take ${\vec {q}}\in \mathbb {Q} ^{\Omega }$${\vec {q}}\in \mathbb {Q} ^{\Omega }$, and we write its components as $q_{\ell }=g_{\ell }/g$$q_{\ell }=g_{\ell }/g$ with $g,g_{\ell }\in \mathbb {N}$$g,g_{\ell }\in \mathbb {N}$ (and $g$$g$ the least common multiple of the $g_{\ell }$$g_{\ell }$-s). We suppose $r_{k\ell }=1/g$$r_{k\ell }=1/g$, so that $c_{k\ell }=r_{k\ell }/q_{\ell }=1/g_{\ell }$$c_{k\ell }=r_{k\ell }/q_{\ell }=1/g_{\ell }$ (and $k=1,\dots ,g_{\ell }$$k=1,\dots ,g_{\ell }$). Defining $L(g)=S_{S}(1/g,\dots ,1/g)$$L(g)=S_{S}(1/g,\dots ,1/g)$, we have:

$$S_{S}(AB)=S_{S}(r_{11},r_{12},\dots ,r_{\Omega M})=L(g)$$

$$S_{S}(AB)=S_{S}(r_{11},r_{12},\dots ,r_{\Omega M})=L(g)$$

$$S_{S}(A|B)=\sum _{\ell =1}^{M}q_{\ell }S_{S}(c_{1\ell },\dots ,c_{\Omega \ell })=\sum _{\ell }q_{\ell }L(g_{\ell })$$

$$S_{S}(A|B)=\sum _{\ell =1}^{M}q_{\ell }S_{S}(c_{1\ell },\dots ,c_{\Omega \ell })=\sum _{\ell }q_{\ell }L(g_{\ell })$$

From the third property of $S_{S}$$S_{S}$ we have:

$${\begin{aligned}S_{S}(AB)=S_{S}(A|B)+S_{S}(B)\quad \Rightarrow \quad L(g)=\sum _{\ell }q_{\ell }L(g_{\ell })+S_{S}(q_{1},\dots ,q_{M})\quad \Rightarrow \\\Rightarrow \quad S_{S}(q_{1},\dots ,q_{M})=L(g)-\sum _{\ell }q_{\ell }L(g_{\ell })\end{aligned}}$$

$${\begin{aligned}S_{S}(AB)=S_{S}(A|B)+S_{S}(B)\quad \Rightarrow \quad L(g)=\sum _{\ell }q_{\ell }L(g_{\ell })+S_{S}(q_{1},\dots ,q_{M})\quad \Rightarrow \\\Rightarrow \quad S_{S}(q_{1},\dots ,q_{M})=L(g)-\sum _{\ell }q_{\ell }L(g_{\ell })\end{aligned}}$$

Therefore, if we know $L(g)$$L(g)$ we can express $S_{S}$$S_{S}$ (when its arguments are rational, for now). Let us see that from we get the expression of Shannon's entropy if $L(g)=k\ln g$$L(g)=k\ln g$, with $k$$k$ a generic constant:

$${\begin{aligned}S_{S}(q_{1},\dots ,q_{M})=L(g)-\sum _{\ell }q_{\ell }L(g_{\ell })=k\ln g-k\sum _{\ell }q_{\ell }\ln g_{\ell }=\\=k\sum _{\ell }q_{\ell }(\ln g-\ln g_{\ell })=-k\sum _{\ell }q_{\ell }\ln {\frac {g_{\ell }}{g}}=-k\sum _{\ell }q_{\ell }\ln q_{\ell }\end{aligned}}$$

$${\begin{aligned}S_{S}(q_{1},\dots ,q_{M})=L(g)-\sum _{\ell }q_{\ell }L(g_{\ell })=k\ln g-k\sum _{\ell }q_{\ell }\ln g_{\ell }=\\=k\sum _{\ell }q_{\ell }(\ln g-\ln g_{\ell })=-k\sum _{\ell }q_{\ell }\ln {\frac {g_{\ell }}{g}}=-k\sum _{\ell }q_{\ell }\ln q_{\ell }\end{aligned}}$$

which is exactly Shannon's entropy. We therefore must prove that $L(g)=k\ln g$$L(g)=k\ln g$, and in order to do that we will use the first and second properties of $S_{S}$$S_{S}$. Let us call $a$$a$ and $b$$b$ two integers such that $a<b$$a<b$; then from the second property we have:

$$S_{S}\left(\underbrace {{\frac {1}{a}},\dots ,{\frac {1}{a}}} _{a{\text{ arg.}}}\right)=S_{S}\left(\underbrace {{\frac {1}{a}},\dots ,{\frac {1}{a}}} _{a{\text{ arg.}}},\underbrace {0,\dots ,0} _{b-a{\text{ arg.}}}\right)$$

$$S_{S}\left(\underbrace {{\frac {1}{a}},\dots ,{\frac {1}{a}}} _{a{\text{ arg.}}}\right)=S_{S}\left(\underbrace {{\frac {1}{a}},\dots ,{\frac {1}{a}}} _{a{\text{ arg.}}},\underbrace {0,\dots ,0} _{b-a{\text{ arg.}}}\right)$$

and from the first:

$${\begin{aligned}S_{S}\left(\underbrace {{\frac {1}{a}},\dots ,{\frac {1}{a}}} _{a{\text{ arg.}}},\underbrace {0,\dots ,0} _{b-a{\text{ arg.}}}\right)<S_{S}\left(\underbrace {{\frac {1}{b}},\dots ,{\frac {1}{b}}} _{b{\text{ arg.}}}\right)\quad \Rightarrow \\\Rightarrow \quad S_{S}(1/a,\dots ,1/a)<S_{S}(1/b,\dots ,1/b)\end{aligned}}$$

$${\begin{aligned}S_{S}\left(\underbrace {{\frac {1}{a}},\dots ,{\frac {1}{a}}} _{a{\text{ arg.}}},\underbrace {0,\dots ,0} _{b-a{\text{ arg.}}}\right)<S_{S}\left(\underbrace {{\frac {1}{b}},\dots ,{\frac {1}{b}}} _{b{\text{ arg.}}}\right)\quad \Rightarrow \\\Rightarrow \quad S_{S}(1/a,\dots ,1/a)<S_{S}(1/b,\dots ,1/b)\end{aligned}}$$

so if $a<b$$a<b$ then $L(a)<L(b)$$L(a)<L(b)$. Let now $C^{(1)},C^{(2)},\dots ,C^{(n)}$$C^{(1)},C^{(2)},\dots ,C^{(n)}$ be $n$$n$ classes containing each $g$$g$ independent events with uniform probability; if we call $A$$A$ the set of $g$$g$ events in $C^{(1)}$$C^{(1)}$ and $B$$B$ all the $g^{n-1}$$g^{n-1}$ remaining ones, from the third property of $S_{S}$$S_{S}$ we have:

$$S_{S}(AB)=S_{S}(A)+S_{S}(B)\quad \Rightarrow \quad L(g^{n})=L(g)+L(g^{n-1})$$

$$S_{S}(AB)=S_{S}(A)+S_{S}(B)\quad \Rightarrow \quad L(g^{n})=L(g)+L(g^{n-1})$$

we thus have found a recursive formula for $L(g^{n})$$L(g^{n})$; applying it $n$$n$ times we get:

$$L(g^{n})=\underbrace {L(g)+L(g)+\cdots +L(g)} _{n{\text{ times}}}+L(1)=nL(g)+L(1)$$

$$L(g^{n})=\underbrace {L(g)+L(g)+\cdots +L(g)} _{n{\text{ times}}}+L(1)=nL(g)+L(1)$$

and we set$L(1)=0$$L(1)=0$. Therefore, $L(g^{n})=nL(g)$$L(g^{n})=nL(g)$. Let us now take $s\in \mathbb {N}$$s\in \mathbb {N}$; there will surely be an $m\in \mathbb {N}$$m\in \mathbb {N}$ for which:

$$2^{m}\leq s^{n}<2^{m+1}$$

$$2^{m}\leq s^{n}<2^{m+1}$$

so (this can be done because $L(a)<L(b)$$L(a)<L(b)$ if $a<b$$a<b$):

$${\begin{aligned}L(2^{m})\leq L(s^{n})<L(2^{m+1})\quad \Rightarrow \quad mL(2)\leq nL(s)<(m+1)L(2)\quad \Rightarrow \\\Rightarrow \quad {\frac {m}{n}}\leq {\frac {L(s)}{L(2)}}<{\frac {m+1}{n}}\end{aligned}}$$

$${\begin{aligned}L(2^{m})\leq L(s^{n})<L(2^{m+1})\quad \Rightarrow \quad mL(2)\leq nL(s)<(m+1)L(2)\quad \Rightarrow \\\Rightarrow \quad {\frac {m}{n}}\leq {\frac {L(s)}{L(2)}}<{\frac {m+1}{n}}\end{aligned}}$$

Now, the logarithm $\ln$$\ln$ is a monotonically increasing function so if $a<b$$a<b$ then $\ln a<\ln b$$\ln a<\ln b$; therefore we find that a similar inequality holds also for the logarithm:

$${\frac {m}{n}}\leq {\frac {\ln s}{\ln 2}}<{\frac {m+1}{n}}$$

$${\frac {m}{n}}\leq {\frac {\ln s}{\ln 2}}<{\frac {m+1}{n}}$$

This means that $L(s)/L(2)$$L(s)/L(2)$ and $\ln s/\ln 2$$\ln s/\ln 2$ both belong to the interval $[m/n,(m+1)/n]$$[m/n,(m+1)/n]$, whose width is $1/n$$1/n$. Thus:

$$\left|{\frac {\ln s}{\ln 2}}-{\frac {L(s)}{L(2)}}\right|<{\frac {1}{n}}$$

$$\left|{\frac {\ln s}{\ln 2}}-{\frac {L(s)}{L(2)}}\right|<{\frac {1}{n}}$$

and taking the limit $n\to \infty$$n\to \infty$ (in fact $n$$n$ is arbitrary, so the inequality must hold for all $n$$n$s) we obtain:

$$L(s)={\frac {L(2)}{\ln 2}}\ln s$$

$$L(s)={\frac {L(2)}{\ln 2}}\ln s$$

and renaming $L(2)/\ln 2$$L(2)/\ln 2$ as $k$$k$, we get:

$$L(g)=k\ln g$$

$$L(g)=k\ln g$$

which is exactly what we wanted to prove.

Therefore, we see that the Shannon's entropy is uniquely determined by the properties shown in theorem .