Bandit Algorithms

2.1 Probability spaces and random elements 24

collectionX 1 ,...,Xkof random variables. For this to make sense, the constraints

should not contradict each other, which means there is a probability measure

μonB(Rk) such thatμsatisfies the postulated constraints. But then we can

choose Ω =Rk,F=B(Rk),P=μandXi: Ω→Rbe theith coordinate

map:Xi(ω) =ωi. The pushforward ofPunderXisμ, which by definition is

compatible with the constraints.

A more specific question is whether for a particular set of constraints on the

joint law there exists a measureμcompatible with the constraints. Very often the

constraints are specified for elements of the cartesian product of finitely many

σ-algebras, like in Eq. (2.1). If (Ω 1 ,F 1 ),...,(Ωn,Fn) are measurable spaces, then

the cartesian product ofF 1 ,...Fnis

F 1 ×···×Fn={A 1 ×···×An:A 1 ∈F 1 ,...,An∈Fn}⊆ 2 Ω^1 ×···×Ωn.

Elements of this set are known asmeasurable rectanglesin Ω 1 ×···×Ωn.

Theorem2.4 (Carath ́eodory’s extension theorem). Let(Ω 1 ,F 1 ),...,(Ωn,Fn)
be measurable spaces andμ ̄:F 1 ×···×Fn→[0,1]be a function such that:

(a)μ ̄(Ω 1 ×···×Ωn) = 1.

(b)μ ̄(∪∞k=1Ak) =

∑∞

k=1 ̄μ(Ak)for all sequences of disjoint sets with Ak ∈

F 1 ×···×Fn.

LetΩ = Ω 1 ×···×ΩnandF=σ(F 1 ×···×Fn). Then there exists a unique
probability measureμon(Ω,F)such thatμagrees withμ ̄onF 1 ×···×Fn.

The theorem is applied by letting Ωk=RandFk=B(R). Then the values of

a measure on all cartesian products uniquely determines its value everywhere.

It is not true thatF 1 ×F 2 =σ(F 1 ×F 2 ). Take for example,F 1 =F 2 = 2{^1 ,^2 }.

Then,|F 1 × F 2 |= 1 + 3×3 = 10 (because∅ ×X =∅), while, since

F 1 ×F 2 includes the singletons of 2{^1 ,^2 }×{^1 ,^2 },σ(F 1 ×F 2 ) = 2{^1 ,^2 }×{^1 ,^2 }.

Hence, six sets are missing fromF 1 ×F 2. For example,{(1,1),(2,2)} ∈

σ(F 1 ×F 2 )\F 1 ×F 2.

Theσ-algebraσ(F 1 ×···×Fn) is called theproductσ-algebraof (Fk)k∈[n]
and is also denoted byF 1 ⊗···⊗Fn. The product operation turns out to be
associative: (F 1 ⊗F 2 )⊗F 3 =F 1 ⊗(F 2 ⊗F 3 ), which justifies writingF 1 ⊗F 2 ⊗F 3.
As it turns out, things work out well again with Borelσ-algebras: Forp,q∈N+,
B(Rp+q) =B(Rp)⊗B(Rq). Needless to say, the same holds when there are more
than two terms in the product.