Desurvire E. Classical and Quantum Information Theory: An Introduction for the Telecom Scientist

Подождите немного. Документ загружается.

4.5 Exercises 67

The fact that several discrete (and continuous) random physical processes are ruled

by exact or near-maximum entropy distributions can be explained by the following: if a

system X offers a large number of possible random arrangements x

(called microstates),

and if such arrangements are equally probable (all independent of each other or past

microstate history), then the system’s entropy H (X) is a maximum, as I have shown

earlier. In some physical processes (like ampliﬁcation of coherent light), there is no

reason for microstates to be equiprobable, which explains the discrepancy between

observed and maximal entropies. The discrepancy, however, vanishes when the number

of possible microstates becomes inﬁnite. In some other physical processes (such as the

electron occupation of atomic energy levels, or the spontaneous emission of photons

by single atoms), the microstates are strictly equiprobable and the system’s entropy is

maximum, as we have seen.

The so-called maximum entropy principle,

is used in several domains of statisti-

cal sciences, from engineering and physics to computer vision, image processing and

reconstruction, language analysis, urban design, marketing, elections, business, eco-

nomics, and ﬁnance! The underlying motivation of maximum-entropy models (MEM) is

to derive, heuristically, the PDF of a complex random process by using available data

samples observed from reality. These experimental data are then used as constraints to

compute the maximum-entropy PDF, elegantly referred to as epistemic. The philosophy

and rationale of the maximum-entropy principle approach is: “Given facts or relations

concerning events, which are veriﬁed in the physical world, what is the best statistical

model available to predict the rest?”

The issue of maximizing entropy is revisited in Chapter 5 when considering continuous

sources.

4.5 Exercises

4.1 (B): What is the entropy in the action of picking, at random, one card out of a

32-card deck? What is the entropy for picking a hand of four cards?

4.2 (B): A bag contains eight balls, including one red, two blue, two green, and three

yellow ones. The events consist in picking, at random, a ball from the bag, seeing

the color, and then replacing the ball. What is the entropy of the source?

4.3 (M): Download from any website the text of the US Declaration of Independence,

www.ushistory.org/declaration/document/index.htm,

www.law.indiana.edu/uslawdocs/declaration.html,

www.loc.gov/rr/program/bib/ourdocs/DeclarInd.html,

www.archives.gov/exhibits/charters/declaration.html,

See, for instance: www.answers.com/topic/principle-of-maximum-entropy?cat=technology&hl?function=

hl?derivation=&hl?partition=, www.answers.com/maximum+entropy+probability+distribution?cat=

technology.

68 Entropy

from, “When in the Course of human events...” to “...our Fortunes and our

sacred Honor.” What is the entropy of the selected text, as viewed as a source of

26 + 1 characters (including space)?

What is the entropy of the selected text, without the space character? (Computing

method clue: see Chapter 4, note 11.)

4.4 (M): Copy into a text ﬁle a “very big” prime number, for instance, a large

“Mersenne,” which you can download from the websites:

www.mersenne.org/,

www.isthe.com/chongo/tech/math/prime/mersenne.html#M32582657,

http://primes.utm.edu/largest.html.

For expediency, reduce the text source to only a few ten thousand digits. Compute

the entropy of the source. Could the result have been guessed directly? (Computing

method clue: see Chapter 4, note 11.)

5 Mutual information and

more entropies

This chapter marks a key turning point in our journey in information-theory land.

Heretofore, we have just covered some very basic notions of IT, which have led us,

nonetheless, to grasp the subtle concepts of information and entropy. Here, we are

going to make signiﬁcant steps into the depths of Shannon’s theory, and hopefully

begin to appreciate its power and elegance. This chapter is going to be somewhat more

mathematically demanding, but it is guaranteed to be not signiﬁcantly more complex

than the preceding materials. Let’s say that there is more ink involved in the equations

and the derivation of the key results. But this light investment will turn out well worth it

to appreciate the forthcoming chapters!

I will ﬁrst introduce two more entropy deﬁnitions: joint and conditional entropies,

just as there are joint and conditional probabilities. This leads to a new fundamental

notion, that of mutual information, which is central to IT and the various Shannon’s

laws. Then I introduce relative entropy, based on the concept of “distance” between two

PDFs. Relative entropy broadens the perspective beyond this chapter, in particular with

an (optional) appendix exploration of the second law of thermodynamics, as analyzed

in the light of information theory.

5.1 Joint and conditional entropies

