Shannon’s entropy

Definition (Discrete)

Let $X$ be a discrete random variable on a finite set$𝒳=\{x_1,\mathrm{\dots },x_n\}$, with probability distributionfunction $p(x)=\mathrm{Pr}(X=x)$. The entropy $H(X)$ of $X$ isdefined as

$$H(X)=-\sum _{x\in 𝒳}p(x){\log }_{b}p(x).$$(1)

The convention $0\log 0=0$ is adopted in the definition. Thelogarithm is usually taken to the base 2, in which case theentropy is measured in “bits,” or to the base e, in which case$H(X)$ is measured in “nats.”

If $X$ and $Y$ are random variables on $𝒳$ and$𝒴$ respectively, the joint entropy of $X$ and $Y$is

$$H(X,Y)=-\sum _{(x,y)\in 𝒳\times 𝒴}p(x,y){\log }_{b}p(x,y),$$

where $p(x,y)$ denote the joint distribution of $X$ and $Y$.

Discussion

The Shannon entropy was first introduced by Shannon in 1948 in hislandmark paper “A Mathematical Theory of Communication.” Theentropy is a functional of the probability distribution function$p(x)$, and is sometime written as

$$H(p(x_1),p(x_2),\mathrm{\dots },p(x_n)).$$

It is noted that the entropy of $X$ does not depend on the actualvalues of $X$, it only depends on $p(x)$. The definition ofShannon’s entropy can be written as an expectation

$$H(X)=-E[{\log }_{b}p(X)].$$

The quantity $-{\log }_{b}p(x)$ is interpreted as the informationcontent of the outcome $x\in 𝒳$, and is also called the Hartleyinformation of $x$. Hence the Shannon’s entropy is the averageamount of information contained in random variable $X$, it is alsothe uncertainty removed after the actual outcome of $X$ isrevealed.

Characterization

We write $H(X)$ as $H_n(p_1,\mathrm{\dots },p_n)$. The Shannon entropysatisfies the following properties.

1. For any $n$, $H_n(p_1,\mathrm{\dots },p_n)$ is a continuous andsymmetric function on variables $p_1$, $p_2,\mathrm{\dots },p_n$.

2. Event of probability zero does not contribute to the entropy, i.e. for any $n$,

   $$H_{n+1}(p_1,\mathrm{\dots },p_n,0)=H_n(p_1,\mathrm{\dots },p_n).$$

3. Entropy is maximized when the probability distribution isuniform. For all $n$,

   $$H_n(p_1,\mathrm{\dots },p_n)\le H_n(\frac{1}{n},\mathrm{\dots },\frac{1}{n}).$$

   This follows from Jensen inequality,

   $$H(X)=E\left[{\log }_b\left(\frac{1}{p(X)}\right)\right]\le {\log }_b\left(E\left[\frac{1}{p(X)}\right]\right)={\log }_b(n).$$

4. If $p_{ij}$, $1\le i\le m$, $1\le j\le n$ arenon-negative real numbers summing up to one, and $q_i={\sum }_{j=1}^n{p}_{ij}$, then

   $$H_{mn}(p_{11},\mathrm{\dots },p_{mn})=H_m(q_1,\mathrm{\dots },q_m)+\sum _{i=1}^m{q}_i{H}_n(\frac{p_{i1}}{q_i},\mathrm{\dots },\frac{p_{in}}{q_i}).$$

   If we partition the $mn$ outcomes of the random experiment into$m$ groups, each group contains $n$ elements, we can do theexperiment in two steps: first determine the group to which theactual outcome belongs to, and second find the outcome in thisgroup. The probability that you will observe group $i$ is $q_i$.The conditional probability distribution function given group $i$is $(p_{i1}/q_i,\mathrm{\dots },p_{in}/q_i)$. The entropy

   $$H_n(\frac{p_{i1}}{q_i},\mathrm{\dots },\frac{p_{in}}{q_i})$$

   is the entropy of the probability distribution conditioned ongroup $i$. Property 4 says that the total information is the sumof the information you gain in the first step, $H_m(q_1,\mathrm{\dots },q_m)$, and a weighted sum of the entropies conditioned on eachgroup.

Khinchin in 1957 showed that the only function satisfying theabove assumptions is of the form:

$$H_n(p_1,\mathrm{\dots },p_n)=-k\sum _{i=1}^n{p}_i\log p_i$$

where $k$ is a positive constant, essentially a choice of unit ofmeasure.

Definition (Continuous)

Entropy in the continuous case is called differential entropy (http://planetmath.org/DifferentialEntropy).

Discussion—Continuous Entropy

Despite its seductively analogous form, continuous entropy cannot be obtained as a limiting case of discrete entropy.

We wish to obtain a generally finite measure as the “bin size” goes to zero. In the discrete case, the bin size is the (implicit) width of each of the $n$ (finite or infinite) bins/buckets/states whose probabilities are the $p_n$. As we generalize to the continuous domain, we must make this width explicit.

To do this, start with a continuous function $f$ discretized as shown in the figure:

Figure 1: Discretizing the function $f$ into bins of width $\mathrm{\Delta }$

As the figure indicates, by the mean-value theorem there exists a value $x_i$ in each bin such that

$$f(x_i)\mathrm{\Delta }={\int }_{i\mathrm{\Delta }}^{(i+1)\mathrm{\Delta }}f(x)𝑑x$$(2)

and thus the integral of the function $f$ can be approximated (in the Riemannian sense) by

$${\int }_{-\mathrm{\infty }}^{\mathrm{\infty }}f(x)𝑑x=\underset{\mathrm{\Delta }\to 0}{lim}\sum _{i=-\mathrm{\infty }}^{\mathrm{\infty }}f(x_i)\mathrm{\Delta }$$(3)

where this limit and “bin size goes to zero” are equivalent.

We will denote

$$H^{\mathrm{\Delta }}:=-\sum _{i=-\mathrm{\infty }}^{\mathrm{\infty }}\mathrm{\Delta }f(x_i)\log \mathrm{\Delta }f(x_i)$$(4)

and expanding the $\log$ we have

$H^{\mathrm{\Delta }}$$=-{\displaystyle \sum _{i=-\mathrm{\infty }}^{\mathrm{\infty }}}\mathrm{\Delta }f(x_i)\log \mathrm{\Delta }f(x_i)$(5)

$=-{\displaystyle \sum _{i=-\mathrm{\infty }}^{\mathrm{\infty }}}\mathrm{\Delta }f(x_i)\log f(x_i)-{\displaystyle \sum _{i=-\mathrm{\infty }}^{\mathrm{\infty }}}f(x_i)\mathrm{\Delta }\log \mathrm{\Delta }.$(6)

As $\mathrm{\Delta }\to 0$, we have

${\displaystyle \sum _{i=-\mathrm{\infty }}^{\mathrm{\infty }}}f(x_i)\mathrm{\Delta }$$\to {\displaystyle \int f(x)𝑑x}=1\mathit{\hspace{1em}\hspace{1em}}\text{and}$(7)

${\displaystyle \sum _{i=-\mathrm{\infty }}^{\mathrm{\infty }}}\mathrm{\Delta }f(x_i)\log f(x_i)$$\to {\displaystyle \int f(x)\log f(x)𝑑x}$(8)

This leads us to our definition of the differential entropy (continuous entropy):

$$h[f]=\underset{\mathrm{\Delta }\to 0}{lim}\left[H^{\mathrm{\Delta }}+\log \mathrm{\Delta }\right]=-{\int }_{-\mathrm{\infty }}^{\mathrm{\infty }}f(x)\log f(x)𝑑x.$$(9)