Joint Entropies
In this module, we'll discuss several extensions of entropy. Let's begin with joint entropy. Suppose we have a random variable
with elements
and random variable
with elements
. We define the joint entropy of
as:
-
![{\displaystyle H(X,Y)=-\sum _{i=1}^{n}\sum _{j=1}^{m}P(x_{i},y_{j})\log _{2}\left(P(x_{i},y_{j})\right)}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/6a0151ef0daf9a72555fc3f9edcb78b5c105c2e5)
|
|
(1)
|
Take note that
. This is trivial. From our previous discussion about the decision trees of a game, we used joint entropies to calculate the overall entropy.
Conditional Entropies
There are two steps to understand conditional entropies. The first is the uncertainty of a random variable caused by a single outcome only. Suppose we have the same random variables
and
defined earlier in joint entropies. Let's denote
as the conditional probability of
when event
happened. We define the entropy
as the entropy of the random variable
given a
happened. Take note that we're only interested in the entropy of
when only the outcome
occurred. Mathematically this is:
-
![{\displaystyle H(Y|x_{i})=-\sum _{j=1}^{m}P(y_{j}|x_{i})\log _{2}\left(P(y_{j}|x_{i})\right)}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/b6a75a395f416f21ed20f68029ad3f13777a9378)
|
|
(2)
|
Just to repeat because it may be confusing, equation 2 just pertains to the uncertainty when only a single event happened. We can extend this to the total entropy
when any of the outcomes in
happens. If we treat
contains a range of
and the probability distribution for each associated
is
so that
is a function of
. Then we define
as the conditional probability of
given
as:
-
![{\displaystyle H(Y|X)=E(H(Y|\cdot ))=-\sum _{j=1}^{m}P(x_{i})H(Y|x_{i})}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/60592d4f11dc773df6f130434dd3b8ef6a25cc70)
|
|
(3)
|
Substituting equation 2 to equation 3 and knowing that
. We can re-write this as:
-
![{\displaystyle H(Y|X)=-\sum _{i=1}^{n}\sum _{j=1}^{m}P(x_{i},y_{j})\log _{2}(P(y_{j}|x_{i}))}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/f7d0cbddaa00a13f1b38844f94fd64b17c8eae5e)
|
|
(3)
|
Note that it is trivial to prove that
if
and
are independent. We'll leave it up to you to prove this. A few hints include:
and
if
and
are independent.
Binary Tree Example
Figure 1: Binary tree example.
Let's apply the first two concepts in a simple binary tree example. Suppose we let
be a random variable with outcomes
and probabilities
. Let
be the random variable with outcomes
. We are also given the probabilities
,
,
, and
. Figure 1 shows the binary tree. Calculate:
(a)
(b)
(c)
(d)
Solution
(a) Use equation 2 to solve
(b) Same as in (a), use equation 2 to solve
(c) Can be solved in two ways. First is to use equation 3.
Or, we can solve it using the alternative version of equation 3. But we also need to know the joint probabilities:
![{\displaystyle P(a,w)={\frac {1}{3}}}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/0399136e47052574f6f31eddf4af2297ae58a291)
![{\displaystyle P(a,x)={\frac {1}{6}}}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/efb97b371da670d54a0ab80ee028ddf18be41ada)
![{\displaystyle P(b,y)={\frac {1}{4}}}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/f898b4cff3b6086b9419cf7043ce06816d4f5881)
![{\displaystyle P(b,z)={\frac {1}{4}}}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/1f7bea47c3380ad162228e58d593b215c48ddb54)
(d) We already listed the joint probabilities in (c). We simply use equation 1 for this:
Important Note!
This example actually shows us an important observation:
-
![{\displaystyle H(X,Y)=H(X)+H(Y|X)}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/a8725690f0c8920b9a29c37b64fb1f2479c5d0b7)
|
|
(4)
|
We can easily observe that this holds true for the binary tree example. This has an important interpretation: The combined uncertainty in
and
(i.e.,
) is the sum of that uncertainty which is totally due to
(i.e.,
), and that which is still due to
once
has been accounted for (i.e.,
).
Since
it also follows that:
-
![{\displaystyle H(Y,X)=H(Y)+H(X|Y)}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/3eadfa2cdd5dab5331504236c299fdd8df4a399f)
|
|
(5)
|
If
and
are independent the:
-
![{\displaystyle H(X,Y)=H(X)+H(Y)}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/41b9cc4a524a355214eafb8883ccde26a88ca9ce)
|
|
(6)
|
An alternative interpretation to
is the information content of
which is NOT contained in
.
Mutual Information
With the final discussion on the properties of joint and conditional entropies, we also define mutual information as the information content of
contained within
written as:
-
![{\displaystyle I(X,Y)=H(Y)-H(Y|X)}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/0b2bd7d56ad5fb2f736c028a1ae0a24c0619e79f)
|
|
(6)
|
Or:
-
![{\displaystyle I(X,Y)=H(X)-H(X|Y)}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/24eb7982f3513e60afcf8f8e1052bd88ee204682)
|
|
(6)
|
If we plug in the definitions of entropy and conditional entropy, mutual information in expanded form is:
-
![{\displaystyle I(X,Y)=\sum _{i=1}^{n}\sum _{j=1}^{m}P(x_{i},y_{j})\log _{2}\left({\frac {P(x_{i},y_{j})}{P(x_{i})P(y_{j})}}\right)}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/610af2564e3a341726205ce6e54b97d8153f4591)
|
|
(7)
|
It also follows that:
. This is trivial from equation 7.
- If
and
are independent, then
. This is also trivial from equation 7.
As a short example, we can use the binary tree problem again. Let's compute
. We simply need to use equation 6:
. We already know
bits.
is computed by first knowing
. Recall that:
But then, for each outcome in
has the same probability of the joint entropy. For example, event
only occurs if event
occurred first. Event
occurs only if event
occurred first. So it means that:
![{\displaystyle P(w)=P(w|a)P(a)=P(w,a)={\frac {1}{3}}}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/f19976dc19c8db235dd03205c78678bbc2060624)
![{\displaystyle P(x)=P(x|a)P(a)=P(x,a)={\frac {1}{6}}}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/a787d8fcb9514a5239ab4d7fb5c6f4ac7180bc8a)
![{\displaystyle P(y)=P(y|b)P(b)=P(y,b)={\frac {1}{4}}}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/b66b083545a055d3b37eafd49d1207502f1efc7f)
![{\displaystyle P(z)=P(z|b)P(b)=P(z,b)={\frac {1}{4}}}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/94ce0480409b6ea7480a195ecae8b4f81224f713)
Therefore,
bits. Therefore, the information
bits.
Graphical Interpretation