So far, in this book, the notions of probability distribution and entropy have been

associated with single, independent events x, as selected from a discrete source X =

{

}

With the example of written language (Chapter 4), we have seen that the occurrence of

single characters from the alphabetical-character source X =

{

A,...,Z

}

is bound to a

quasi-exponential PDF, which varies according to language, context, and time.

Considering the fact that language is made out of words, and not single characters,

we realize that the previous analysis is incomplete. For instance, we could make an

inventory of all words made of two, three, or more characters, and derive a new set of

statistics. We could then say how often in English the letter E appears next to the letter

A, or what the probability is that a given English word of ﬁve characters simultaneously

contains the letters A, T, and N, and, given the knowledge that the ﬁrst two letters

are TH, what the probability is that the third one is E, to form the ubiquitous word

THE.

70 Mutual information and more entropies

This observation leads us to deﬁning the entropy associated with joint events,on

one hand, or conditional events on the other hand. To do this, let us brieﬂy recall the

properties of joint and conditional probabilities, which have been outlined in Chapter 1,

and give them further attention here.

Consider two events x ∈ X and y ∈ Y , where X, Y are two random sources. The two

events can occur simultaneously, regardless of any sequence order: we just observe x

and y,ory and x, which conveys the same information. Alternatively, we can observe

x then y, but for some reason we seem never to get y then x. Our observation could also

be that whenever x happens, we are likely to see y happen as well. Alternatively, the fact

that x happens could have no incidence on the outcome of y. For instance, deﬁne the

following event sources:

X = {quarterly results of a major telecom company},

Y = {stock market},

Z = {weather forecast},

W = {outbound city trafﬁc}.

It is safe to say (scientiﬁcally speaking!) that events x from X and have no impact

whatsoever on events z or w from Z or W . Thus events x and z (or x and w)are

independent. The probabilities p(x) that x = excellent, and p(z) that z = cold and rainy

also have different and unrelated PDFs. As we know from Chapter 1, the joint probability

that we observe both events simultaneously is given by the mere product:

p(x, y) = p(excellent, cold and rainy) = p(x)p(y). (5.1)

In Eq. (5.1), the function p(x, y) is called the joint probability or joint distribution of

events (x, y). The meaning of the “,” in the argument is that of the logical AND.

The

joint distribution is, thus, always symmetrical, i.e., p(x, y) = p(y, x), because the joint

events x AND y and y AND x are strictly same. Since p(x, y) is a probability, we have

the summing properties













y∈Y

p(x, y) = p(x)



x∈X

p(x, y) = p(y)



x∈X



y∈Y

p(x, y) = 1.

(5.2)

But the relation concerning any event pairs (x, y)or(z,w) of the above-deﬁned sets is

not at all this straightforward. This is because we should expect that these events are

not independent: good or bad quarterly results do affect the stock market, good or bad

weather forecasts do affect the outbound city trafﬁc.

One then deﬁnes the conditional probability p(a|b) as representing the probability

of observing event a given the observation or knowledge of event b.If p(a|b) = p(a),

this means that event a occurs regardless of b, or that the two are independent. Of

Joint probabilities p(x, y) can also be written in the logical form p(x ∧ y) where the sign ∧ stands for the

logical or Boolean operation AND.

5.1 Joint and conditional entropies 71

course, the same conclusion applies if p(b|a) = p(b). As we have seen in Chapter 1,

the fundamental relation between joint and conditional probabilities, is given by Bayes’s

theorem:

p(a, b) = p(a|b) p(b) = p(b|a)p(a). (5.3)

Using the summing properties in Eq. (5.2),wealsohave













b∈B

p(a|b) p(b) = p(a)



a∈A

p(b|a) p(a) = p(b)



a∈A



b∈B

p(b|a) p(a) =



a∈A



b∈B

p(a|b) p(b) = 1,

(5.4)

noting that conditional probabilities p(a|x) do not sum over x up to unity, unlike the

probabilities p(x) associated with single events.

It is straightforward to verify from

the above relations that if the events a and b are independent, then p(a|b) = p(a) and

p(b|a) = p(b). I provide next a numerical example of joint and conditional probabilities,

which we will also use further on to introduce new entropy concepts.

Stock exchange

Let the ﬁrst event source be three possible conclusions for the quarterly sales report from

a public company, namely:

x ∈ X ={good, same, bad}≡

{

, x

}

meaning that the results are in excess of the predictions (good), or on target (same), or

under target (bad). The second event source is the company’s stock value, as reﬂected

