PROBLEMS 67
3.9 AEP.LetX
1
,X
2
,... be independent, identically distributed ran-
dom variables drawn according to the probability mass function
p(x), x ∈{1, 2,...,m}. Thus, p(x
1
,x
2
,...,x
n
) =
n
i=1
p(x
i
).We
know that −
1
n
log p(X
1
,X
2
,...,X
n
) → H(X) in probability. Let
q(x
1
,x
2
,...,x
n
) =
n
i=1
q(x
i
), where q is another probability
mass function on {1, 2,...,m}.
(a) Evaluate lim −
1
n
log q(X
1
,X
2
,...,X
n
),whereX
1
,X
2
,... are
i.i.d. ∼ p(x).
(b) Now evaluate the limit of the log likelihood ratio
1
n
log
q(X
1
,...,X
n
)
p(X
1
,...,X
n
)
when X
1
,X
2
,... are i.i.d. ∼ p(x). Thus, the
odds favoring q are exponentially small when p is true.
3.10 Random box size.
An n-dimensional rectangular box with sides X
1
,X
2
,X
3
,...,X
n
is
to be constructed. The volume is V
n
=
n
i=1
X
i
. The edge length l
of a n-cube with the same volume as the random box is l = V
1/n
n
.
Let X
1
,X
2
,... be i.i.d. uniform random variables over the unit
interval [0, 1]. Find lim
n→∞
V
1/n
n
and compare to (EV
n
)
1
n
. Clearly,
the expected edge length does not capture the idea of the volume
of the box. The geometric mean, rather than the arithmetic mean,
characterizes the behavior of products.
3.11 Proof of Theorem 3.3.1. This problem shows that the size of the
smallest “probable” set is about 2
nH
.LetX
1
,X
2
,...,X
n
be i.i.d.
∼ p(x).LetB
(n)
δ
⊂ X
n
such that Pr(B
(n)
δ
)>1 −δ.Fix<
1
2
.
(a) Given any two sets A, B such that Pr(A) > 1 −
1
and Pr(B) >
1 −
2
, show that Pr(A ∩ B) > 1 −
1
−
2
. Hence, Pr(A
(n)
∩
B
(n)
δ
) ≥ 1 − − δ.
(b) Justify the steps in the chain of inequalities
1 − − δ ≤ Pr(A
(n)
∩ B
(n)
δ
) (3.34)
=
A
(n)
∩B
(n)
δ
p(x
n
) (3.35)
≤
A
(n)
∩B
(n)
δ
2
−n(H −)
(3.36)
=|A
(n)
∩ B
(n)
δ
|2
−n(H −)
(3.37)
≤|B
(n)
δ
|2
−n(H −)
. (3.38)
(c) Complete the proof of the theorem.