Databases Reference
In-Depth Information
Theory
, by R.M. Gray [118]; and
Elements of Information Theory
, by T.M. Cover and
J.A. Thomas [38].
5.
Kolmogorov complexity is addressed in detail in
An Introduction to Kolmogorov Com-
plexity and Its Applications,
by M. Li and P. Vitanyi [
12
].
6.
A very readable overview of Kolmogorov complexity in the context of lossless compres-
sion can be found in the chapter “Complexity Measures,” by S.R. Tate, in the
Lossless
Compression Handbook
[
13
].
7.
Various aspects of the minimum description length principle are discussed in
Advances
in Minimum Description Length
edited by P. Grunwald, I.J. Myung, and M.A. Pitt [
14
].
Included in this topic is a very nice introduction to the minimum description length
principle by Peter Grunwald [
15
].
2.8 Projects and Problems
1.
Suppose
X
is a random variable that takes on values from an
M
-letter alphabet. Show
that 0
log
2
M
.
2.
Show that for the case where the elements of an observed sequence are
iid
, the entropy
is equal to the first-order entropy.
3.
Given an alphabet
H
(
X
)
A
={
a
1
,
a
2
,
a
3
,
a
4
}
, find the first-order entropy in the following cases:
1
4
(a)
P
(
a
1
)
=
P
(
a
2
)
=
P
(
a
3
)
=
P
(
a
4
)
=
1
1
1
8
(b)
P
(
a
1
)
=
2
,
P
(
a
2
)
=
4
,
P
(
a
3
)
=
P
(
a
4
)
=
1
1
(c)
P
(
a
1
)
=
0
.
505
,
P
(
a
2
)
=
4
,
P
(
a
3
)
=
8
, and
P
(
a
4
)
=
0
.
12
4.
Suppose we have a source with a probability model
P
={
p
0
,
p
1
,...,
p
m
}
and entropy
H
P
. Suppose we have another source with probability model
Q
={
q
0
,
q
1
,...,
q
m
}
and
entropy
H
Q
, where
=
=
,
,...,
−
,
+
,...,
q
i
p
i
i
0
1
j
2
j
1
m
and
p
j
+
p
j
−
1
q
j
=
q
j
−
1
=
2
How is
H
Q
related to
H
P
(greater, equal, or less)? Prove your answer.
5.
Consider the following sequence:
ATGCTTAAGCTGCTTAACCTGAAGCTTCCGCTGAAGAACCTG
CTGAACCCGCTTAAGCTGAACCTTCTGAAGCTTAACCTGCTT
(a)
Estimating the probabilities from the sequence, compute the first-, second-, third-,
and fourth-order entropy for this sequence.
(b)
Based on these entropies, can you infer how this sequence is structured?
6.
There are several image and speech files among the accompanying data sets.