by the stock exchange, with

y ∈ Y ={up, steady, down}≡

{

, y

}

Then we assume that there exists some form of correlation between the company’s

results (x ∈ X ) and its stock value (y ∈ Y ). A numerical example of joint and con-

ditional probability data, p(x

, y

), p(x

) and p(y

), is shown in Table 5.1.The

ﬁrst group of numerical data, shown at the top of Table 5.1 corresponds to the joint

probabilities p(y

, x

) ≡ p(x

, y

). Summing up the data by rows (i) or by columns

( j) yields the probabilities p(x

)or p(y

), respectively. The double checksum (bottom

right), which yields unity through summing by row or by column, is also shown for

consistency. The two other groups of numerical data in Table 5.1 correspond to the

conditional probabilities p(x

) and p(y

). These are calculated through Bayes’s

theorem p(x

) = p(x

, y

)/ p(y

) and p(y

) = p(x

, y

)/ p(x

). The intermediate

columns providing the data p(x

)p(y

) = p(y

)p(x

) ≡ p(x

, y

) and their check-

sums by column are shown in the table for consistency.

Yet we have the property



a∈A

p(a|b) = 1foranyeventb ∈ B, summing over all possible events a ∈ A.

72 Mutual information and more entropies

Table 5.1 Example of joint and conditional probability distributions constructed from the two event sources x ∈

X = {good, same, bad} ≡

{

, x

}

for a company’s quarterly sales results and y ∈ Y = {up, steady, down}

≡

{

, y

}

for its stock value. The table on top shows the joint probability p(x

, y

), consistent with the probabilities

p(x

) and p(y

) of the individual events x

and y

(values given in column or line p, respectively). The right column and

bottom line provide the different checksums. The two other tables (middle and bottom) show the conditional probabilities

p(y

) and p(x

), along with their different checksums.

(up) y

(steady) y

(down)

p(x

, y

) p 0.300 0.500 0.200



(good) 0.160 0.075 0.075 0.010 0.160

(same) 0.750 0.210 0.400 0.140 0.750

(bad) 0.090 0.015 0.025 0.050 0.090



= 0.300 0.500 0.200 1.000

(up) p(y

, x

) y

(steady) p(y

, x

) y

(down) p(y

, x

)

p(y

, x

) p 0.300 = p(y

)p(x

) 0.500 = p(y

)p(x

) 0.200 = p(y

)p(x

)

(good) 0.160 0.469 0.075 0.469 0.075 0.063 0.010

(same) 0.750 0.280 0.210 0.533 0.400 0.187 0.140

(bad) 0.090 0.167 0.015 0.278 0.025 0.556 0.050



= 0.300 0.500 0.200 1.000

(good) p(x

)p(y

) x

(same) p(x

, y

) x

(bad) p(x

, y

)

p(x

, y

) p 0.160 = p(x

)p(y

) 0.750 = p(x

)p(y

) 0.090 = p(x

)p(y

)

(up) 0.300 0.250 0.075 0.700 0.210 0.050 0.015

(steady) 0.500 0.150 0.210 0.800 0.400 0.050 0.025

(down) 0.200 0.010 0.015 0.700 0.1 0.250 0.050



= 0.300 0.750 0.090 1.000

We deﬁne the joint entropy, or the entropy H (X, Y ) associated with the joint distri-

bution p(x, y) with x ∈ X and y ∈ Y , namely:

H(X, Y ) =−



x∈X



y∈Y

p(x, y)log

p(x, y). (5.5)

This joint entropy represents the average information derived from joint events occurring

from two sources X and Y . The unit of H (X, Y )isbit/symbol.

We then deﬁne the conditional entropy H (X|Y ) through:

H(X |Y ) =−



x∈X



y∈Y

p(x, y)log

p(x|y). (5.6)

The conditional entropy H (X|Y ) corresponds to the average information conveyed by

the conditional PDF, p(x|y). Put simply, H (X|Y ) represents the information we learn

from source X, given the information we have from source Y .Itsunitisalsobit/symbol.

Or, equivalently, H(X, Y ) =−



p(x

, y

)log

