18.445 Homework 4 Solutions

18.445 HOMEWORK 4 SOLUTIONS Exercise 1. Let X, Y be two random variables on (Ω, F, P). Let A ⊂ F be a sub-σ-algebra. The random variables X and Y are said to be independent conditionally on A is for every non-negative measurable functions f, g, we have E[f (X)g(Y ) | A] = E[f (X) | A] × E[g(Y ) | A] a.s. Show that X, Y are independent conditionally on A is and only if for every non-negative A-measurable random variable Z, and every non-negative measurable functions f, g, we have E[f (X)g(Y )Z] = E[f (X)ZE[g(Y ) | A]]. Proof. If X and Y are independent conditionally on A and Z is A-measurable, then E[f (X)g(Y )Z] = E E[f (X)g(Y )Z | A] = E E[f (X)g(Y ) | A]Z = E E[f (X) | A]E[g(Y ) | A]Z = E E f (X)E[g(Y ) | A]Z | A = E f (X)ZE[g(Y ) | A] . Conversely, if this equality holds for every nonnegative A-measurable Z, then in particular, for every A ∈ A, E[f (X)g(Y ):A ] = E f (X)E[g(Y ) | A]:A . It follows from the definition of conditional expectation that E[f (X)g(Y ) | A] = E f (X)E[g(Y ) | A] | A = E[f (Y ) | A]E[g(Y ) | A], so X and Y are independent conditionally on A. D Exercise 2. Let X = (Xn )n≥0 be a martingale. (1). Suppose that T is a stopping time, show that X T is also a martingale. In particular, E[XT ∧n ] = E[X0 ]. Proof. Since X is a martingale, first we have E[|XnT |] ≤ E[max |Xi |] ≤ i≤n n n E[|Xi |] < ∞. i=1 Moreover, for every n ≥ m, E[XnT | Fn−1 ] = E[XnT−1 + (Xn − Xn−1 ):T >n−1 | Fn−1 ] = E[XnT−1 ] + :T >n−1 E[Xn − Xn−1 | Fn−1 ] = E[XnT−1 ]. We conclude that X T is a martingale. D 1 (2). Suppose that S ≤ T are bounded stopping times, show that E[XT | FS ] = XS , a.s. In particular, E[XT ] = E[XS ]. Proof. Suppose S and T are bounded by a constant N ∈ N. For A ∈ FS , E[XN 1A ] = N X E[XN 1A 1S=i ] i=1 = N h i X E E[XN | FS ]1A 1S=i i=1 N h i X = E E[XN | Fi ]1A 1S=i i=1 = N h i X E Xi 1A 1S=i i=1 = E[XS 1A ], so E[XN | FS ] = XS . Similarly, E[XN | FT ] = XT . We conclude that h i E[XT | FS ] = E E[XN | FT ] | FS = E[XN | FS ] = XS .  (3). Suppose that there exists an integrable random variable Y such that |Xn | ≤ Y for all n, and T is a stopping time which is finite a.s., show that E[XT ] = E[X0 ]. Proof. Since |Xn | ≤ Y for all n and T is finite a.s., |Xn∧T | ≤ Y . Then the dominated convergence theorem implies that lim E[Xn∧T ] = E[ lim Xn∧T ] = E[XT ]. n→∞ n→∞ As n ∧ T is a bounded stopping time, Part (2) implies that E[Xn∧T ] = E[X0 ]. Hence we conclude that E[XT ] = E[X0 ].  (4). Suppose that X has bounded increments, i.e. ∃M > 0 such that |Xn+1 − Xn | ≤ M for all n, and T is a stopping time with E[T ] < ∞, show that E[XT ] = E[X0 ]. PT Proof. We can write E[XT ] = E[X0 ] + E[ i=1 (Xi − Xi−1 )], so it suffices to show that the last term is zero. Note that T T X X E[| (Xi − Xi−1 )|] ≤ E[ |Xi − Xi−1 |] ≤ M E[T ] < ∞. i=1 i=1 Then the dominated convergence theorem implies that T ∞ X X E[ (Xi − Xi−1 )] = E[ (Xi − Xi−1 )1T ≥i ] i=1 i=1 = = ∞ X i=1 ∞ X E[(Xi − Xi−1 )1T ≥i ] E[Xi − Xi−1 ]P[T ≥ i] i=1 = 0, where we used that Xi − Xi−1 is independent of {T ≥ i} = {T < i − 1} as T is a stopping time of the martingale X.  Exercise 3. Let X = (Xn )n≥0 be Gambler’s ruin with state space Ω = {0, 1, 2, ..., N }: X0 = k, P[Xn+1 = Xn + 1 | Xn ] = P[Xn+1 = Xn − 1 | Xn ] = 1/2, 2 τ = min{n : Xn = 0 or N }. (1). Show that Y = (Yn := Xn2 − n)n≥0 is a martingale. Proof. By the definition of X, E[Yn | Fn−1 ] = E[Xn2 − n | Fn−1 ] 2 = E[(Xn − Xn−1 )2 + 2(Xn − Xn−1 )Xn−1 + Xn−1 − n | Fn−1 ] 2 −n = E[(Xn − Xn−1 )2 | Xn−1 ] + 2E[Xn − Xn−1 | Xn−1 ]Xn−1 + Xn−1 2 = 1 + 0 + Xn−1 − n = Yn−1 , so Y is a martingale.  (2). Show that Y has bounded increments. Proof. It is clear that |Yn − Yn−1 | = |Xn2 − Xn2−1 − 1| ≤ |Xn + Xn−1 ||Xn − Xn−1 | + 1 ≤ |Xn−1 | + 1 + |Xn−1 | + 1 ≤ 2N + 2, so Y has bounded increments.  (3). Show that E[τ ] < ∞. Proof. First, let α be the probability that the chain increases for N consecutive steps, i.e. α = P[Xi+1 − Xi = 1, Xi+2 − Xi+1 = 1, . . . , Xi+N − Xi+N −1 = 1] which is positive and does not depend on i. If τ > mN , then the chain never increases N times consecutively in the first mN steps. In particular, {τ > mN } ⊂ m−1 \ {XiN +1 − XiN = 1, XiN +2 − XiN +1 = 1, . . . , XiN +N − XiN +N −1 = 1}c . i=0 Since the events on the right-hand side are independent and each have probability 1 − α < 1, P[τ > mN ] ≤ (1 − α)m . For mN ≤ l < (m + 1)N , P[τ > l] ≤ P[τ > mN ], so E[τ ] = ∞ X l=0 P[τ > l] ≤ ∞ X N P[τ > mN ] ≤ N m=0 ∞ X (1 − α)m < ∞. m=0  (4). Show that E[τ ] = k(N − k). Proof. Since E[Xn+1 − Xn | Fn ] = 0 and |Xn+1 − Xn | = 1, X is a martingale with bounded increments. We also showed that Y is a martingale with bounded increments. As E[τ ] < ∞, Exercise 2 Part (4) implies that k = E[X0 ] = E[Xτ ] = P[Xτ = 0] · 0 + P[Xτ = N ] · N and k 2 = E[Y0 ] = E[Yτ ] = E[Xτ2 ] − E[τ ]. (1) (2) Then (1) gives, P[Xτ = N ] = k/N . Hence it follows from (2) that E[τ ] = E[Xτ2 ] − k 2 = P[Xτ = 0] · 0 + P[Xτ = N ] · N 2 − k 2 = kN − k 2 = k(N − k).  Exercise 4. Let X = (Xn )n≥0 be the simple random walk on Z. 3 (1). Show that (Yn := Xn3 − 3nXn )n≥0 is a martingale. Proof. We have E[Yn − Yn−1 | Fn−1 ] = E[Xn3 − 3nXn − Xn3−1 + 3(n − 1)Xn−1 | Fn−1 ] 2 = E[(Xn − Xn−1 )3 + 3(Xn − Xn−1 )2 Xn−1 + 3(Xn − Xn−1 )Xn−1 − 3n(Xn − Xn−1 ) − 3Xn−1 | Fn−1 ] 2 = E[(Xn − Xn−1 )3 ] + 3E[(Xn − Xn−1 )2 ]Xn−1 + 3E[Xn − Xn−1 ]Xn−1 − 3nE[Xn − Xn−1 ] − 3Xn−1 = 0 + 3Xn−1 + 0 − 0 − 3Xn−1 = 0, so Y is a martingale.  (2). Let τ be the first time that the walker hits either 0 or N . Show that, for 0 ≤ k ≤ N , we have Ek [τ | Xτ = N ] = N 2 − k2 . 3 Proof. Since 0 ≤ Xnτ ≤ N , the martingale Y τ is bounded and thus has bounded increments. The stopping time τ is the same as in Exercise 3, so the same argument implies that k 3 = E[Y0 ] = E[Yτ ] = E[Xτ3 ] − 3E[τ Xτ ]. We compute that E[Xτ3 ] = P[Xτ = 0] · 0 + P[Xτ = N ] · N 3 = kN 2 . Hence kN 2 − k 3 = E[τ Xτ ] = P[Xτ = 0] · 0 + P[Xτ = N ] · E[τ N | Xτ = N ] = kE[τ | Xτ = N ]. 3 We conclude that E[τ | Xτ = N ] = N 2 − k2 . 3  Exercise 5. Let (Ω, F, P) be a probability space with filtration (Fn )n≥0 . (1). For any m, m0 ≥ n and A ∈ Fn , show that T = m1A + m0 1Ac is a stopping time. Proof. Assume without loss of generality that m ≤ m0 (since we can flip the roles of A and Ac ). If l < m, then {T ≤ l} = ∅ ∈ Fl . If m ≤ l < m0 , then {T ≤ l} = A ∈ Fn ⊂ Fl as n ≤ m ≤ l. If l ≥ m0 , then {T ≤ l} = Ω ∈ Fl . Hence T is a stopping time.  (2). Show that an adapted process (Xn )n≥0 is a martingale if and only if it is integrable, and for every bounded stopping time T , we have E[XT ] = E[X0 ]. Proof. The “only if” part was proved in Exercise 2 Part (2) with S ≡ 0. Conversely, suppose for every bounded stopping time T , we have E[XT ] = E[X0 ]. In particular, E[Xm ] = E[X0 ] for every m ∈ N. Moreover, for n ≤ m and A ∈ Fn , Part (1) implies that T = n1A + m1Ac is a bounded stopping time. Thus E[Xm ] = E[X0 ] = E[XT ] = E[Xn 1A + Xm 1Ac ], so E[Xm 1A ] = E[Xn 1A ]. By definition, this means E[Xm | Fn ] = Xn , so X is a martingale. Exercise 6. Let X = (Xn )n≥0 be a martingale in L2 . 4  (1). Show that its increments (Xn+1 − Xn )n≥0 are pairwise orthogonal, i.e. for all n = 6 m, we have E[(Xn+1 − Xn )(Xm+1 − Xm )] = 0. Proof. First, note that for any n ≤ m, h i h i E[Xn Xm ] = E E[Xn Xm | Fn ] = E Xn E[Xm | Fn ] = E[Xn2 ]. Now assume without loss of generality that n < m. Then E[(Xn+1 − Xn )(Xm+1 − Xm )] = E[Xn+1 Xm+1 ] − E[Xn Xm+1 ] − E[Xn+1 Xm ] + E[Xn Xm ] 2 2 = E[Xn+1 ] − E[Xn2 ] − E[Xn+1 ] + E[Xn2 ] = 0.  (2). Show that X is bounded in L2 if and only if X E[(Xn+1 − Xn )2 ] < ∞. n≥0 Proof. Note that E[X0 (Xn+1 − Xn )] = E[X02 ] − E[X02 ] = 0 by the computation in Part (1). Thus for any m, we have m−1 m−1 h X X
2 i 2 E[Xm ] = E X0 + (Xn+1 − Xn ) = E[X02 ] + E[(Xn+1 − Xn )2 ] n=0 n=0 where the cross terms disappear by Part (1). Therefore, X 2 sup E[Xm ] = E[X02 ] + E[(Xn+1 − Xn )2 ]. m≥0 (3) n≥0 If X is bounded in L2 , i.e. the left-hand side in (3) is bounded, then the sum on the right-hand side is bounded. Conversely, if the sum is bounded, since X0 is in L2 , the left-hand side is also bounded.  5