Shannon Entropy

Entropy is a concept in Thermodynamics (see Thermodynamic Entropy ), Statistical Mechanics and Information Theory . The concepts of information and entropy have deep links with one another, although it took many years for the development of the theories of Statistical Mechanics and Information Theory to make this apparent. This article is about '''information entropy''', the information-theoretic formulation of Entropy . Information entropy is occasionally called '''Shannon's entropy''' in honor of Claude E. Shannon .

INTRODUCTION

The concept of entropy in Information Theory describes with how much Randomness (or, alternatively, 'uncertainty') there is in a signal or random event. An alternative way to look at this is to talk about how much information is carried by the signal.

For example, consider some paper " A Mathematical Theory of Communication ".

Shannon offers a definition of entropy which satisfies the assumptions that:

The measure should be proportional (continuous) - i.e. changing the value of one of the probabilities by a very small amount should only change the entropy by a small amount.

If all the outcomes (letters in the example above) are equally likely then increasing the number of letters should always increase the entropy.

We should be able to make the choice (in our example of a letter) in two steps, in which case the entropy of the final result should be a weighted sum of the entropies of the two steps.

(Note: Shannon/Weaver make reference to Tolman ( 1938 ) who in turn credits Pauli ( 1933 ) with the definition of entropy that is used by Shannon. Elsewhere in statistical mechanics, the literature includes references to Von Neumann as having derived the same form of entropy in 1927 , so it was that von Neumann favoured the use of the existing term 'entropy'. )

FORMAL DEFINITIONS

Claude E. Shannon defines entropy in terms of a discrete random event ''x'', with possible states (or outcomes) 1..''n'' as:

:

H(x)=\sum_{i=1}^np(i)\log_2 \left(rac{1}{p(i)}
ight)=-\sum_{i=1}^np(i)\log_2 p(i).\,\!