p(x

, y

5.1 Joint and conditional entropies 73

In the joint and conditional entropy deﬁnitions, note that the two-dimensional aver-

aging over the event space

{

X, Y

}

consistently involves the joint distribution p(x, y).

As a property, the conditional entropy H (X|Y ) is generally different from H (Y |X),

which is deﬁned as

H(Y |X ) =−



x∈X



y∈Y

p(x, y)log

p(y|x), (5.7)

since in the general case, p(x|y) = p(y|x). The conditional entropy H (X |Y )orH (Y |X)

is sometimes referred to by the elegant term equivocation.

It is easily veriﬁed that if the sources X, Y represent independent events, then

(a) H (X, Y ) = H (X) + H(Y ), (5.8)

(b) H (X|Y ) = H (X)m and H (Y |X) = H (Y ). (5.9)

As it can also be easily established, the joint and conditional entropy are related to each

other through the chain rule:



H(X, Y ) = H (X|Y ) + H (Y )

H(X, Y ) = H (Y |X) + H (X).

(5.10)

We may ﬁnd the chain rule easier to memorize under the form



H(X |Y ) = H (X, Y ) − H (Y )

H(Y |X ) = H (X, Y ) − H (X),

(5.11)

which states that, given a source X or Y , any advance knowledge (or “conditioning”)

from the other source Y or X reduces the joint entropy “reserve” H (X, Y ) by the net

amount H(Y )orH (X), respectively; these are positive quantities. In other words, the

prior information one may gain from a given source is made at the expense of the

information available from the other source, unless the two are independent.

We can illustrate the above properties through our stock-exchange PDF data from

Table 5.1. We want, here, to determine how the average information from the com-

pany’s sales, H (X ), is affected from that concerning the stocks, H(Y ), and the reverse.

The computations of H (X), H (Y ), H (X, Y ), H (Y |X ) and H (X |Y ) are detailed in

Table 5.2. It is seen from the table that the results and stock entropies compute to H(X ) =

1.046 and H (Y ) = 1.485, respectively (for easier reading, I omit here the bit/symbol

units). The joint entropy is found to be H(X, Y ) = 2.466, which is lower than the sum

H(X ) + H(Y ) =2.532. This proves that the two sources are not independent, namely, that

they have some information in common. We ﬁnd indeed that the conditional entropies

satisfy:

H(Y |X ) = 1.418 < H (Y ) = 1.485,

H(X |Y ) = 0.980 < H (X ) = 1.046,

or, equivalently, (using four decimal places, for accuracy (see Table 5.2):

H(Y ) − H (Y |X) = 1.4855 − 1.4188 = 0.0667,

H(X ) − H(X |Y ) = 1.0469 −0.9802 = 0.0667.

74 Mutual information and more entropies

Table 5.2 From top to bottom: calculation of entropies H (X ), H (Y), H(X , Y), H (Y|X ) and H (X |Y), as based on the

numerical example of Table 5.1. The two equations shown at the bottom of the table prove the fundamental relations

between single-event entropies, conditional entropies, and the joint entropy.

= p(x

)

= p(y

)

−u

log u

−v

log v

(good) 0.160 0.423 y

(up) 0.300 0.521

(same) 0.750 0.311 y

(steady) 0.500 0.500

(bad) 0.090 0.313 y

(down) 0.200 0.464

H(X) = 1.0469 H(Y) = 1.4855

H(X ) + H (Y ) = 2.5324

= p(x

, y

)

−u

log u

i1‘

−u

log u

−u

log u

0.075 0.280 0.075 0.280 0.010 0.066

0.210 0.473 0.400 0.529 0.140 0.397

0.015 0.091 0.025 0.133 0.050 0.216



= 0.844



= 0.942



= 0.680

H(X, Y ) = 2.4657

= p(y

)

−u

log v

−u

log v

−u

log v

0.469 0.075 0.082 0.469 0.075 0.082 0.063 0.010 0.040

0.280 0.210 0.386 0.533 0.400 0.363 0.187 0.140 0.339

0.167 0.015 0.039 0.278 0.025 0.046 0.556 0.050 0.042



= 0.506



= 0.491



= 0.421

H(Y |X ) = 1.4188

= p(x

)

1 j

−u

log w

1 j

2 j

−u

log w

2 j

3 j

−u

log w

3 j

0.250 0.075 0.150 0.700 0.210 0.108 0.050 0.015 0.065

0.150 0.075 0.205 0.800 0.400 0.129 0.050 0.025 0.108

0.050 0.010 0.043 0.700 0.140 0.072 0.250 0.050 0.100



= 0.398



= 0.309



= 0.421

H(X |Y ) = 0.9802

H(X, Y ) = H(Y |X ) + H (X )

2.4657 = 1.4188 +1.0469

= H (X|Y ) + H (Y )

= 0.9802 + 1.4855.

These two results mean that the prior knowledge of the company’s stocks contains an

average of 0.0667 bit/symbol of information on the company’s quarterly result, and the

reverse is also true. As we shall see in the next section, the two differences above are

always equal and they are called mutual information. Simply put, the mutual information

is the average information that two sources share in common.

5.2 Mutual information 75

5.2 Mutual information

I introduce yet another type of entropy deﬁnition, which will bring us to some closing

point and our ﬁnal reward. We can deﬁne the mutual information of two sources X and

Y as the bit/symbol quantity:

H(X ; Y ) =



x∈X



y∈Y

p(x, y)log

p(x, y)

p(x)p(y)

. (5.12)

We may note the absence of a minus sign in the above deﬁnition, unlike in

H(X, Y ), H (Y |X ), and H (X|Y ). Also note the “;” separator, which distinguishes mutual

information from joint entropy H (X, Y ). Mutual information is also often referred to in

some textbooks as I (X; Y ) instead of H(X ; Y ).

Since the logarithm argument is unity when the two sources are independent

(p(x, y) = p(x)p(y)), we immediately observe that the mutual information is equal

to zero in this case. This reﬂects the fact that independent sources do not have any

information in common.

It takes a bit of painstaking but straightforward computation to show the following

three equalities:

H(X ; Y ) = H (X) − H (X |Y )

= H (Y ) − H (Y |X) (5.13)

= H (X) + H(Y ) − H(X, Y ).

The ﬁrst two equalities above conﬁrm the observation derived from our previous numer-

ical example. They can be interpreted according to the following statement: mutual

information is the reduction of uncertainty in X that we get from the knowledge of Y

(and the reverse).

The last equality, as rewritten under the form

H(X, Y ) = H (X) + H (Y ) − H (X; Y ), (5.14)

shows that the joint entropy of two sources is generally less than the sum of the source

entropies. The difference is the mutual information that the sources have in common,

which reduces the net uncertainty or joint entropy.

Finally, we note from the three relations in Eq. (5.13) that the mutual information

is symmetrical in the arguments, namely, H(X ; Y ) = H (Y ; X ), as is expected from its

very meaning.

The different entropy deﬁnitions introduced up to this point may seem a bit abstract

and their different relations apparently not very practical to memorize! But the situation

becomes different after we draw an analogy with the property of ensembles.

Consider, indeed, two ensembles, called A and B. The two ensembles may be united

to form a whole, which is noted F = A ∪ B (A union B). The two ensembles may or

may not have elements in common. The set of common elements is called G = A ∩ B

(A intersection B). The same deﬁnitions of union and intersection apply to any three

ensembles A, B, and C. Figure 5.1 shows Venn diagram representations of such ensemble

combinations. While Venn diagrams were introduced in Chapter 1, I shall provide further

76 Mutual information and more entropies

∩

∪

∩ ¬

∩

∩ ¬

∩

∪

Figure 5.1 Venn diagrams representing two (A, B)orthree(A, B, C) ensembles with their

unions (A ∪ B or A ∪ B ∪ C) and their intersections (A ∩ B or A ∩ B ∩ C). The intersections

deﬁned by A ∩¬B, B ∩¬A,andA ∩¬B ∩¬C, A ∩ B ∩¬C are also shown.

related concepts here. In the case of two ensembles, there exist four subset possibilities,

as deﬁned by their elements’s properties:

Elements common to AorB: A ∪ B,

Elements common to A and B: A ∩ B,

Elements from A and not B: A ∩¬B,

Elements from B and not A: B ∩¬A.

In the conventional notations shown at right, we see that the symbol ∪stands for a logical

OR, the symbol ∩ stands for a logical AND, and the symbol ¬ stands for a logical

NO. These three different symbols, which are also called Boolean operators,

make

it possible to perform various mathematical computations in the ﬁeld called Boolean

logic. In the case of three ensembles A, B, C, we observe that there exist many more

subset possibilities (e.g., A ∩ B ∩ C, A ∩ B ∩¬C); it is left as an exercise to the reader

to enumerate and formalize them in terms of Boolean expressions. The interest of the

above visual description with the Venn diagrams is the straightforward correspondence

with the various entropy deﬁnitions that have been introduced. Indeed, it can be shown

To be accurate, Boolean logic uses instead the symbol ∨for “or” (the equivalent of ∪in ensemble language),

and the symbol ∧ for “and” (the equivalent of ∩ in ensemble language).