Bandit Algorithms

3.1 Stochastic processes 46

infinite sequence such that

x=

∑∞

t=1

Ft(x)2−t.

We can viewF 1 ,F 2 ,...as (binary valued) random variables over the probability

space ([0,1],B([0,1]),λ). Viewed as such, a direct calculation shows that

F 1 ,F 2 ,...are independent. From this we can create an infinite sequence of

uniform random variables by reversing the process. To do this we rearrange the

(Ft)∞t=1sequence into a grid. For example:

F 1 ,F 2 ,F 4 ,F 7 ,···

F 3 ,F 5 ,F 8 ,···

F 6 ,F 9 ,···

F 10 ,···

Letting∑ Xm,tbe thetth entry in themth row of this grid, we defineXm=

∞

t=1^2

−tXm,tand again one can easily check that with this choice the sequence

X 1 ,X 2 ,...is independent andλXt=μis uniform for eacht.

3.1 Stochastic processes

LetT be an arbitrary set. Astochastic processon probability space (Ω,F,P)

is a collection of random variables{Xt:t∈ T}. In this bookT will always

be countable and so in the following we restrict ourselves toT =N. The first

theorem is not the most general, but suffices for our purposes and is more easily

stated than more generic alternatives.

Theorem3.2. For eachn∈N+let(Ωn,Fn)be a Borel space andμnbe a

measure on(Ω 1 ×···×Ωn,F 1 ⊗···⊗Fn)and assume thatμnandμn+1are

related through

μn+1(A×Ωn+1) =μn(A) for allA∈Ω 1 ⊗···⊗Ωn. (3.1)

Then there exists a probability space(Ω,F,P)and random elementsX 1 ,X 2 ,...
withXt: Ω→Ωtsuch thatPX 1 ,...,Xn=μnfor alln.

Sequences of measures (μn)nsatisfying Eq. (3.1) are calledprojective.

Theorem 3.1 follows immediately from Theorem 3.2. By assumption a random

variable takes values in (R,B(R)), which is Borel. Then letμn=⊗nt=1μbe

then-fold product measure ofμwith itself. That this sequence of measures is

projective is clear and the theorem does the rest.