That is, the entropy of the event ''x'' is the sum, over all possible outcomes ''i'' of ''x'', of the product of the probability of outcome ''i'' times the log of the inverse of the probability of ''i'' (which is also called ''i'''s '' Surprisal '' - the entropy of ''x'' is the expected value of its outcome's surprisal). We can also apply this to a general Probability Distribution , rather than a discrete-valued event.

Shannon shows that any definition of entropy satisfying his assumptions will be of the form:

::

-K\sum_{i=1}^np(i)\log p(i).\,\!

where ''K'' is a constant (and is really just a choice of measurement units).

Shannon defined a measure of entropy (''H'' = − ''p₁'' log₂ ''p₁'' − … − ''p_n'' log₂ ''p_n'') that, when applied to an information source, could determine the minimum channel capacity required to reliably transmit the source as encoded binary digits. The formula can be derived by calculating the mathematical expectation of the ''amount of information'' contained in a digit from the information source. Shannon's entropy measure came to be taken as a measure of the uncertainty about the realization of a random variable. It thus served as a proxy capturing the concept of information contained in a message as opposed to the portion of the message that is strictly determined (hence predictable) by inherent structures. For example, redundancy in language structure or statistical properties relating to the occurrence frequencies of letter or word pairs, triplets etc. See Markov Chain .

Shannon's definition of entropy is closely related to ''). Similarly, Maxwell's Demon reverses thermodynamic entropy with information; but if it is itself bound by the laws of thermodynamics, getting rid of that information exactly balances out the thermodynamic gain the demon would otherwise achieve.

It is important to remember that entropy is a quantity defined in the context of a probabilistic model for a data source. Independent fair coin flips have an entropy of 1 bit per flip. A source that always generates a long string of A's has an entropy of 0, since the next character will always be an 'A'.

The entropy rate of a data source means the average number of Bit s per symbol needed to encode it. Empirically, it seems that entropy of English text is between 1.1 and 1.6 bits per character, though clearly that will vary from text source to text source. Experiments with human predictors show an information rate of 1.1 or 1.6 bits per character, depending on the experimental setup; the PPM Compression Algorithm can achieve a compression ratio of 1.5 bits per character.

From the preceding example, note the following points:

# The amount of entropy is not always an integer number of bits.
# Many data bits may not convey information. For example, data structures often store information redundantly, or have identical sections regardless of the information in the data structure.

Entropy effectively bounds the performance of the strongest lossless (or nearly lossless) compression possible, which can be realized in theory by using the Typical Set or in practice using Huffman , Lempel-Ziv or Arithmetic Coding . The performance of existing data compression algorithms is often used as a rough estimate of the entropy of a block of data.

A common way to define entropy for text is based on the Markov Model of text. For an order-0 source (each character is selected independent of the last characters), the binary entropy is:

:

H(\mathcal{S}) = - \sum p_i \log_2 p_i, \,\!

where ''p''_''i'' is the probability of ''i''. For a first-order Markov Source (one in which the probability of selecting a character is dependent only on the immediately preceding character), the entropy rate is:

:

H(\mathcal{S}) = - \sum_i p_i \sum_j  \  p_i (j) \log_2 p_i (j), \,\!

where ''i'' is a state (certain preceding characters) and

p_i(j)

is the probability of

j

given

i

as the previous character (s).

For a second order Markov source, the entropy rate is

:

H(\mathcal{S}) = -\sum_i p_i \sum_j p_i(j) \sum_k p_{i,j}(k)\ \log \  p_{i,j}(k). \,\!

In general the b-ary entropy of a source

\mathcal{S}

= (''S'',''P'') with Source Alphabet ''S'' = {''a''₁, …, ''a_n''} and Discrete Probability Distribution ''P'' = {''p''₁, …, ''p_n''} where ''p_i'' is the probability of ''a_i'' (say ''p_i'' = ''p''(''a_i'')) is defined by:

:

H_b(\mathcal{S}) = - \sum_{i=1}^n p_i \log_b p_i \,\!

Note: the ''b'' in "''b''-ary entropy" is the number of different symbols of the "ideal alphabet" which is being used as the standard yardstick to measure source alphabets. In information theory, two symbols are Necessary And Sufficient for an alphabet to be able to encode information, therefore the default is to let ''b'' = 2 ("binary entropy"). Thus, the entropy of the source alphabet, with its given empiric probability distribution, is a number equal to the number (possibly fractional) of symbols of the "ideal alphabet", with an optimal probability distribution, necessary to encode for each symbol of the source alphabet. Also note that "optimal probability distribution" here means a Uniform Distribution : a source alphabet with ''n'' symbols has the highest possible entropy (for an alphabet with ''n'' symbols) when the probability distribution of the alphabet is uniform. This optimal entropy turns out to be

log_b \, n

.

Another way to define the entropy function ''H'' (not using the Markov Model ) is by proving that ''H'' is uniquely defined (as earlier mentioned) Iff ''H'' satisfies 1) - 3):

1) ''H''(''p''₁, …, ''p_n'') is Defined and Continuous For All ''p''₁, …, ''p_n'' where ''p_i''

\in

{Link without Title} For All ''i'' = 1, …, ''n'' and ''p''₁ + … + ''p_n'' = 1. (Remark that the function solely depends on the probability distribution, not the alphabet.)

2) For All Positive Integers ''n'', ''H'' satisfies

:

H\underbrace{\left(rac{1}{n}, \ldots, rac{1}{n}
ight)}_{n\ \mathrm{arguments}} < H\underbrace{\left(rac{1}{n+1}, \ldots, rac{1}{n+1}
ight).}_{n+1\ \mathrm{arguments}}

3) For Positive Integers ''b_i'' where ''b''₁ + … + ''b_k'' = ''n'', ''H'' satisfies

:

H\underbrace{\left(rac{1}{n}, \ldots, rac{1}{n}
ight)}_n = H\underbrace{\left(rac{b_1}{n}, \ldots, rac{b_k}{n}
ight)}_k + \sum_{i=1}^k rac{b_i}{n} H\underbrace{\left(rac{1}{b_i}, \ldots, rac{1}{b_i}
ight)}_{b_i}.

EFFICIENCY

A source alphabet encountered in practice should be found to have a probability distribution which is less than optimal. If the source alphabet has ''n'' symbols, then it can be compared to an "optimized alphabet" with ''n'' symbols, whose probability distribution is uniform. The ratio of the entropy of the source alphabet with the entropy of its optimized version is the efficiency of the source alphabet, which can be expressed as a Percentage .

This implies that the efficiency of a source alphabet with ''n'' symbols can be defined simply as being equal to its ''n''-ary entropy.

DERIVATION OF SHANNON'S ENTROPY

Since the entropy was given as a definition, it does not need to be derived. On the other hand, a "derivation" can be given which gives a sense of the motivation for the definition as well as the link to thermodynamic entropy.

Q. Given a Roulette with ''n'' pockets which are all equally likely to be landed on by the ball, what is the probability of obtaining a distribution (''A₁'', ''A₂'', …, ''A_n'') where ''A_i'' is the number of times pocket ''i'' was landed on and

:

P = \sum_{i=1}^n A_i \,\!

is the total number of ball-landing events?

A. The probability is a Multinomial Distribution , viz.

:

p = {\Omega \over \Tau} = {P! \over A_1! \ A_2! \ A_3! \ \cdots \ A_n!} \left(rac1n
ight)^P \,\!

where

:

\Omega = {P! \over A_1! \ A_2! \ A_3! \ \cdots \ A_n!} \,\!

is the number of possible combinations of outcomes (for the events) which fit the given distribution, and

:

\Tau = n^P \

is the number of all possible combinations of outcomes for the set of ''P'' events.

Q. And what is the entropy?

A. The entropy of the distribution is obtained from the Logarithm of Ω:
:

H = \log \Omega = \log rac{P!}{A_1! \ A_2! \ A_3! \cdots \ A_n!} \,\!

= \log P! - \log A_1! - \log A_2! - \log A_3! - \cdots - \log A_n! \

= \sum_i^P \log i - \sum_i^{A_1} \log i - \sum_i^{A_2} \log i - \cdots - \sum_i^{A_n} \log i \,\!

The summations can be approximated closely by being replaced with integrals:

:

H = \int_1^P \log x \, dx - \int_1^{A_1} \log x \, dx - \int_1^{A_2} \log x \, dx - \cdots - \int_1^{A_n} \log x \, dx. \,\!

The integral of the logarithm is

:

\int \log x \, dx = x \log x - \int x \, {dx \over x} = x \log x - x. \,\!

So the entropy is

:

H = (P \log P - P + 1) - (A_1 \log A_1 - A_1 + 1) - (A_2 \log A_2 - A_2 + 1) - \cdots - (A_n \log A_n - A_n + 1)

= (P \log P + 1) - (A_1 \log A_1 + 1) - (A_2 \log A_2 + 1) - \cdots - (A_n  \log A_n + 1)

= P \log P - \sum_{x=1}^n A_x \log A_x + (1 - n) \,\!

Change ''A_x'' to ''p_x = A_x/P'' and change ''P'' to ''1'' (in order to measure the "bias" or "unevenness", in the probability distribution of the pockets for a single event), then

:

H = (1 - n) - \sum_{x=1}^n p_x \log p_x \,\!

and the term (1 − ''n'') can be dropped since it is a constant, independent of the ''p_x'' distribution. The result is

:

H = - \sum_{x=1}^n p_x \log p_x \,\!

.

Thus, the Shannon entropy is a consequence of the equation

:

H = \log \Omega \

which relates to Boltzmann's definition,

:

\mathcal{S} = K \ln \Omega

,

of thermodynamic entropy.

PROPERTIES OF SHANNON'S INFORMATION ENTROPY

We write ''H''(''X'') as ''H_n''(''p₁'',...,''p_n''). The Shannon entropy satisfies the following properties:

For any ''n'', ''H_n''(''p₁'',...,''p_n'') is a continuous and symmetric function on variables ''p₁'', ''p₂'',...,''p_n''.

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

H_{n+1}(p_1,\ldots,p_n,0) = H_n(p_1,\ldots,p_n)

Entropy is maximized when the probability distribution is uniform. For all ''n'',

H_n(p_1,\ldots,p_n) \leq H_n\Big(rac{1}{n},\ldots,rac{1}{n} \Big)

Following from the Jensen inequality,
:

\leq \log_b \Big( E\Big[ rac{1}{p(X)} \Big] \Big) = \log_b(n)

If $p_{ij}, 1\leq i \leq m, 1\leq j \leq n$ are non-negative real numbers summing up to one, and $q_i = \sum_{j=1}^n p_{ij}$ , then

H_{mn}(p_{11},\ldots, p_{mn}) = H_m(q_1,\ldots,q_m) + \sum_{i=1}^m q_i H_n\Big(rac{p_{i1}}{q_i},\ldots, rac{p_{in}}{q_i} \Big)

If we partition the ''mn'' outcomes of the random experiment into ''m'' groups with each group containing ''n'' elements, we can do the experiment in two steps: first, determine the group to which the actual outcome belongs to; then, find the outcome in that group. The probability that you will observe group ''i'' is ''q_i''. The conditional probability distribution function for group ''i'' is ''p_i1''/''q_i'',...,''p_in''/''q_i''). The entropy
:

H_n\Big(rac{p_{i1}}{q_i},\ldots, rac{p_{in}}{q_i} \Big)

is the entropy of the probability distribution conditioned on group ''i''. This property means that the total information is the sum of the information gained in the first step, ''H_m''(''q₁'',..., ''q_n''), and a weighted sum of the entropies conditioned on each group.

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

H_n(p_1,\ldots,p_n) = -k \sum_{i=1}^n p_i \log p_i

,
where ''k'' is a positive constant representing the desired unit of measurement.

DERIVING CONTINUOUS ENTROPY FROM DISCRETE ENTROPY: THE BOLTZMANN ENTROPY

The Shannon entropy is restricted to finite sets. It seems that the formula

)

) is usually referred to as the Boltzmann entropy, '''continuous entropy''', or Differential Entropy . Although the analogy between both functions is suggestive, the following question must be set: is the Boltzmann entropy a valid extension of the Shannon entropy? To answer this question, we must establish a connection between the two functions:

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 whose probabilities are denoted by ''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.

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

:

f(x_i) \Delta = \int_{i\Delta}^{(i+1)\Delta} f(x)\, dx

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

:

\int_{-\infty}^{\infty} f(x)\, dx = \lim_{\Delta 	o 0} \sum_{i = -\infty}^{\infty} f(x_i) \Delta

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

We will denote

:

H^{\Delta} :=- \sum_{i=-\infty}^{\infty} \Delta f(x_i) \log \Delta f(x_i)

and expanding the logarithm, we have

:

H^{\Delta} = - \sum_{i=-\infty}^{\infty} \Delta f(x_i) \log \Delta f(x_i)

= - \sum_{i=-\infty}^{\infty} \Delta f(x_i) \log f(x_i) -\sum_{i=-\infty}^{\infty} f(x_i) \Delta \log \Delta.

\Delta 	o 0

, we have

:

\sum_{i=-\infty}^{\infty} f(x_i) \Delta 	o \int f(x)\, dx = 1

and so

:

\sum_{i=-\infty}^{\infty} \Delta f(x_i) \log f(x_i) 	o \int f(x) \log f(x)\, dx.

But note that

\log \Delta 	o -\infty

\Delta 	o 0

, therefore we need a special definition of the differential or continuous entropy:

:

= -\int_{-\infty}^{\infty} f(x) \log f(x)\,dx,

which is, as said before, referred to as the Boltzmann entropy. This means that the Boltzmann entropy ''is not'' a limit of the Shannon entropy for ''n'' → ∞ and, consequently is not a measure of uncertainty and information.

SEE ALSO

Entropy Encoding

Kolmogorov-Sinai Entropy in Dynamical System s

Theil Index

Perplexity

EXTERNAL LINKS

Information is not entropy, information is not uncertainty ! - a discussion of the use of the terms "information" and "entropy".

I'm Confused: How Could Information Equal Entropy? - a similar discussion on the bionet.info-theory FAQ.

Java "entropy pool" for cryptographically-secure unguessable random numbers

Description of information entropy from "Tools for Thought" by Howard Rheingold

	CATEGORIES ABOUT INFORMATION ENTROPY

	entropy and information

	information theory

	statistics

	randomness

	APPAREL
	BABY
	BEAUTY
	BOOKS
	CAR TOYS
	CELL PHONES
	DVD'S
	ELECTRONICS
	GOURMET FOOD
	GROCERIES
	HEALTH & PERSONAL
	HOME & GARDEN
	JEWELRY
	MUSIC
	MUSIC INSTRUMENTS
	OFFICE PRODUCTS
	SOFTWARE
	SPORTING GOODS
	TOOLS & HARDWARE
	TOYS
	VIDEO GAMES
	SHOPPING HOME

	MORE SHOPPING...

Information About

Shannon Entropy