Martingales and Stopping Times

Advanced Stochastic Processes. LECTURE 10 Martingales and stopping times Lecture outline • Martingales and properties. • Stopping times. Stopping theorems. 10.1. Martingales We continue with studying examples of martingales. • Brownian motion. A standard Brownian motion B(t) is a martingale. Let us first clarify with respect to which filtration. For every fixed t, the Brownian motion B(s), 0 ≤ s ≤ t is measurable with respect to the Borel σ­field B = Bt generated by continuous functions f ∈ C[0, t] (see first lecture). The sequence of fields Bt generates a filtration on C[0, ∞) since t1 ≤ t2 implies Bt1 ⊂ Bt2 (check this statement). We see that Brownian motion B(t) is adapted to this filtration. We claim that in fact it is a martingale. Indeed fix 0 ≤ s < t. We have E[B(t)|Bs ] = E[B(t) − B(s) + B(s)|Bs ] = E[B(t) − B(s)|Bs ] + E[B(s)|Bs ] = 0 + B(s) = B(s) where we use the fact that, due to the independent increments property, B(t) − B(s) is independent from Bs , implying E[B(t) − B(s)|Bs ] = E[B(t) − B(s)] = 0; and B(s) ∈ Bs , implying E[B(s)|Bs ] = B(s). • Brownian motion with drift. Now consider a Brownian motion with drift µ and standard deviation σ. That is consider Bµ (t) = µt + σB(t), where B is the standard Brownian motion. It is straightforward to show that Bµ (t) − µt is a martingale. Also it is simple to show that (Bµ (t) − µt)2 − σ 2 t is also a martingale. 1 2 • Wald’s martingale. Suppose Xn , n ∈ N is an i.i.d. sequence with E[X1 ] = µ, such that the exponential moment generating function M (θ) � E[eθX1 ] < ∞ for some θ > 0. � n) is a martingale. It is straightforward to check Let Sn = 1≤k≤n Xk . Then Zn = exp(θS M n (θ) this. 10.2. Properties of martingales Note that if Xn is submartingale, then −Xn is supermartingale and vice verse. Proposition 1. Suppose Xn is a martingale and φ is a convex function such that E[|φ(Xn )|] < ∞. Then φ(Xn ) is a submartingale. Proof. We apply conditional Jensen’s inequality: E[Φ(Xn+1 )|Fn ] ≥ φ(E[Xn+1 |F ]) = φ(Xn ). � Note that if Xn was submartingale and Φ was non­decreasing, then the same result applies. As a corollary we obtain that if for some p ≥ 1 we have E[|Xn |p ] < ∞ for all n, then |Xn |p is submartingale. Definition 10.1. A sequence of random variables Hn is defined to be predictable if Hn ∈ Fn−1 . Here is sort of an artificial example. Let Xn be adapted to filtration Fn . Then Hn = Xn−1 , H0 = H1 = H0 , is predictable. We simply ”played” with indices. Instead now consider Hn = E[Xn |Fn−1 ]. By the definition of conditional expectations, Hn ∈ Fn−1 , so it is predictable. Theorem 10.2 (Doob’s decomposition). Every submartingale Xn , n ≥ 0 adapted to filtration Fn , can be written in a unique way as Xn = Mn + An where Mn is a martingale and An is non­decreasing sequence, predictable with respect to Fn . Proof. Set A0 = 0 and define An recursively by An = An−1 + E[Xn |Fn−1 ] − Xn−1 ≥ An−1 . Let Mn = Xn − An . By induction, we have that An ∈ Fn−1 since An−1 ∈ Fn−2 ⊂ Fn−1 and E[Xn |Fn−1 ], Xn−1 ∈ Fn−1 . Therefore An is predictable. We now need to show that Mn is a martingale. We have E[Mn |Fn−1 ] = E[Xn − An |Fn−1 ] = E[Xn |Fn−1 ] − An = Xn−1 − An−1 = Mn−1 . Thus Mn is indeed a martingale. This completes the proof of the existence part. To prove uniqueness, we assume that Xn = Mn� + An� is any such decomposition. Then � E[Xn |Fn−1 ] = E[Mn� + A�n |Fn−1 ] = Mn−1 + A�n = Xn−1 − A�n−1 + A�n since, by assumption, Mn� is a martingale and A�n is predictable. Then we see that A�n satisfies the same recursion as An , implying A�n = An . It then immediately follows that Mn� = Mn . � The concept of predictable sequences is useful when we want to model a gambling scheme, or in general any controlled stochastic process, where we observe the state Xn−1 of the process at time t = n − 1, take some decision at time t = n and observe the realization Xn at time t = n. This realization might actually depend on our decision. In the special case of gambling, suppose Xn − Xn−1 = ±1. Xn is your wealth at time n if in each round you bet one dollar. In particular, � If you instead bet an amount Hn each time, then your net at time n is 1≤m≤n Hm (Xm − Xm−1 ). LECTURE 10. MARTINGALES 3 Modelling Xn as an i.i.d. coin toss sequence with the usual product σ­field on {0, 1}∞ , we have Xn is adapted to the σ­field on {0, 1}n and Hn is predictable. Is there a scheme which allows us to beat the system? In fact, yes. This is the famous double the bet strategy. We make H1 = 1 and Hn = 2Hn−1 if Xn−1 − Xn−2 = −1 and stop once Xn−1 − Xn−2 = 1, then assuming we won the first time in round k, our net worth is −1 − 2 − · · · − 2k−1 + 2k = 1. If P(Xn−1 − Xn−2 = 1) > 0, and the games have independently distributed outcomes, then we win a.s. a dollar at some random time t = k. As we will see this was possible because we did not put a bound on how long we are allowed to play and how much we are allowed to lose. We will establish that either of this conditions make beating the gambling system impossible. For now we establish the following result. Theorem � 10.3. Suppose Xn is a supermartingale and Hn ≥ 0 is predictable. Then Zn = 1≤m≤n Hm (Xm − Xm−1 ) is also a supermartingale. Proof. We have E[Zn+1 |Fn ] = E[Hn+1 (Xn+1 − Xn )|Fn ] + E[ � Hm (Xm − Xm−1 )|Fn ]. 1≤m≤n Since H is predictable, then Hn+1 ∈ Fn , implying that the first summand is equal to Hn+1 E[(Xn+1 − Xn )|Fn ] ≤ 0, where inequality follows since Xn is supermartingale. On the other hand, � Hm (Xm − Xm−1 )|Fn = Zn ∈ Fn , 1≤m≤n implying that its expectation is E[Zn |Fn ] = Zn . This completes the proof. � 10.3. Stopping times In the example above, showing how to create a winning gambling system, notice that part of the strategy was to stop the first time when we win. Thus the game is interrupted at a random time, which depends on the observed conditions. We now formalize this using the concept of stopping times. The end goal of this section is establishing the following result: if the gambling strategy involves a stopping time which is bounded, then our expected gain is non­positive. Definition 10.4. Given a filtration {Ft }t∈T on a sample space Ω, a random variable τ : Ω → T is called a stopping time, if the event {τ ≤ t} = {ω ∈ Ω : τ (ω) ≤ t} ∈ Ft , for every t. Here we consider again the two cases T = N or T = R+ . Note, that we do not need to specify a probability measure here. The concept of stopping times is framed only in terms of measurability with respect to σ­fields. • Consider the filtration corresponding to a sequence of random variables X1 , . . . , Xn , . . .. Namely Ω = R∞ and Fn is Borel σ­field of Rn . Fix some real value x. Given any sample ω = (ω1 , . . . , ωn , . . .) ∈ R∞ define � τ (ω) = inf{n : ωk ≥ x}. 1≤k≤n 4 Namely, τ (ω) is the smallest index at which the sum of the components is at least x. Then τ is a stopping time. Indeed, the event τ ≤ n is completely specified by the portion ω1 , . . . , ωn of the sample. In particular � {ω : τ (ω) ≤ n} = ∪1≤k≤n {ω : ωi ≥ x}. 1≤i≤k Each of the events in the union on the right­hand side is measurable with respect to Fn . This example is the familiar Wald’s stopping time: τ is the smallest n for which a random walk X1 + · · · + Xn ≥ x, except for, we do not say that the random sequence should be i.i.d. and, in fact, we do not say anything about the probability law of the sequence at all. • Consider the standard Wiener measure on C([0, ∞)), that is consider the standard Brow­ nian motion. Then, given a > 0, Ta = inf{t : B(t) = a} is a stopping time with respect to the filtration Ft , t ∈ R+ , where Ft is the Borel σ­field on C([0, t]). This is the familiar hitting time of the Brownian motion. The main result in terms of stopping times that we wish to establish is as follows. Theorem 10.5. Suppose Xn is a supermartingale and τ is a stopping time, which is a.s. bounded. That is, for some integer M > 0, we have τ ≤ M a.s. Then E[Xτ ] ≤ E[X0 ]. In other words, if there exists a bound on the number of rounds for betting, then the expected net gain is non­ positive, provided that in each round the expected gain is non­positive. This theorem will be established as a result of several short lemmas. Lemma 10.6. Suppose τ is a stopping time corresponding to the filtration Fn . Then the sequence of random variables Hn = 1{τ ≥ n} is predictable. Proof. Hn is a random variable which takes values 0 and 1. Note that the event {Hn = 0} = {τ < n} = {τ ≤ n − 1}. Since τ is a stopping time, then the event {τ ≤ n − 1} ∈ Fn−1 . Thus � Hn is predictable. Given two real values a, b we use a ∧ b to denote min(a, b). Corollary 1. Suppose Xn is supermartingale and τ is a stopping time. Then Yn = Xn∧τ is also a supermartingale. Proof. Define Hn = 1{τ ≥ n}. Observe that � (10.7) Hm (Xm − Xm−1 ) = −H0 X0 + 1≤m≤n � Xm (Hm − Hm+1 ) + Hn Xn 1≤m≤n−1 Note, H0 = 1{τ ≥ 0} = 1. Hm − Hm+1 = 1{τ ≥ m} − 1{τ ≥ m + 1} = 1{τ = m}. Therefore, the expression on the right­hand side of (10.7) is equal to Xn∧τ − X0 . By Theorem 10.3, the left­hand side of (10.7) is a supermartingale. Since the constant process X0 is also trivially a supermartingale, their sum is a supermartingale. We conclude that Yn = Xn∧τ is a supermartin­ gale. � Now we are ready to obtain our end result. LECTURE 10. MARTINGALES 5 Proof of Theorem 10.5. The process Yn = Xn∧τ is a supermartingale by Corollary 1. There­ fore E[YM ] ≤ E[Y0 ] But YM = XM ∧τ = Xτ and Y0 = X0∧τ = X0 . We conclude E[Xτ ] ≤ E[X0 ]. This concludes the proof of Theorem 10.5. � 10.4. Additional reading materials • Durrett [1] Chapter 4.