Bandit Algorithms

2.7 Notes 38

normal distribution and its density

p(x) =

1

√

2 π

exp(−x^2 /2), (2.10)

which can be integrated over intervals to obtain the probability that a Gaussian

random variable will take a value in that interval. The reader should notice

thatp:R→Ris Borel measurable and that the Gaussian measure associated

with this density isPon (R,B(R)) defined by

P(A) =

∫

A

pdλ.

Here the integral is with respect to the Lebesgue measureλon (R,B(R)). The

notion of a density can be generalized beyond this simple setup. LetPandQ

be measures (not necessarily probability measures) on arbitrary measurable

space (Ω,F). TheRadon-Nikodym derivativeofPwith respect toQis an

F-measurable random variabledPdQ: Ω→[0,∞) such that

P(A) =

∫

A

dP

dQ

dQ for allA∈F. (2.11)

We can also write this in the form

∫

IAdP=

∫

IAdPdQdQ,A∈F, from which we

may realize that for anyX P-integrable random variable,

∫

XdP=

∫

XdPdQdQ

must also hold. This is often called thechange-of-measure formula. Another

word for the Radon-Nikodym derivativedQdPis thedensityofPwith respect to

Q. It is not hard to find examples where the density does not exist. We say that

Pisabsolutely continuouswith respect toQifQ(A) = 0 =⇒ P(A) = 0

for allA∈ F. WhendPdQ exists it follows immediately thatP is absolutely

continuous with respect toQby Eq. (2.11). Except for some pathological cases

it turns out that this is both necessary and sufficient for the existence ofdP/dQ.

The measureQisσ-finite if there exists a countable covering{Ai}of Ω with

F-measurable sets such thatQ(Ai)<∞for eachi.

Theorem2.13.LetP,Qbe measures on a common measurable space(Ω,F)

and assume thatQisσ-finite. Then the density ofPwith respect toQ,dPdQ,

exists if and only ifPis absolutely continuous with respect toQ. Furthermore,

dP

dQis uniquely defined up to aQ-nul l set so that for anyf^1 ,f^2 satisfying(2.11),

f 1 =f 2 holdsQ-almost surely.

Densities work as expected. Suppose thatZis a standard Gaussian random
variable. We usually write its density as in Eq. (2.10), which we now know
is the Radon-Nikodym derivative of the Gaussian measure with respect to
the Lebesgue measure. The densities of ‘classical’ continuous distributions are
almost always defined with respect to the Lebesgue measure.
10 In line with the literature, we will usePQto denote thatPis absolutely
continuous with respect toQ. WhenPis absolutely continuous with respect
toQ, we also say thatQdominatesP. The intuitive meaning of the symbol