downloaded from
Scholarfriends
SOLUTIONS MANUAL for Elements of Information Theory
2nd Edition by Thomas M. Cover, Joy A. Thomas
https://scholarfriends.com
Downloaded by: | https://scholarfriends.com/singlePaper/638936/solutions-manual-for-elements-of-
information-theory-2nd-edition-by-thomas-m-cover-joy-a-thomas
Distribution of this document is illegal.
,SOLUTIONS
MANUAL
Downloaded from Scholarfriends.com
,Elements of Information Theory
Second Edition
Solutions to Problems
Thomas M. Cover
Joy A. Thomas
October 17, 2006
Downloaded from Scholarfriends.com
,Contents
1 Introduction 7
2 Entropy, Relative Entropy and Mutual Information 9
3 The Asymptotic Equipartition Property 49
4 Entropy Rates of a Stochastic Process 61
5 Data Compression 97
6 Gambling and Data Compression 139
7 Channel Capacity 163
8 Differential Entropy 203
9 Gaussian channel 217
10 Rate Distortion Theory 241
11 Information Theory and Statistics 273
12 Maximum Entropy 301
13 Universal Source Coding 309
14 Kolmogorov Complexity 321
15 Network Information Theory 331
16 Information Theory and Portfolio Theory 377
17 Inequalities in Information Theory 391
3
Downloaded from Scholarfriends.com
,Chapter 2
Entropy, Relative Entropy and
Mutual Information
1. Coin flips. A fair coin is flipped until the first head occurs. Let X denote the number
of flips required.
(a) Find the entropy H(X) in bits. The following expressions may be useful:
∞ ∞
X
n 1 X r
r = , nr n = .
n=0
1−r n=0
(1 − r)2
(b) A random variable X is drawn according to this distribution. Find an “efficient”
sequence of yes-no questions of the form, “Is X contained in the set S ?” Compare
H(X) to the expected number of questions required to determine X .
Solution:
(a) The number X of tosses till the first head appears has the geometric distribution
with parameter p = 1/2 , where P (X = n) = pq n−1 , n ∈ {1, 2, . . .} . Hence the
entropy of X is
∞
X
H(X) = − pq n−1 log(pq n−1 )
n=1
"∞ ∞
#
X X
n n
= − pq log p + npq log q
n=0 n=0
−p log p pq log q
= −
1−q p2
−p log p − q log q
=
p
= H(p)/p bits.
If p = 1/2 , then H(X) = 2 bits.
9
Downloaded from Scholarfriends.com
,10 Entropy, Relative Entropy and Mutual Information
(b) Intuitively, it seems clear that the best questions are those that have equally likely
chances of receiving a yes or a no answer. Consequently, one possible guess is
that the most “efficient” series of questions is: Is X = 1 ? If not, is X = 2 ?
If not, is X = 3 ? . . . with a resulting expected number of questions equal to
P∞ n
n=1 n(1/2 ) = 2. This should reinforce the intuition that H(X) is a mea-
sure of the uncertainty of X . Indeed in this case, the entropy is exactly the
same as the average number of questions needed to define X , and in general
E(# of questions) ≥ H(X) . This problem has an interpretation as a source cod-
ing problem. Let 0 = no, 1 = yes, X = Source, and Y = Encoded Source. Then
the set of questions in the above procedure can be written as a collection of (X, Y )
pairs: (1, 1) , (2, 01) , (3, 001) , etc. . In fact, this intuitively derived code is the
optimal (Huffman) code minimizing the expected number of questions.
2. Entropy of functions. Let X be a random variable taking on a finite number of
values. What is the (general) inequality relationship of H(X) and H(Y ) if
(a) Y = 2X ?
(b) Y = cos X ?
Solution: Let y = g(x) . Then
X
p(y) = p(x).
x: y=g(x)
Consider any set of x ’s that map onto a single y . For this set
X X
p(x) log p(x) ≤ p(x) log p(y) = p(y) log p(y),
x: y=g(x) x: y=g(x)
P
since log is a monotone increasing function and p(x) ≤ x: y=g(x) p(x) = p(y) . Ex-
tending this argument to the entire range of X (and Y ), we obtain
X
H(X) = − p(x) log p(x)
x
X X
= − p(x) log p(x)
y x: y=g(x)
X
≥ − p(y) log p(y)
y
= H(Y ),
with equality iff g is one-to-one with probability one.
(a) Y = 2X is one-to-one and hence the entropy, which is just a function of the
probabilities (and not the values of a random variable) does not change, i.e.,
H(X) = H(Y ) .
(b) Y = cos(X) is not necessarily one-to-one. Hence all that we can say is that
H(X) ≥ H(Y ) , with equality if cosine is one-to-one on the range of X .
Downloaded from Scholarfriends.com
,Entropy, Relative Entropy and Mutual Information 11
3. Minimum entropy. What is the minimum value of H(p 1 , ..., pn ) = H(p) as p ranges
over the set of n -dimensional probability vectors? Find all p ’s which achieve this
minimum.
Solution: We wish to find all probability vectors p = (p 1 , p2 , . . . , pn ) which minimize
X
H(p) = − pi log pi .
i
Now −pi log pi ≥ 0 , with equality iff pi = 0 or 1 . Hence the only possible probability
vectors which minimize H(p) are those with p i = 1 for some i and pj = 0, j 6= i .
There are n such vectors, i.e., (1, 0, . . . , 0) , (0, 1, 0, . . . , 0) , . . . , (0, . . . , 0, 1) , and the
minimum value of H(p) is 0.
4. Entropy of functions of a random variable. Let X be a discrete random variable.
Show that the entropy of a function of X is less than or equal to the entropy of X by
justifying the following steps:
(a)
H(X, g(X)) = H(X) + H(g(X) | X) (2.1)
(b)
= H(X); (2.2)
(c)
H(X, g(X)) = H(g(X)) + H(X | g(X)) (2.3)
(d)
≥ H(g(X)). (2.4)
Thus H(g(X)) ≤ H(X).
Solution: Entropy of functions of a random variable.
(a) H(X, g(X)) = H(X) + H(g(X)|X) by the chain rule for entropies.
(b) H(g(X)|X) = 0 since for any particular value of X, g(X) is fixed, and hence
P P
H(g(X)|X) = x p(x)H(g(X)|X = x) = x 0 = 0 .
(c) H(X, g(X)) = H(g(X)) + H(X|g(X)) again by the chain rule.
(d) H(X|g(X)) ≥ 0 , with equality iff X is a function of g(X) , i.e., g(.) is one-to-one.
Hence H(X, g(X)) ≥ H(g(X)) .
Combining parts (b) and (d), we obtain H(X) ≥ H(g(X)) .
5. Zero conditional entropy. Show that if H(Y |X) = 0 , then Y is a function of X ,
i.e., for all x with p(x) > 0 , there is only one possible value of y with p(x, y) > 0 .
Solution: Zero Conditional Entropy. Assume that there exists an x , say x 0 and two
different values of y , say y1 and y2 such that p(x0 , y1 ) > 0 and p(x0 , y2 ) > 0 . Then
p(x0 ) ≥ p(x0 , y1 ) + p(x0 , y2 ) > 0 , and p(y1 |x0 ) and p(y2 |x0 ) are not equal to 0 or 1.
Thus
X X
H(Y |X) = − p(x) p(y|x) log p(y|x) (2.5)
x y
≥ p(x0 )(−p(y1 |x0 ) log p(y1 |x0 ) − p(y2 |x0 ) log p(y2 |x0 )) (2.6)
> > 0, (2.7)
Downloaded from Scholarfriends.com
,12 Entropy, Relative Entropy and Mutual Information
since −t log t ≥ 0 for 0 ≤ t ≤ 1 , and is strictly positive for t not equal to 0 or 1.
Therefore the conditional entropy H(Y |X) is 0 if and only if Y is a function of X .
6. Conditional mutual information vs. unconditional mutual information. Give
examples of joint random variables X , Y and Z such that
(a) I(X; Y | Z) < I(X; Y ) ,
(b) I(X; Y | Z) > I(X; Y ) .
Solution: Conditional mutual information vs. unconditional mutual information.
(a) The last corollary to Theorem 2.8.1 in the text states that if X → Y → Z that
is, if p(x, y | z) = p(x | z)p(y | z) then, I(X; Y ) ≥ I(X; Y | Z) . Equality holds if
and only if I(X; Z) = 0 or X and Z are independent.
A simple example of random variables satisfying the inequality conditions above
is, X is a fair binary random variable and Y = X and Z = Y . In this case,
I(X; Y ) = H(X) − H(X | Y ) = H(X) = 1
and,
I(X; Y | Z) = H(X | Z) − H(X | Y, Z) = 0.
So that I(X; Y ) > I(X; Y | Z) .
(b) This example is also given in the text. Let X, Y be independent fair binary
random variables and let Z = X + Y . In this case we have that,
I(X; Y ) = 0
and,
I(X; Y | Z) = H(X | Z) = 1/2.
So I(X; Y ) < I(X; Y | Z) . Note that in this case X, Y, Z are not markov.
7. Coin weighing. Suppose one has n coins, among which there may or may not be one
counterfeit coin. If there is a counterfeit coin, it may be either heavier or lighter than
the other coins. The coins are to be weighed by a balance.
(a) Find an upper bound on the number of coins n so that k weighings will find the
counterfeit coin (if any) and correctly declare it to be heavier or lighter.
(b) (Difficult) What is the coin weighing strategy for k = 3 weighings and 12 coins?
Solution: Coin weighing.
(a) For n coins, there are 2n + 1 possible situations or “states”.
• One of the n coins is heavier.
• One of the n coins is lighter.
• They are all of equal weight.
Downloaded from Scholarfriends.com
,Entropy, Relative Entropy and Mutual Information 13
Each weighing has three possible outcomes - equal, left pan heavier or right pan
heavier. Hence with k weighings, there are 3 k possible outcomes and hence we
can distinguish between at most 3k different “states”. Hence 2n + 1 ≤ 3k or
n ≤ (3k − 1)/2 .
Looking at it from an information theoretic viewpoint, each weighing gives at most
log 2 3 bits of information. There are 2n + 1 possible “states”, with a maximum
entropy of log 2 (2n + 1) bits. Hence in this situation, one would require at least
log 2 (2n + 1)/ log 2 3 weighings to extract enough information for determination of
the odd coin, which gives the same result as above.
(b) There are many solutions to this problem. We will give one which is based on the
ternary number system.
We may express the numbers {−12, −11, . . . , −1, 0, 1, . . . , 12} in a ternary number
system with alphabet {−1, 0, 1} . For example, the number 8 is (-1,0,1) where
−1 × 30 + 0 × 31 + 1 × 32 = 8 . We form the matrix with the representation of the
positive numbers as its columns.
1 2 3 4 5 6 7 8 9 10 11 12
3 0 1 -1 0 1 -1 0 1 -1 0 1 -1 0 Σ1 = 0
31 0 1 1 1 -1 -1 -1 0 0 0 1 1 Σ2 = 2
3 2 0 0 0 0 1 1 1 1 1 1 1 1 Σ3 = 8
Note that the row sums are not all zero. We can negate some columns to make
the row sums zero. For example, negating columns 7,9,11 and 12, we obtain
1 2 3 4 5 6 7 8 9 10 11 12
3 0 1 -1 0 1 -1 0 -1 -1 0 1 1 0 Σ1 = 0
31 0 1 1 1 -1 -1 1 0 0 0 -1 -1 Σ2 = 0
32 0 0 0 0 1 1 -1 1 -1 1 -1 -1 Σ3 = 0
Now place the coins on the balance according to the following rule: For weighing
#i , place coin n
• On left pan, if ni = −1 .
• Aside, if ni = 0 .
• On right pan, if ni = 1 .
The outcome of the three weighings will find the odd coin if any and tell whether
it is heavy or light. The result of each weighing is 0 if both pans are equal, -1 if
the left pan is heavier, and 1 if the right pan is heavier. Then the three weighings
give the ternary expansion of the index of the odd coin. If the expansion is the
same as the expansion in the matrix, it indicates that the coin is heavier. If
the expansion is of the opposite sign, the coin is lighter. For example, (0,-1,-1)
indicates (0)30 +(−1)3+(−1)32 = −12 , hence coin #12 is heavy, (1,0,-1) indicates
#8 is light, (0,0,0) indicates no odd coin.
Why does this scheme work? It is a single error correcting Hamming code for the
ternary alphabet (discussed in Section 8.11 in the book). Here are some details.
First note a few properties of the matrix above that was used for the scheme.
All the columns are distinct and no two columns add to (0,0,0). Also if any coin
Downloaded from Scholarfriends.com
, 14 Entropy, Relative Entropy and Mutual Information
is heavier, it will produce the sequence of weighings that matches its column in
the matrix. If it is lighter, it produces the negative of its column as a sequence
of weighings. Combining all these facts, we can see that any single odd coin will
produce a unique sequence of weighings, and that the coin can be determined from
the sequence.
One of the questions that many of you had whether the bound derived in part (a)
was actually achievable. For example, can one distinguish 13 coins in 3 weighings?
No, not with a scheme like the one above. Yes, under the assumptions under
which the bound was derived. The bound did not prohibit the division of coins
into halves, neither did it disallow the existence of another coin known to be
normal. Under both these conditions, it is possible to find the odd coin of 13 coins
in 3 weighings. You could try modifying the above scheme to these cases.
8. Drawing with and without replacement. An urn contains r red, w white, and
b black balls. Which has higher entropy, drawing k ≥ 2 balls from the urn with
replacement or without replacement? Set it up and show why. (There is both a hard
way and a relatively simple way to do this.)
Solution: Drawing with and without replacement. Intuitively, it is clear that if the
balls are drawn with replacement, the number of possible choices for the i -th ball is
larger, and therefore the conditional entropy is larger. But computing the conditional
distributions is slightly involved. It is easier to compute the unconditional entropy.
• With replacement. In this case the conditional distribution of each draw is the
same for every draw. Thus
r
red
with prob. r+w+b
w
Xi = white with prob. r+w+b (2.8)
b
black with prob. r+w+b
and therefore
H(Xi |Xi−1 , . . . , X1 ) = H(Xi ) (2.9)
r w b
= log(r + w + b) − log r − log w − log (2.10)
b.
r+w+b r+w+b r+w+b
• Without replacement. The unconditional probability of the i -th ball being red is
still r/(r + w + b) , etc. Thus the unconditional entropy H(X i ) is still the same as
with replacement. The conditional entropy H(X i |Xi−1 , . . . , X1 ) is less than the
unconditional entropy, and therefore the entropy of drawing without replacement
is lower.
9. A metric. A function ρ(x, y) is a metric if for all x, y ,
• ρ(x, y) ≥ 0
• ρ(x, y) = ρ(y, x)
Downloaded from Scholarfriends.com
Scholarfriends
SOLUTIONS MANUAL for Elements of Information Theory
2nd Edition by Thomas M. Cover, Joy A. Thomas
https://scholarfriends.com
Downloaded by: | https://scholarfriends.com/singlePaper/638936/solutions-manual-for-elements-of-
information-theory-2nd-edition-by-thomas-m-cover-joy-a-thomas
Distribution of this document is illegal.
,SOLUTIONS
MANUAL
Downloaded from Scholarfriends.com
,Elements of Information Theory
Second Edition
Solutions to Problems
Thomas M. Cover
Joy A. Thomas
October 17, 2006
Downloaded from Scholarfriends.com
,Contents
1 Introduction 7
2 Entropy, Relative Entropy and Mutual Information 9
3 The Asymptotic Equipartition Property 49
4 Entropy Rates of a Stochastic Process 61
5 Data Compression 97
6 Gambling and Data Compression 139
7 Channel Capacity 163
8 Differential Entropy 203
9 Gaussian channel 217
10 Rate Distortion Theory 241
11 Information Theory and Statistics 273
12 Maximum Entropy 301
13 Universal Source Coding 309
14 Kolmogorov Complexity 321
15 Network Information Theory 331
16 Information Theory and Portfolio Theory 377
17 Inequalities in Information Theory 391
3
Downloaded from Scholarfriends.com
,Chapter 2
Entropy, Relative Entropy and
Mutual Information
1. Coin flips. A fair coin is flipped until the first head occurs. Let X denote the number
of flips required.
(a) Find the entropy H(X) in bits. The following expressions may be useful:
∞ ∞
X
n 1 X r
r = , nr n = .
n=0
1−r n=0
(1 − r)2
(b) A random variable X is drawn according to this distribution. Find an “efficient”
sequence of yes-no questions of the form, “Is X contained in the set S ?” Compare
H(X) to the expected number of questions required to determine X .
Solution:
(a) The number X of tosses till the first head appears has the geometric distribution
with parameter p = 1/2 , where P (X = n) = pq n−1 , n ∈ {1, 2, . . .} . Hence the
entropy of X is
∞
X
H(X) = − pq n−1 log(pq n−1 )
n=1
"∞ ∞
#
X X
n n
= − pq log p + npq log q
n=0 n=0
−p log p pq log q
= −
1−q p2
−p log p − q log q
=
p
= H(p)/p bits.
If p = 1/2 , then H(X) = 2 bits.
9
Downloaded from Scholarfriends.com
,10 Entropy, Relative Entropy and Mutual Information
(b) Intuitively, it seems clear that the best questions are those that have equally likely
chances of receiving a yes or a no answer. Consequently, one possible guess is
that the most “efficient” series of questions is: Is X = 1 ? If not, is X = 2 ?
If not, is X = 3 ? . . . with a resulting expected number of questions equal to
P∞ n
n=1 n(1/2 ) = 2. This should reinforce the intuition that H(X) is a mea-
sure of the uncertainty of X . Indeed in this case, the entropy is exactly the
same as the average number of questions needed to define X , and in general
E(# of questions) ≥ H(X) . This problem has an interpretation as a source cod-
ing problem. Let 0 = no, 1 = yes, X = Source, and Y = Encoded Source. Then
the set of questions in the above procedure can be written as a collection of (X, Y )
pairs: (1, 1) , (2, 01) , (3, 001) , etc. . In fact, this intuitively derived code is the
optimal (Huffman) code minimizing the expected number of questions.
2. Entropy of functions. Let X be a random variable taking on a finite number of
values. What is the (general) inequality relationship of H(X) and H(Y ) if
(a) Y = 2X ?
(b) Y = cos X ?
Solution: Let y = g(x) . Then
X
p(y) = p(x).
x: y=g(x)
Consider any set of x ’s that map onto a single y . For this set
X X
p(x) log p(x) ≤ p(x) log p(y) = p(y) log p(y),
x: y=g(x) x: y=g(x)
P
since log is a monotone increasing function and p(x) ≤ x: y=g(x) p(x) = p(y) . Ex-
tending this argument to the entire range of X (and Y ), we obtain
X
H(X) = − p(x) log p(x)
x
X X
= − p(x) log p(x)
y x: y=g(x)
X
≥ − p(y) log p(y)
y
= H(Y ),
with equality iff g is one-to-one with probability one.
(a) Y = 2X is one-to-one and hence the entropy, which is just a function of the
probabilities (and not the values of a random variable) does not change, i.e.,
H(X) = H(Y ) .
(b) Y = cos(X) is not necessarily one-to-one. Hence all that we can say is that
H(X) ≥ H(Y ) , with equality if cosine is one-to-one on the range of X .
Downloaded from Scholarfriends.com
,Entropy, Relative Entropy and Mutual Information 11
3. Minimum entropy. What is the minimum value of H(p 1 , ..., pn ) = H(p) as p ranges
over the set of n -dimensional probability vectors? Find all p ’s which achieve this
minimum.
Solution: We wish to find all probability vectors p = (p 1 , p2 , . . . , pn ) which minimize
X
H(p) = − pi log pi .
i
Now −pi log pi ≥ 0 , with equality iff pi = 0 or 1 . Hence the only possible probability
vectors which minimize H(p) are those with p i = 1 for some i and pj = 0, j 6= i .
There are n such vectors, i.e., (1, 0, . . . , 0) , (0, 1, 0, . . . , 0) , . . . , (0, . . . , 0, 1) , and the
minimum value of H(p) is 0.
4. Entropy of functions of a random variable. Let X be a discrete random variable.
Show that the entropy of a function of X is less than or equal to the entropy of X by
justifying the following steps:
(a)
H(X, g(X)) = H(X) + H(g(X) | X) (2.1)
(b)
= H(X); (2.2)
(c)
H(X, g(X)) = H(g(X)) + H(X | g(X)) (2.3)
(d)
≥ H(g(X)). (2.4)
Thus H(g(X)) ≤ H(X).
Solution: Entropy of functions of a random variable.
(a) H(X, g(X)) = H(X) + H(g(X)|X) by the chain rule for entropies.
(b) H(g(X)|X) = 0 since for any particular value of X, g(X) is fixed, and hence
P P
H(g(X)|X) = x p(x)H(g(X)|X = x) = x 0 = 0 .
(c) H(X, g(X)) = H(g(X)) + H(X|g(X)) again by the chain rule.
(d) H(X|g(X)) ≥ 0 , with equality iff X is a function of g(X) , i.e., g(.) is one-to-one.
Hence H(X, g(X)) ≥ H(g(X)) .
Combining parts (b) and (d), we obtain H(X) ≥ H(g(X)) .
5. Zero conditional entropy. Show that if H(Y |X) = 0 , then Y is a function of X ,
i.e., for all x with p(x) > 0 , there is only one possible value of y with p(x, y) > 0 .
Solution: Zero Conditional Entropy. Assume that there exists an x , say x 0 and two
different values of y , say y1 and y2 such that p(x0 , y1 ) > 0 and p(x0 , y2 ) > 0 . Then
p(x0 ) ≥ p(x0 , y1 ) + p(x0 , y2 ) > 0 , and p(y1 |x0 ) and p(y2 |x0 ) are not equal to 0 or 1.
Thus
X X
H(Y |X) = − p(x) p(y|x) log p(y|x) (2.5)
x y
≥ p(x0 )(−p(y1 |x0 ) log p(y1 |x0 ) − p(y2 |x0 ) log p(y2 |x0 )) (2.6)
> > 0, (2.7)
Downloaded from Scholarfriends.com
,12 Entropy, Relative Entropy and Mutual Information
since −t log t ≥ 0 for 0 ≤ t ≤ 1 , and is strictly positive for t not equal to 0 or 1.
Therefore the conditional entropy H(Y |X) is 0 if and only if Y is a function of X .
6. Conditional mutual information vs. unconditional mutual information. Give
examples of joint random variables X , Y and Z such that
(a) I(X; Y | Z) < I(X; Y ) ,
(b) I(X; Y | Z) > I(X; Y ) .
Solution: Conditional mutual information vs. unconditional mutual information.
(a) The last corollary to Theorem 2.8.1 in the text states that if X → Y → Z that
is, if p(x, y | z) = p(x | z)p(y | z) then, I(X; Y ) ≥ I(X; Y | Z) . Equality holds if
and only if I(X; Z) = 0 or X and Z are independent.
A simple example of random variables satisfying the inequality conditions above
is, X is a fair binary random variable and Y = X and Z = Y . In this case,
I(X; Y ) = H(X) − H(X | Y ) = H(X) = 1
and,
I(X; Y | Z) = H(X | Z) − H(X | Y, Z) = 0.
So that I(X; Y ) > I(X; Y | Z) .
(b) This example is also given in the text. Let X, Y be independent fair binary
random variables and let Z = X + Y . In this case we have that,
I(X; Y ) = 0
and,
I(X; Y | Z) = H(X | Z) = 1/2.
So I(X; Y ) < I(X; Y | Z) . Note that in this case X, Y, Z are not markov.
7. Coin weighing. Suppose one has n coins, among which there may or may not be one
counterfeit coin. If there is a counterfeit coin, it may be either heavier or lighter than
the other coins. The coins are to be weighed by a balance.
(a) Find an upper bound on the number of coins n so that k weighings will find the
counterfeit coin (if any) and correctly declare it to be heavier or lighter.
(b) (Difficult) What is the coin weighing strategy for k = 3 weighings and 12 coins?
Solution: Coin weighing.
(a) For n coins, there are 2n + 1 possible situations or “states”.
• One of the n coins is heavier.
• One of the n coins is lighter.
• They are all of equal weight.
Downloaded from Scholarfriends.com
,Entropy, Relative Entropy and Mutual Information 13
Each weighing has three possible outcomes - equal, left pan heavier or right pan
heavier. Hence with k weighings, there are 3 k possible outcomes and hence we
can distinguish between at most 3k different “states”. Hence 2n + 1 ≤ 3k or
n ≤ (3k − 1)/2 .
Looking at it from an information theoretic viewpoint, each weighing gives at most
log 2 3 bits of information. There are 2n + 1 possible “states”, with a maximum
entropy of log 2 (2n + 1) bits. Hence in this situation, one would require at least
log 2 (2n + 1)/ log 2 3 weighings to extract enough information for determination of
the odd coin, which gives the same result as above.
(b) There are many solutions to this problem. We will give one which is based on the
ternary number system.
We may express the numbers {−12, −11, . . . , −1, 0, 1, . . . , 12} in a ternary number
system with alphabet {−1, 0, 1} . For example, the number 8 is (-1,0,1) where
−1 × 30 + 0 × 31 + 1 × 32 = 8 . We form the matrix with the representation of the
positive numbers as its columns.
1 2 3 4 5 6 7 8 9 10 11 12
3 0 1 -1 0 1 -1 0 1 -1 0 1 -1 0 Σ1 = 0
31 0 1 1 1 -1 -1 -1 0 0 0 1 1 Σ2 = 2
3 2 0 0 0 0 1 1 1 1 1 1 1 1 Σ3 = 8
Note that the row sums are not all zero. We can negate some columns to make
the row sums zero. For example, negating columns 7,9,11 and 12, we obtain
1 2 3 4 5 6 7 8 9 10 11 12
3 0 1 -1 0 1 -1 0 -1 -1 0 1 1 0 Σ1 = 0
31 0 1 1 1 -1 -1 1 0 0 0 -1 -1 Σ2 = 0
32 0 0 0 0 1 1 -1 1 -1 1 -1 -1 Σ3 = 0
Now place the coins on the balance according to the following rule: For weighing
#i , place coin n
• On left pan, if ni = −1 .
• Aside, if ni = 0 .
• On right pan, if ni = 1 .
The outcome of the three weighings will find the odd coin if any and tell whether
it is heavy or light. The result of each weighing is 0 if both pans are equal, -1 if
the left pan is heavier, and 1 if the right pan is heavier. Then the three weighings
give the ternary expansion of the index of the odd coin. If the expansion is the
same as the expansion in the matrix, it indicates that the coin is heavier. If
the expansion is of the opposite sign, the coin is lighter. For example, (0,-1,-1)
indicates (0)30 +(−1)3+(−1)32 = −12 , hence coin #12 is heavy, (1,0,-1) indicates
#8 is light, (0,0,0) indicates no odd coin.
Why does this scheme work? It is a single error correcting Hamming code for the
ternary alphabet (discussed in Section 8.11 in the book). Here are some details.
First note a few properties of the matrix above that was used for the scheme.
All the columns are distinct and no two columns add to (0,0,0). Also if any coin
Downloaded from Scholarfriends.com
, 14 Entropy, Relative Entropy and Mutual Information
is heavier, it will produce the sequence of weighings that matches its column in
the matrix. If it is lighter, it produces the negative of its column as a sequence
of weighings. Combining all these facts, we can see that any single odd coin will
produce a unique sequence of weighings, and that the coin can be determined from
the sequence.
One of the questions that many of you had whether the bound derived in part (a)
was actually achievable. For example, can one distinguish 13 coins in 3 weighings?
No, not with a scheme like the one above. Yes, under the assumptions under
which the bound was derived. The bound did not prohibit the division of coins
into halves, neither did it disallow the existence of another coin known to be
normal. Under both these conditions, it is possible to find the odd coin of 13 coins
in 3 weighings. You could try modifying the above scheme to these cases.
8. Drawing with and without replacement. An urn contains r red, w white, and
b black balls. Which has higher entropy, drawing k ≥ 2 balls from the urn with
replacement or without replacement? Set it up and show why. (There is both a hard
way and a relatively simple way to do this.)
Solution: Drawing with and without replacement. Intuitively, it is clear that if the
balls are drawn with replacement, the number of possible choices for the i -th ball is
larger, and therefore the conditional entropy is larger. But computing the conditional
distributions is slightly involved. It is easier to compute the unconditional entropy.
• With replacement. In this case the conditional distribution of each draw is the
same for every draw. Thus
r
red
with prob. r+w+b
w
Xi = white with prob. r+w+b (2.8)
b
black with prob. r+w+b
and therefore
H(Xi |Xi−1 , . . . , X1 ) = H(Xi ) (2.9)
r w b
= log(r + w + b) − log r − log w − log (2.10)
b.
r+w+b r+w+b r+w+b
• Without replacement. The unconditional probability of the i -th ball being red is
still r/(r + w + b) , etc. Thus the unconditional entropy H(X i ) is still the same as
with replacement. The conditional entropy H(X i |Xi−1 , . . . , X1 ) is less than the
unconditional entropy, and therefore the entropy of drawing without replacement
is lower.
9. A metric. A function ρ(x, y) is a metric if for all x, y ,
• ρ(x, y) ≥ 0
• ρ(x, y) = ρ(y, x)
Downloaded from Scholarfriends.com
