Conditional entropy

In information theory, the conditional entropy quantifies the amount of information needed to describe the outcome of a random variable formula_1 given that the value of another random variable formula_2 is known. Here, information is measured in shannons, nats, or hartleys. The "entropy of formula_1 conditioned on formula_2" is written as formula_5.
Definition.
The conditional entropy of formula_1 given formula_2 is defined as
where formula_8 and formula_9 denote the support sets of formula_2 and formula_1.
"Note:" Here, the convention is that the expression formula_12 should be treated as being equal to zero. This is because formula_13. 
Intuitively, notice that by definition of expected value and of conditional probability, formula_14 can be written as formula_15, where formula_16 is defined as formula_17. One can think of formula_18 as associating each pair formula_19 with a quantity measuring the information content of formula_20 given formula_21. This quantity is directly related to the amount of information needed to describe the event formula_20 given formula_23. Hence by computing the expected value of formula_24 over all pairs of values formula_25, the conditional entropy formula_26 measures how much information, on average, the variable formula_27 encodes about formula_28.
Motivation.
Let formula_29 be the entropy of the discrete random variable formula_1 conditioned on the discrete random variable formula_2 taking a certain value formula_32. Denote the support sets of formula_2 and formula_1 by formula_8 and formula_9. Let formula_1 have probability mass function formula_38. The unconditional entropy of formula_1 is calculated as formula_40, i.e.
where formula_42 is the information content of the outcome of formula_1 taking the value formula_44. The entropy of formula_1 conditioned on formula_2 taking the value formula_32 is defined analogously by conditional expectation: 
Note that formula_5 is the result of averaging formula_29 over all possible values formula_32 that formula_2 may take. Also, if the above sum is taken over a sample formula_53, the expected value formula_54 is known in some domains as equivocation.
Given discrete random variables formula_2 with image formula_8 and formula_1 with image formula_9, the conditional entropy of formula_1 given formula_2 is defined as the weighted sum of formula_29 for each possible value of formula_32, using formula_63 as the weights:
Properties.
Conditional entropy equals zero.
formula_65 if and only if the value of formula_1 is completely determined by the value of formula_2.
Conditional entropy of independent random variables.
Conversely, formula_68 if and only if formula_1 and formula_2 are independent random variables.
Chain rule.
Assume that the combined system determined by two random variables formula_2 and formula_1 has joint entropy formula_73, that is, we need formula_73 bits of information on average to describe its exact state. Now if we first learn the value of formula_2, we have gained formula_76 bits of information. Once formula_2 is known, we only need formula_78 bits to describe the state of the whole system. This quantity is exactly formula_5, which gives the "chain rule" of conditional entropy:
The chain rule follows from the above definition of conditional entropy:
In general, a chain rule for multiple random variables holds:
It has a similar form to chain rule in probability theory, except that addition instead of multiplication is used.
Bayes' rule.
Bayes' rule for conditional entropy states
"Proof." formula_84 and formula_85. Symmetry entails formula_86. Subtracting the two equations implies Bayes' rule.
If formula_1 is conditionally independent of formula_88 given formula_2 we have:
Other properties.
For any formula_2 and formula_1:
where formula_94 is the mutual information between formula_2 and formula_1.
For independent formula_2 and formula_1:
Although the specific-conditional entropy formula_101 can be either less or greater than formula_76 for a given random variate formula_103 of formula_1, formula_105 can never exceed formula_76.
Conditional differential entropy.
Definition.
The above definition is for discrete random variables. The continuous version of discrete conditional entropy is called "conditional differential (or continuous) entropy". Let formula_2 and formula_1 be a continuous random variables with a joint probability density function formula_109. The differential conditional entropy formula_110 is defined as
Properties.
In contrast to the conditional entropy for discrete random variables, the conditional differential entropy may be negative.
As in the discrete case there is a chain rule for differential entropy:
Notice however that this rule may not be true if the involved differential entropies do not exist or are infinite.
Joint differential entropy is also used in the definition of the mutual information between continuous random variables:
formula_113 with equality if and only if formula_2 and formula_1 are independent.
Relation to estimator error.
The conditional differential entropy yields a lower bound on the expected squared error of an estimator. For any random variable formula_2, observation formula_1 and estimator formula_118 the following holds:
This is related to the uncertainty principle from quantum mechanics.
Generalization to quantum theory.
In quantum information theory, the conditional entropy is generalized to the conditional quantum entropy. The latter can take negative values, unlike its classical counterpart.