1950 CHAPTER 60. CONDITIONAL, MARTINGALES

Thus Zk (ω) = 1 exactly when an upcrossing has been completed and each Zi is a randomvariable.

U[a,b] (ω) =n

∑k=1

Zk (ω)

so U[a,b] is a random variable as claimed.The following corollary collects some key observations found in the above construction.

Corollary 60.2.4 U[a,b] (ω) ≤ the number of unbroken strings of ones in the sequence,{Yk (ω)} there being at most one unbroken string of ones which produces no upcrossing.Also

Yi (ω) = ψ i

({X j (ω)

}i−1j=1

), (60.2.4)

where ψ i is some function of the past values of X j (ω).

Lemma 60.2.5 Let φ be a convex and increasing function and suppose

{(Xn,Sn)}

is a submartingale. Then if E (|φ (Xn)|)< ∞, it follows

{(φ (Xn) , Sn)}

is also a submartingale.

Proof: It is given that E (Xn+1,Sn)≥ Xn and so

φ (Xn)≤ φ (E (Xn+1|Sn))≤ E (φ (Xn+1) |Sn)

by Jensen’s inequality.The following is called the upcrossing lemma.

60.2.1 Upcrossings

Lemma 60.2.6 (upcrossing lemma) Let {(Xi,Si)}ni=1 be a submartingale and let U[a,b] (ω)

be the number of upcrossings of [a,b]. Then

E(U[a,b]

)≤ E (|Xn|)+ |a|

b−a.

Proof: Let φ (x) ≡ a+(x−a)+ so that φ is an increasing convex function always atleast as large as a. By Lemma 60.2.5 it follows that {(φ (Xk) ,Sk)} is also a submartingale.

φ (Xk+r)−φ (Xk) =k+r

∑i=k+1

φ (Xi)−φ (Xi−1)

=k+r

∑i=k+1

(φ (Xi)−φ (Xi−1))Yi +k+r

∑i=k+1

(φ (Xi)−φ (Xi−1))(1−Yi).