Conditional entropy

from Wikipedia, the free encyclopedia

In information theory , conditional entropy is a measure of the “uncertainty” about the value of a random variable that remains after the result of another random variable becomes known. The conditional entropy is written and has a value between 0 and , the original entropy of . It is measured in the same unit of measure as entropy.

Specifically, it has the value 0 if the value of can be determined from functional, and the value if and are stochastically independent .

definition

Let be a discrete random variable and its stock of values , that is to say, there is at most a countable set with . Then the entropy of is through

defined, whereby the values ​​2 ( Bit ) or e ( Nat ) are typically assumed for the corresponding units. If the probability is the same for one , it is set by convention , so the corresponding term is not included in the sum.

Let it be an event with . Then one defines the conditional entropy of given by replacing the probability with the conditional probability ; H.

.

Now be a discrete random variable with a range of values . Then the conditional entropy of given is defined as the weighted mean of the conditional entropies of given the events for , i. H.

.

At a higher level of abstraction, it is the conditional expected value of the information function given and the expected value of the function .

properties

A memoryless channel connects two sources. The transinformation I (x; y) is the information that was sent by X and also received by Y.

A simple calculation shows

,

so the uncertainty of given is equal to the uncertainty of and minus the uncertainty of .

It is with equality if and only if and are stochastically independent. This follows from the fact that if and only if and are stochastically independent. It also means that is, so the entire information received is just misinformation. Similarly, the complete information from source X is lost, so that no transinformation is then available.

Also applies

,

with equality if and only if functionally depends on, d. H. for a function .

Block entropy

Transferred to a multivariate random variable of length , as a representation for a block of symbols , the conditional entropy can be defined as the uncertainty of a symbol (according to a certain given block):

with ,

where denotes the block entropy . For the conditional entropy , i.e. the uncertainty of a symbol after a -block, it follows:

The definitions of block entropy and conditional entropy are equivalent in the border crossing, cf. Source tropy .

Transinformation , which indicates the strength of the statistical relationship between two random variables, is also closely related to conditional entropy .

example

Let X be a source that periodically sends the characters ... 00100010001000100010 ...

Now the conditional entropy of the currently observed character is to be calculated taking into account previous characters.

No characters considered

The calculation is based on the definition of entropy .

Probability table:

x = 0 x = 1
P (X = x)

A mark taken into account

Now let X: = x t and Y: = x t-1 . The following probabilities result:

Probability tables:

P (X | Y) x = 0 x = 1
y = 0
y = 1

The following applies:

          

y = 0 y = 1

Two signs considered

Let X: = x t and Y: = (x t-2 , x t-1 ). The following probabilities result:

Y = (1,1) never appears in the source, so does not need to be considered.

Probability tables:

P (X | Y) X = 0 X = 1
y = (0.0)
y = (0.1)
y = (1.0)
y = (1.1)

The following applies:

y = (0.0) y = (0.1) y = (1.0) y = (1.1)
P (Y = y)

The following applies:

Three characters considered

If three consecutive signs are already known, the following sign is also determined (because the source behaves periodically). There is thus no new information about the next character. Accordingly, the entropy must be zero. This can also be seen from the probability table:

P (X | Y) X = 0 X = 1
y = (0,0,0)
y = (0,0,1)
y = (0,1,0)
y = (0,1,1)
y = (1,0,0)
y = (1,0,1)
y = (1,1,0)
y = (1,1,1)

The following applies:

           

Impossible events are marked here with "-", e.g. B. at y = (1,0,1). The given source will never deliver this output, since a one is always followed by three zeros.

You can see that in the table there are no other probabilities than 0 or 1. Since according to the definition of entropy, the entropy must ultimately be.

Explanation of the probability tables

The tables refer to the example character sequence above.

P (X | Y) x = 0 x = 1
y = 0
y = 1

The following applies:

Here one considers a character under the condition of the previous character . For example , if there is a character , the question is: What is the probability of the following character or ? The next sign is always for . So is . It also follows that is because the row sum is always one.

P (X) x t = 0 x t = 1
x t-1 = 0
x t-1 = 1

The following applies:

Here one looks at the frequency of occurrence of a character combination. You can read from the table that the letter combinations (0,1) and (1,0) occur just as often. The sum of all matrix entries is one.

Entropy and information content

In this example, the entropy falls all the more the more characters are taken into account (see also: Markov process ). If the number of characters taken into account is chosen to be sufficiently large, the entropy converges to zero.

One would like to the information content of the given string of n = 12 characters calculate, is obtained according to the definition I ges = n⋅H (X | Y) at ...

... no characters considered, 9.39 bit total information. (Information content of statistically independent events)
... one considered character 8.26 bit total information.
... two characters considered, 6 bit total information.
... three characters taken into account, 0 bit total information.

literature

  • Martin Werner: Information and Coding. Basics and Applications, 2nd edition, Vieweg + Teubner Verlag, Wiesbaden 2008, ISBN 978-3-8348-0232-3 .
  • Karl Steinbuch, Werner Rupprecht: communications engineering. An introductory presentation, Springer Verlag, Berlin / Heidelberg 1967.
  • R. Mathar: Information Theory. Discrete models and processes, BG Teubner Verlag, Stuttgart 1996, ISBN 978-3-519-02574-0 .

Web links