Bandit Algorithms

14.4 Bibliographic remarks 185

14.4 Bibliographic remarks

There are many references for information theory. Most well known (and

comprehensive) is the book by Cover and Thomas [2012]. Another famous book

is the elementary and enjoyable introduction by MacKay [2003]. The approach

we have taken for defining and understanding the relative entropy is inspired by

an excellent shorter book by Gray [2011]. Theorem 14.1 connects our definition of

relative entropies to densities (the ‘classic definition’). It can be found in§5.2 of

the aforementioned book. Dobrushin’s theorem is due to him [Dobrushin, 1959].

An alternative source is Lemma 5.2.2 in the book of Gray [2011]. Theorem 14.2 is

also known as the Bretagnolle–Huber inequality [Bretagnolle and Huber, 1979].

14.5 Exercises

14.1 LetPbe a probability distribution onN+andpi=P({i}). Show that for

any prefix codec:N+→{ 0 , 1 }∗it holds that

∑∞

i=1

pi`(c(i))≥H 2 (P).

Hint Use Kraft’s inequality from Note 1.

14.2 Find probability measuresPandQonN+withPQandD(P,Q) =∞.

14.3Prove the inequality in Eq. (14.9) for prefix free codesc.

Hint Consider an infinite sequence of independent Bernoulli random variables

(Xn)∞n=1whereXn∼B(1/2). ViewingXas an infinite binary string, what is the

probability thatXhas a prefix that is a code for some symbol?

14.4 Let (Ω,F) be a measurable space and letP,Q:F →[0,1] be probability

measures. Leta < bandX: Ω→[a,b] be aF-measurable random variable.

Prove that

∣∣

∣∣

∫

Ω

X(ω)dP(ω)−

∫

Ω

X(ω)dQ(ω)

∣∣

∣∣≤(b−a)δ(P,Q).

14.5(Entropy inequalities) Prove that each of the inequalities in Eq. (14.15)

is tight.

14.6(Counting measure absolute continuity and derivatives) Let Ω be

a countable set andp: Ω→[0,1] be a distribution on Ω so that

∑

ω∈Ωp(ω) = 1.

LetPbe the measure associated withp, which means thatP(A) =

∑

ω∈Ap(ω).

Recall that the counting measureμis the measure on (Ω, 2 Ω) given byμ(A) =|A|

ifAis finite andμ(A) =∞otherwise.

(a) Show thatPis absolutely continuous with respect toμ.