Cryptography Reference
In-Depth Information
n
=
H
(
X
i
|
X
1
···
X
i−
1
)
.
i
=1
Note that the order in which variables are extracted is arbitrary. For example,
if we have 3 random variables
X
,
Y
,and
Z
, we can compute their joint entropy as
follows:
H
(
XY Z
)=
H
(
X
)+
H
(
Y
|
X
)+
H
(
Z
|
XY
)
=
H
(
X
)+
H
(
Z
|
X
)+
H
(
Y
|
XZ
)
=
H
(
Y
)+
H
(
X
|
Y
)+
H
(
Z
|
XY
)
=
H
(
Y
)+
H
(
Z
|
Y
)+
H
(
X
|
YZ
)
H
(
Z
)+
H
(
X
|
Z
)+
H
(
Y
|
XZ
)
=
H
(
Z
)+
H
(
Y
|
Z
)+
H
(
X
|
YZ
)
=
Similarly, we can compute the joint entropy of
X
1
···
X
n
given
Y
as follows:
H
(
X
1
···
X
n
|
Y
)=
H
(
X
1
|
Y
)+
H
(
X
2
|
X
1
Y
)+
...
+
H
(
X
n
|
X
1
···
X
n−
1
Y
)
n
=
H
(
X
i
|
X
1
···
X
i−
1
Y
)
i
=1
5.2.3
Mutual Information
The
mutual information
I
(
X
;
Y
) between two random variables
X
and
Y
is defined
as the amount of information by which the entropy (uncertainty) of
X
is reduced by
learning
Y
. This can be formally expressed as follows:
I
(
X
;
Y
)=
H
(
X
)
−
H
(
X
|
Y
)
The mutual information is symmetric in the sense that
I
(
X
;
Y
)=
H
(
X
)
−
H
(
X
X
)=
I
(
Y
;
X
).
The conditional mutual information between
X
and
Y
, given the random
variable
Z
,isdefinedasfollows:
|
Y
)=
H
(
Y
)
−
H
(
Y
|
I
(
X
;
Y
|
Z
)=
H
(
X
|
Z
)
−
H
(
X
|
YZ
)