Thomas M. Cover, Joy A. Thomas. Elements of information theory
Подождите немного. Документ загружается.
16.8 SHANNON–MCMILLAN–BREIMAN THEOREM (GENERAL AEP) 645
We define the kth-order entropy H
k
as
H
k
= E
{
−log p(X
k
|X
k−1
,X
k−2
,...,X
0
)
}
(16.174)
= E
{
−log p(X
0
|X
−1
,X
−2
,...,X
−k
)
}
, (16.175)
where the last equation follows from stationarity. Recall that the entropy
rate is given by
H = lim
k→∞
H
k
(16.176)
= lim
n→∞
1
n
n−1
k=0
H
k
. (16.177)
Of course, H
k
H by stationarity and the fact that conditioning does
not increase entropy. It will be crucial that H
k
H = H
∞
,where
H
∞
= E
{
−log p(X
0
|X
−1
,X
−2
,...)
}
. (16.178)
The proof that H
∞
= H involves exchanging expectation and limit.
The main idea in the proof goes back to the idea of (conditional) propor-
tional gambling. A gambler receiving uniform odds with the knowledge of
the k past will have a growth rate of wealth log |
X|−H
k
, while a gambler
with a knowledge of the infinite past will have a growth rate of wealth
of log |
X|−H
∞
. We don’t know the wealth growth rate of a gambler
with growing knowledge of the past X
n
0
, but it is certainly sandwiched
between log |
X|−H
k
and log |X|−H
∞
.ButH
k
H = H
∞
. Thus, the
sandwich closes and the growth rate must be log |
X|−H .
We will prove the theorem based on lemmas that will follow the proof.
Theorem 16.8.1 (AEP: Shannon–McMillan–Breiman Theorem) If
H is the entropy rate of a finite-valued stationary ergodic process {X
n
},
then
−
1
n
log p(X
0
,...,X
n−1
) → H with probability 1. (16.179)
Proof: We prove this for finite alphabet
X; this proof and the proof for
countable alphabets and densities is given in Algoet and Cover [20]. We
argue that the sequence of random variables −
1
n
log p(X
n−1
0
) is asymptot-
ically sandwiched between the upper bound H
k
and the lower bound H
∞
for all k ≥ 0. The AEP will follow since H
k
→ H
∞
and H
∞
= H .The
kth-order Markov approximation to the probability is defined for n ≥ k as
p
k
(X
n−1
0
) = p(X
k−1
0
)
n−1
i=k
p(X
i
|X
i−1
i−k
). (16.180)
646 INFORMATION THEORY AND PORTFOLIO THEORY
From Lemma 16.8.3 we have
lim sup
n→∞
1
n
log
p
k
(X
n−1
0
)
p(X
n−1
0
)
≤ 0, (16.181)
which we rewrite, taking the existence of the limit
1
n
log p
k
(X
n
0
) into
account (Lemma 16.8.1), as
lim sup
n→∞
1
n
log
1
p(X
n−1
0
)
≤ lim
n→∞
1
n
log
1
p
k
(X
n−1
0
)
= H
k
(16.182)
for k = 1, 2,... . Also, from Lemma 16.8.3, we have
lim sup
n→∞
1
n
log
p(X
n−1
0
)
p(X
n−1
0
|X
−1
−∞
)
≤ 0, (16.183)
which we rewrite as
lim inf
1
n
log
1
p(X
n−1
0
)
≥ lim
1
n
log
1
p(X
n−1
0
|X
−1
−∞
)
= H
∞
(16.184)
from the definition of H
∞
in Lemma 16.8.1.
Putting together (16.182) and (16.184), we have
H
∞
≤ lim inf −
1
n
log p(X
n−1
0
) ≤ lim sup −
1
n
log p(X
n−1
0
)
≤ H
k
for all k. (16.185)
But by Lemma 16.8.2, H
k
→ H
∞
= H . Consequently,
lim −
1
n
log p(X
n
0
) = H. (16.186)
We now prove the lemmas that were used in the main proof. The first
lemma uses the ergodic theorem.
Lemma 16.8.1 (Markov approximations) For a stationary ergodic
stochastic process {X
n
},
−
1
n
log p
k
(X
n−1
0
) → H
k
with probability 1, (16.187)
−
1
n
log p(X
n−1
0
|X
−1
−∞
) → H
∞
with probability 1. (16.188)
16.8 SHANNON–MCMILLAN–BREIMAN THEOREM (GENERAL AEP) 647
Proof: Functions Y
n
= f(X
n
−∞
) of ergodic processes {X
i
} are ergodic
processes. Thus, log p(X
n
|X
n−1
n−k
) and log p(X
n
|X
n−1
,X
n−2
,...,)are also
ergodic processes, and
−
1
n
log p
k
(X
n−1
0
) =−
1
n
log p(X
k−1
0
) −
1
n
n−1
i=k
log p(X
i
|X
i−1
i−k
) (16.189)
→ 0 +H
k
with probability 1, (16.190)
by the ergodic theorem. Similarly, by the ergodic theorem,
−
1
n
log p(X
n−1
0
|X
−1
,X
−2
,...) =−
1
n
n−1
i=0
log p(X
i
|X
i−1
,X
i−2
,...)
(16.191)
→ H
∞
with probability 1. (16.192)
Lemma 16.8.2 (No gap) H
k
H
∞
and H = H
∞
.
Proof: We know that for stationary processes, H
k
H , so it remains
to show that H
k
H
∞
, thus yielding H = H
∞
. Levy’s martingale
convergence theorem for conditional probabilities asserts that
p(x
0
|X
−1
−k
) → p(x
0
|X
−1
−∞
) with probability 1 (16.193)
for all x
0
∈ X.SinceX is finite and p log p is bounded and continuous in
p for all 0 ≤ p ≤ 1, the bounded convergence theorem allows interchange
of expectation and limit, yielding
lim
k→∞
H
k
= lim
k→∞
E
−
x
0
∈X
p(x
0
|X
−1
−k
) log p(x
0
|X
−1
−k
)
(16.194)
= E
−
x
0
∈X
p(x
0
|X
−1
−∞
) log p(x
0
|X
−1
−∞
)
(16.195)
= H
∞
. (16.196)
Thus, H
k
H = H
∞
.
648 INFORMATION THEORY AND PORTFOLIO THEORY
Lemma 16.8.3 (Sandwich)
lim sup
n→∞
1
n
log
p
k
(X
n−1
0
)
p(X
n−1
0
)
≤ 0, (16.197)
lim sup
1
n
log
p(X
n−1
0
)
p(X
n−1
0
|X
−1
−∞
)
≤ 0. (16.198)
Proof: Let A be the support set of p(X
n−1
0
).Then
E
p
k
(X
n−1
0
)
p(X
n−1
0
)
=
x
n−1
0
∈A
p(x
n−1
0
)
p
k
(x
n−1
0
)
p(x
n−1
0
)
(16.199)
=
x
n−1
0
∈A
p
k
(x
n−1
0
) (16.200)
= p
k
(A) (16.201)
≤ 1. (16.202)
Similarly, let B(X
−1
−∞
) denote the support set of p(·|X
−1
−∞
).Thenwehave
E
p(X
n−1
0
)
p(X
n−1
0
|X
−1
−∞
)
= E
E
p(X
n−1
0
)
p(X
n−1
0
|X
−1
−∞
)
X
−1
−∞
(16.203)
= E
x
n
∈B(X
−1
−∞
)
p(x
n
)
p(x
n
|X
−1
−∞
)
p(x
n
|X
−1
−∞
)
(16.204)
= E
x
n
∈B(X
−1
−∞
)
p(x
n
)
(16.205)
≤ 1. (16.206)
By Markov’s inequality and (16.202), we have
Pr
p
k
(X
n−1
0
)
p(X
n−1
0
)
≥ t
n
≤
1
t
n
(16.207)
SUMMARY 649
or
Pr
1
n
log
p
k
(X
n−1
0
)
p(X
n−1
0
)
≥
1
n
log t
n
≤
1
t
n
. (16.208)
Letting t
n
= n
2
and noting that
∞
n=1
1
n
2
< ∞,weseebythe
Borel–Cantelli lemma that the event
1
n
log
p
k
(X
n−1
0
)
p(X
n−1
0
)
≥
1
n
log t
n
(16.209)
occurs only finitely often with probability 1. Thus,
lim sup
1
n
log
p
k
(X
n−1
0
)
p(X
n−1
0
)
≤ 0 with probability 1. (16.210)
Applying the same arguments using Markov’s inequality to (16.206), we
obtain
lim sup
1
n
log
p(X
n−1
0
)
p(X
n−1
0
|X
−1
−∞
)
≤ 0 with probability 1, (16.211)
proving the lemma.
The arguments used in the proof can be extended to prove the AEP for
the stock market (Theorem 16.5.3).
SUMMARY
Growth rate. The growth rate of a stock market portfolio b with
respect to a distribution F(x) is defined as
W(b,F)=
log b
t
x dF(x) = E
log b
t
x
. (16.212)
Log-optimal portfolio. The optimal growth rate with respect to a dis-
tribution F(x) is
W
∗
(F ) = max
b
W(b,F). (16.213)
650 INFORMATION THEORY AND PORTFOLIO THEORY
The portfolio b
∗
that achieves the maximum of W(b,F) is called the
log-optimal portfolio.
Concavity. W(b,F)is concave in b and linear in F . W
∗
(F ) is convex
in F .
Optimality conditions. The portfolio b
∗
is log-optimal if and only if
E
X
i
b
∗t
X
= 1ifb
∗
i
> 0,
≤ 1ifb
∗
i
= 0. (16.214)
Expected ratio optimality. If S
∗
n
=
n
i=1
b
∗t
X
i
, S
n
=
n
i=1
b
t
i
X
i
,then
E
S
n
S
∗
n
≤ 1 if and only if E ln
S
n
S
∗
n
≤ 0. (16.215)
Growth rate (AEP)
1
n
log S
∗
n
→ W
∗
(F ) with probability 1. (16.216)
Asymptotic optimality
lim sup
n→∞
1
n
log
S
n
S
∗
n
≤ 0 with probability 1. (16.217)
Wrong information. Believing g when f is true loses
W = W(b
∗
f
,F)− W(b
∗
g
,F) ≤ D(f ||g). (16.218)
Side information Y
W ≤ I(X;Y). (16.219)
Chain rule
W
∗
(X
i
|X
1
, X
2
,...,X
i−1
) = max
b
i
(x
1
,x
2
,...,x
i−1
)
E log b
t
i
X
i
(16.220)
W
∗
(X
1
, X
2
,...,X
n
) =
n
i=1
W
∗
(X
i
|X
1
, X
2
,...,X
i−1
). (16.221)
SUMMARY 651
Growth rate for a stationary market.
W
∗
∞
= lim
W
∗
(X
1
, X
2
,...,X
n
)
n
(16.222)
1
n
log S
∗
n
→ W
∗
∞
. (16.223)
Competitive optimality of log-optimal portfolios.
Pr(V S ≥ U
∗
S
∗
) ≤
1
2
. (16.224)
Universal portfolio.
max
ˆ
b
i
(·)
min
x
n
,b
n
i=1
ˆ
b
t
i
(x
i−1
)x
i
n
i=1
b
t
x
i
= V
n
, (16.225)
where
V
n
=
n
1
+···+n
m
=n
n
n
1
,n
2
,...,n
m
2
−nH (n
1
/n,...,n
m
/n)
−1
. (16.226)
For m = 2,
V
n
∼
$
2/πn (16.227)
The causal universal portfolio
ˆ
b
i+1
(x
i
) =
bS
i
(b, x
i
)dµ(b)
S
i
(b, x
i
)dµ(b)
(16.228)
achieves
ˆ
S
n
(x
n
)
S
∗
n
(x
n
)
≥
1
2
√
n + 1
(16.229)
for all n and all x
n
.
AEP. If {X
i
} is stationary ergodic, then
−
1
n
log p(X
1
,X
2
,...,X
n
) → H(X) with probability 1. (16.230)
652 INFORMATION THEORY AND PORTFOLIO THEORY
PROBLEMS
16.1 Growth rate.Let
X =
(1,a) with probability
1
2
(1, 1/a) with probability
1
2
where a>1. This vector X represents a stock market vector of
cash vs. a hot stock. Let
W(b,F)= E log b
t
X
and
W
∗
= max
b
W(b,F)
be the growth rate.
(a) Find the log optimal portfolio b
∗
.
(b) Find the growth rate W
∗
.
(c) Find the asymptotic behavior of
S
n
=
n
i=1
b
t
X
i
for all b.
16.2 Side information. Suppose, in Problem 16.1, that
Y =
1if(X
1
,X
2
) ≥ (1, 1),
0if(X
1
,X
2
) ≤ (1, 1).
Let the portfolio b depend on Y . Find the new growth rate W
∗∗
and verify that W = W
∗∗
− W
∗
satisfies
W ≤ I(X;Y).
16.3 Stock dominance. Consider a stock market vector
X = (X
1
,X
2
).
Suppose that X
1
= 2 with probability 1. Thus an investment in
the first stock is doubled at the end of the day.
PROBLEMS 653
(a) Find necessary and sufficient conditions on the distribution of
stock X
2
such that the log-optimal portfolio b
∗
invests all the
wealth in stock X
2
[i.e., b
∗
= (0, 1)].
(b) Argue for any distribution on X
2
that the growth rate satisfies
W
∗
≥ 1.
16.4 Including experts and mutual funds.LetX ∼ F(x), x ∈
R
m
+
,be
the vector of price relatives for a stock market. Suppose that an
“expert” suggests a portfolio b. This would result in a wealth
factor b
t
X. We add this to the stock alternatives to form
˜
X =
(X
1
,X
2
,...,X
m
, b
t
X). Show that the new growth rate,
˜
W
∗
= max
b
1
,...,b
m
,b
m+1
ln(b
t
˜
x)dF(
˜
x), (16.231)
is equal to the old growth rate,
W
∗
= max
b
1
,...,b
m
ln(b
t
x)dF(x). (16.232)
16.5 Growth rate for symmetric distribution. Consider a stock vec-
tor X ∼ F(x), X ∈
R
m
, X ≥ 0, where the component stocks
are exchangeable. Thus, F(x
1
,x
2
,...,x
m
) = F(x
σ(1)
,x
σ(2)
,...,
x
σ(m)
) for all permutations σ .
(a) Find the portfolio b
∗
optimizing the growth rate and establish
its optimality. Now assume that X has been normalized so
that
1
m
m
i=1
X
i
= 1, and F is symmetric as before.
(b) Again assuming X to be normalized, show that all symmetric
distributions F havethesamegrowthrateagainstb
∗
.
(c) Find this growth rate.
16.6 Convexity. We are interested in the set of stock market densities
that yield the same optimal porfolio. Let P
b
0
be the set of all
probability densities on
R
m
+
for which b
0
is optimal. Thus, P
b
0
=
{p(x) :
ln(b
t
x)p(x) dx is maximized by b = b
0
}. Show that P
b
0
is a convex set. It may be helpful to use Theorem 16.2.2.
16.7 Short selling.Let
X =
(1, 2), p,
(1,
1
2
), 1 − p.
Let B ={(b
1
,b
2
) : b
1
+ b
2
= 1}. Thus, this set of portfolios B
does not include the constraint b
i
≥ 0. (This allows short selling.)
654 INFORMATION THEORY AND PORTFOLIO THEORY
(a) Find the log optimal portfolio b
∗
(p).
(b) Relate the growth rate W
∗
(p) to the entropy rate H(p).
16.8 Normalizing x. Suppose that we define the log-optimal portfolio
b
∗
to be the portfolio maximizing the relative growth rate
ln
b
t
x
1
m
m
i=1
x
i
dF(x
1
,...,x
m
).
The virtue of the normalization
1
m
X
i
, which can be viewed as
the wealth associated with a uniform portfolio, is that the relative
growth rate is finite even when the growth rate
ln b
t
xdF(x)
is not. This matters, for example, if X has a St. Petersburg-like
distribution. Thus, the log-optimal portfolio b
∗
is defined for all
distributions F , even those with infinite growth rates W
∗
(F ).
(a) Show that if b maximizes
ln(b
t
x)dF(x), it also maximizes
ln
b
t
x
u
t
x
dF(x),whereu = (
1
m
,
1
m
,...,
1
m
).
(b) Find the log optimal portfolio b
∗
for
X =
(2
2
k
+1
, 2
2
k
), 2
−(k+1)
,
(2
2
k
, 2
2
k
+1
), 2
−(k+1)
,
where k = 1, 2,....
(c) Find EX and W
∗
.
(d) Argue that b
∗
is competitively better than any portfolio b in
the sense that Pr{b
t
X >cb
∗t
X}≤
1
c
.
16.9 Universal portfolio. We examine the first n = 2 steps of the
implementation of the universal portfolio in (16.7.2) for µ(b) uni-
form for m = 2 stocks. Let the stock vectors for days 1 and 2 be
x
1
= (1,
1
2
),andx
2
= (1, 2). Let b = (b, 1 − b) denote a portfo-
lio.
(a) Graph S
2
(b) =
2
i=1
b
t
x
i
, 0 ≤ b ≤ 1.
(b) Calculate S
∗
2
= max
b
S
2
(b).
(c) Argue that log S
2
(b) is concave in b.
(d) Calculate the (universal) wealth
ˆ
S
2
=
1
0
S
2
(b)db.
(e) Calculate the universal portfolio at times n = 1andn = 2:
ˆ
b
1
=
1
0
b db