Databases Reference
In-Depth Information
and
M
−
1
H
(
Y
)
=−
P
(
y
j
)
log
2
P
(
y
j
)
j
=
0
A measure of the relationship between two random variables is the
conditional entropy
(the average value of the conditional self-information). Recall that the self-information for an
event
A
is defined as
1
i
(
A
)
=
log
)
=−
log
P
(
A
)
P
(
A
In a similar manner, the conditional self-information of an event
A
, given that another event
B
has occurred, can be defined as
1
(
|
)
=
)
=−
(
|
)
i
A
B
log
log
P
A
B
P
(
A
|
B
Suppose
B
is the event “Frazer has not drunk anything in two days,” and
A
is the event
“Frazer is thirsty.” Then
P
(
A
|
B
)
should be close to one, which means that the conditional
self-information
i
would be close to zero. This makes sense from an intuitive point of
view as well. If we know that Frazer has not drunk anything in two days, then the statement that
Frazer is thirsty would not be at all surprising to us and would contain very little information.
As in the case of self-information, we are generally interested in the average value of
the conditional self-information. This average value is called the conditional entropy. The
conditional entropies of the source and reconstruction alphabets are given as
(
A
|
B
)
N
−
1
M
−
1
H
(
X
|
Y
)
=−
P
(
x
i
|
y
j
)
P
(
y
j
)
log
2
P
(
x
i
|
y
j
)
(10)
i
=
0
j
=
0
and
N
−
1
M
−
1
H
(
Y
|
X
)
=−
P
(
y
j
|
x
i
)
P
(
x
i
)
log
2
P
(
y
j
|
x
i
)
(11)
i
=
0
j
=
0
The conditional entropy
H
can be interpreted as the amount of uncertainty remaining
about the random variable
X
, or the source output, given that we know what value the recon-
struction
Y
took. The additional knowledge of
Y
should reduce the uncertainty about
X
, and
we can show that
(
X
|
Y
)
(
|
)
(
)
(12)
H
X
Y
H
X
(see Problem 5 at the end of this chapter).
Example8.4.2:
Suppose we have the 4-bits-per-symbol source and compression scheme described in
Example 8.4.1. Assume that the source is equally likely to select any letter from its alphabet.
Let us calculate the various entropies for this source and compression scheme.
