Bandit Algorithms

3.6 Exercises 53

(d)Show that (Xm,t)t≥ 1 is also an independent sequence of Bernoulli random
variables, that are uniformly distributed.
(e) Show thatXt=

∑

t≥ 1 Xm,t^2

−tis uniformly distributed on [0,1].

3.2(Martingales and optional stopping) Let (Xt)∞t=1 be an infinite

sequence of independent Rademacher random variables andSt=

∑t

s=1Xs^2

s− (^1).
(a) Show that (St)∞t=0is a martingale.
(b) Letτ= min{t:St= 1}and show thatP(τ <∞) = 1.
(c) What isE[Sτ]?
(d) Explain why this does not contradict Doob’s optional stopping theorem.
3.3(Martingales and optional stopping (ii)) Give an example of a
martingale (Sn)∞n=0and stopping timeτsuch that
nlim→∞E[Sτ∧n]^6 =E[Sτ].
3.4(Maximal inequality fails without nonnegativity) Show that
Theorem 3.9 does not hold in general for supermartingales if the assumption that
it be nonnegative is dropped.
3.5Let (Ω,F) and (X,G) be measurable spaces,X:X →Rbe a random variable
andK: Ω×G →[0,1] a probability kernel from (Ω,F) to (X,G). Define function
U: Ω→RbyU(ω) =

∫

XX(x)K(ω,dx) and assume thatU(ω) exists for allω.

Prove thatUisF-measurable.

3.6(Limits of increasing stopping times are stopping times) Let (τn)∞n=1
be an almost surely increasing sequence ofF-stopping times on probability space
(Ω,F,P) with filtrationF= (Fn)∞n=1, which means thatτn(ω)≤τn+1(ω) for all
n≥1 almost surely. Prove thatτ(ω) = limn→∞τn(ω) is aF-stopping time.

3.7(Properties of stopping times) LetF= (Ft)t∈Nbe a filtration, and

τ,τ 1 ,τ 2 be stopping times with respect toF. Show the following:

(a)Fτis aσ-algebra.
(b) Ifτ=kfor somek≥1 thenFτ=Fk.
(c) Ifτ 1 ≤τ 2 thenFτ 1 ⊂Fτ 2.
(d)τisFτ-measurable.
(e) If (Xt) isF-adapted thenXτisFτ-measurable.
(f)Fτis the smallestσ-algebra such that allF-adapted sequences (Xt) satisfy
XτisFτ-measurable.

3.8 Prove Theorem 3.10.