Bandit Algorithms

2.1 Probability spaces and random elements 20

with any predicate (an expression evaluating to true or false) whereU,V,...are
functions with domain Ω.
What properties shouldPsatisfy? Since Ω is the set of all possible outcomes
it seems reasonable to expect thatPis defined for Ω andP(Ω) = 1. Second,
probabilities should be nonnegative soP(A)≥0 for anyA⊂Ω on whichPis
defined. LetAc= Ω\Abe thecomplementofA. Then we should expect that
P(Ac) = 1−P(A) (negation rule). Finally, ifA,Bare disjoint so thatA∩B=∅
andP(A),P(B) andP(A∪B) are all defined, thenP(A∪B) =P(A) +P(B).
This is called thefinite additivity property.
LetFbe the set of subsets of Ω on whichPis defined. It would seem silly if
A∈ FandAc∈ F/ , sinceP(Ac) could simply be defined byP(Ac) = 1−P(A).
Similarly, ifPis defined on disjoint setsAandB, then it makes sense ifA∪B∈F.
We will also require the additivity property to hold(i)regardless of whether the
sets are disjoint and(ii)even forcountably infinitely manysets. If{Ai}iis a
collection of sets andAi∈Ffor alli∈N, then∪iAi∈Fand if these sets are
disjoint,P(∪iAi) =

∑

iP(Ai). A set of subsets that satisfies all these properties

is called aσ-algebra, which is pronounced ‘sigma-algebra’ and sometimes also

called aσ-field (see Note 1).

Definition2.1 (σ-algebra and probability measures).A setF ⊆ 2 Ωis aσ-

algebra if Ω∈ FandAc∈ Ffor allA∈ Fand∪iAi∈ Ffor all{Ai}iwith

Ai∈ Ffor alli∈N. That is, it should include the whole outcome space and

be closed under complementation and countable unions. A functionP:F →R

is aprobability measure ifP(Ω) = 1 and for allA∈ F,P(A)≥0 and

P(Ac) = 1−P(A) andP(∪iAi) =

∑

iP(Ai) for all countable collections of disjoint

sets{Ai}iwithAi∈ Ffor alli. IfF is aσ-algebra andG ⊂ Fis also aσ-

algebra, then we sayGis asub-σ-algebraofF. IfPis a measure onF, then

therestrictionofPtoGis a measureP|GonGdefined byP|G(A) =P(A) for

allA∈G.

At this stage, the reader may rightly wonder about why we introduced the notion
of sub-σ-algebras. The answer should become clear quite soon. The elements
ofF are calledmeasurable sets. They are measurable in the sense thatP
assigns values to them. The pair (Ω,F) alone is called ameasurable space,
while the triplet (Ω,F,P) is called aprobability space. If the condition that
P(Ω) = 1 is lifted, thenPis called ameasure. If the condition thatP(A)≥ 0
is also lifted, thenPis called asigned measure. For measures and signed
measures it would be unusual to use the symbolP, which is mostly reserved for
probabilities. Probability measures are also calledprobability distributions,
or justdistributions.
Random variables lead to new probability measures. In particular,PX(A) =
P

(

X−^1 (A)

)

is a probability measure defined for all the subsetsAofNfor which

P

(

X−^1 (A)

)

is defined. The probability measurePXis called thelawofXor the

pushforwardmeasure ofPunderX.