60.2. DISCRETE MARTINGALES 1949

Note that if {Xk} is a martingale, then {|Xk|} is a submartingale and that if {Xk} is asubmartingale and φ is convex and increasing, then {φ (Xk)} is a submartingale.

An upcrossing occurs when a sequence goes from a up to b. Thus it crosses the interval,[a,b] in the up direction, hence upcrossing. More precisely,

Definition 60.2.2 Let {xi}Ii=1 be any sequence of real numbers, I ≤ ∞. Define an increas-

ing sequence of integers {mk} as follows. m1 is the first integer ≥ 1 such that xm1 ≤ a, m2is the first integer larger than m1 such that xm2 ≥ b, m3 is the first integer larger than m2such that xm3 ≤ a, etc. Then each sequence,

{xm2k−1 , · · · ,xm2k

}, is called an upcrossing of

[a,b].

Here is a picture of an upcrossing.

b

a

Proposition 60.2.3 Let {Xi}ni=1 be a finite sequence of real random variables defined on Ω

where (Ω,S ,P) is a probability space. Let U[a,b] (ω) denote the number of upcrossings ofXi (ω) of the interval [a,b]. Then U[a,b] is a random variable.

Proof: Let X0 (ω) ≡ a + 1, let Y0 (ω) ≡ 0, and let Yk (ω) remain 0 for k = 0, · · · , luntil Xl (ω) ≤ a. When this happens (if ever), Yl+1 (ω) ≡ 1. Then let Yi (ω) remain 1 fori = l + 1, · · · ,r until Xr (ω) ≥ b when Yr+1 (ω) ≡ 0. Let Yk (ω) remain 0 for k ≥ r + 1until Xk (ω)≤ a when Yk (ω)≡ 1 and continue in this way. Thus the upcrossings of Xi (ω)are identified as unbroken strings of ones for Yk with a zero at each end, with the possibleexception of the last string of ones which may be missing the zero at the upper end andmay or may not be an upcrossing.

Note also that Y0 is measurable because it is identically equal to 0 and that if Yk ismeasurable, then Yk+1 is measurable because the only change in going from k to k+1 is achange from 0 to 1 or from 1 to 0 on a measurable set determined by Xk. In particular,

Y−1k+1 (1) = ([Yk = 1]∩ [Xk < b])∪ ([Yk = 0]∩ [Xk ≤ a])

This set is in S by induction. Of course, Y−1k+1 (0) is just the complement of this set. Thus

Yk+1 is S measurable since 0,1 are the only two values possible. Now let

Zk (ω) =

{1 if Yk (ω) = 1 and Yk+1 (ω) = 0,0 otherwise,

if k < n and

Zn (ω) =

{1 if Yn (ω) = 1 and Xn (ω)≥ b,0 otherwise.