Convergence of Martingales

12

Convergence of martingales

Convergence of martingales

1.  Maximal inequalities

Let (W,K,P,(Fn)n ³ 1) be a stochastic basis and X = (Xn)n be an adapted sequence of random variables. The random variable X* := sup{½Xn½; n ³ 1} is called the maximal variable of X. A maximal inequality is any inequality concerning X*.

We shall also denote by X*n the random variable max(½X1½,½X2½,…,½Xn½). Thus X* = limnX*n = supnX*n .

There are many ways to organize the material: we adopted that of Jacques Neveu (Martingales a temps discrete Masson 1972).

We start with a result concerning the combination of two supermartingales.

Proposition 1.1. Let (Xn)n and (Yn)n be two supermartingales. Let t be stopping times. Suppose that if

(1.1) t¥, then Xt ³ Yt. Define Zn = Xn1{n < t} + Yn1{n ³ t} .

Then Z is again a supermartingale.

Proof. The task is to prove that E(Zn+1½Fn) £ Zn .

But Zn = Xn1{n < t} + Yn1{n ³ t} ³ 1{n < t}E(Xn+1½ Fn) + 1{n ³ t}E(Yn+1½Fn) (as X and Y are supermartingales!) = E(Xn+11{n < t}½ Fn) + E(Yn+11{n ³ t}½Fn) (since t is a stopping time both sets are in Fn!) = E(Xn+11{n < t}+ Yn+11{n ³ t}½Fn) = E(Xn+11{n+1 < t}+Xn+11{t = n+1}+ Yn+11{n ³ t}½Fn) ³ E(Xn+11{n+1 < t}+Yn+11{t = n+1}+ Yn+11{n ³ t}½Fn) (since Xt ³ Yt hence t = n+1 Þ Xn+1 ³ Yn+1!) = E(Xn+11{n+1 < t}+Yn+11{n+1 ³t}½Fn) = E(Zn+1½Fn).

Corollary 1.2. Maximal inequality for nonnegative supermartingales.

The following inequality holds if X is a non-negative supermartingale:

(1.2)  P(X* > a) £

Proof. Let us consider the stopping time

(1.3)  t = inf {n ½ Xn > a} (convention: inf Æ = ¥!)

Remark the obvious fact that X* > a Û t < ¥.

In the previous proposition we consider Xn to be even our supermartingale X and Yn = a (any constant is of course a martingale). The condition (1.1) is fulfilled since t < ¥ Þ Xt > a. It means that Zn = Xn1{nt} + a1{t£n} is a supermartingale hence EZn £ EZ1 = E(X11{t¹1} +a1{ t=1}) £ EX1 (since t=1 Þ Xt = X1 > a) . As a1{t£n} £ Zn it means that aP(t£n) £ EZn Þ P(t£n) ££ . Therefore P(t < ¥) = P() = limn®¥ P(t£n) (since the sets increase!) £ . As a consequence P(X* > a) £ .

Corollary 1.3. If X is a nonnegative supermartingale, then X* < ¥ a.s.

Proof. P(X* = ¥) £ P(X* > a) £ " a > 0.

It follows that for almost all w Î W the sequence (Xn(w))n is bounded.

We shall prove now a maximal inequality for the submartingales.

Proposition 1.4 . Let X be a submartingale. Then

(1.4)  P(X* > a) £

(1.5)  P(X*n > a) £

Proof. Let m = supn E½Xn½ , let a > 0 and let Yn = ½Xn½. Then Y is another submartingale, by Jensen’s inequality hence m = limn®¥ E½Xn½. Let

(1.6) t = inf {n ½ Yn > a} (inf Æ := ¥!)

Then the stopped sequence (YnÙt)n remains a submartingale (any bounded stopping time is regular!) and YtÙn ³ a1{t£n} + Yn1{tn}. (Indeed, by the very definition of t , t¥ Þ Yt > a!)

It follows that a1{t£n} £ YtÙn Þ aP(t £ n) £ EYtÙn £ EYn £ m (the stopping theorem applied to the pair of regular stopping times tÙn and n!) . It means that P(t £ n) £ for any n hence P(t¥ ) £ . But clearly {t < ¥} = {X* > a}.

The second inequality comes from the remark that t £ n Û X*n > a . So a1{t£n} £ YtÙn1{t£n} Þ aP(t £ n) £ E(YtÙn1{t£n}) £ E(Yn1{t£n}) (as tÙn £ n Þ YtÙn £ E(Yn½FtÙn) by the stopping theorem Û E(YtÙn1A) £ E(Yn1A) " A Î FtÙn ; our A is {t £ n}!) . Recalling that {t £ n} = {X*n > a} we discover that aP(X*n > a) £ E(Yn1{ X*n > a }) = E(½Xn½1{ X*n > a }) which is exactly (1.5).

We shall prove now another kind of maximal inequalities concerned with ║X*║p : the so-called Doob’s inequalities.

Proposition 1.5. Let X be a martingale

(i). Suppose that Xn Î Lp " n for some 1 < p < ¥. Let q = p/(p-1) be the Holder conjugate of p. Then

(1.7)  ║X*║p £ q supn║Xn║p

(ii). If Xn are only in L1, then

(1.8)  ║X*║1 £ (1+supn E(½Xn½log+½Xn½)

Proof.

(i). Recall the following trick when dealing with non-negative random variables: if f:[0,¥) ® Â is differentiable and X > 0, then Ef(X) = f(0) + .

If f(x) = xp the above formula becomes EXp =.

Now write (1.5) as tP(X*n> t) £ E(Yn1{X*n > t}) and multiply it with ptp-1. We obtain

ptp-1P(X*n> t) £ ptp-2E(Yn1{S*n > t}). Integrating, one gets E(X*np) £ = = (we applied Fubini, the nonnegative case) = q = qE(Yn(X*n)p-1) £ q║Yn║p║ (X*n)p-1║q (Holder !) . But ║ (X*n)p-1║q = = = ║X*n║pp-1 hence we obtained the inequality ║X*n║pp = E(X*np) £ q║Yn║p║ (X*n)p-1║q = q║Yn║p║X*n║pp-1 or

(1.9)  ║X*n║pp £ q║Yn║p " n.

As a consequence, ║X*n║pp £ qsupk║Yk║p " n. But (X*n)n is an increasing sequence of nonnegative random variables. By Beppo-Levi we see that ║X*║pp =limn®¥║X*n║pp £ qsupk║Yk║p proving the inequality (1.7).

(ii). Look again at (1.5) written as P(X*n> t) £ E(Yn1{X*n > t}). Integrate that from 1 to ¥:

(X*n> t) = = = . Now = lnb if b ³ 1 or = 0 elsewhere. In short =ln+b. It means that = hence the result is

(1.10) (X*n> t) £ E(Ynln+(X*n))

Now look at the right hand term of (1.10). The integrand is of the form aln+b. As alnb = aln(a×) = alna + aln and x > 0 Þ lnx £ x/e , it follows that alnb £ alna + a= alna + . The inequality holds with “xlnx” replaced with “xln+x”. If b > 1, then aln+b = alnb £ alna + £ aln+a + and if b £ 1, then aln+b = 0 £ £ aln+a + . We got the elementary inequality

(1.11) aln+b £ aln+a + " a,b ³ 0

Using (1.11) in (1.10) one gets (X*n> t) £ E(Ynln+Yn) + . Now we are close enough to (1.8) because EX*n = (X*n> t) £ 1 + (X*n> t) £ E(Ynln+Yn) + implying that (1-e-1) EX*n £ 1 + E(Ynln+Yn) " n. Remark that the sequence (Ynln+Yn)n is a submartingale due to the convexity of the function x  xln+x and Jensen’s inequality. So the sequence (E(Ynln+Yn))n is non-decreasing. Be as it may, it is clear now that (1-e-1) EX*n £ 1 + supk E(Ykln+Yk) which implies (1.8) letting n ® ¥.

Remark. If sup ║Xn║p < ¥ , we say that X is bounded in Lp. Doob’s inequalities point out that if p>1 and X is bounded in Lp then X* is in Lp. However, this doesn’t hold for p=1 : if X is bounded in L1, X* may not be in L1. A counterexample is the martingale from Example 4 , previous lesson. If we want X* to be in L1, it means that we want X to be bounded in Lln+L . Meaning the condition (1.8).

2.  Almost sure convergence of semimartingales

We begin with the convergence of the non-negative supermartingales.

If X is a non-negative supermartingale, we know from Corollary 1.3 that X* < ¥ a.s, that is, the sequence (Xn)n is bounded a.s. . So lim inf Xn ¹ - ¥, lim sup Xn ¹ +¥. In this case the fact that (Xn(w))n diverges is the same with the following claim:

(2.1)  There exist a,b rationale numbers, 0 < a < b such that the set {n ½ Xn(w) < a and Xn+k(w) > b for some k > 0} is infinite

Indeed, (Xn(w))n diverges Û a : = lim inf Xn(w) < lim sup Xn(w) := b, 0 £ a < b < ¥., then some subsequence of (Xn(w))n converges to a and other subsequence converges to b; so for any rationales a,b such that a < a < b < b the first subsequence is smaller than a and the second is greater than b.

Let us fix a,b Î Q+, a < b and consider the following sequence of random variables:

t1(w) = inf { n ½ Xn(w) < a}; t2(w) = inf { n > t1(w) ½ Xn(w) > b} …..

t2n-1(w) = inf { n > t2n-2(w)½ Xn(w) < a}; t2n(w) = inf { n > t2n-1(w) ½ Xn(w) > b} …

(always with the convention inf Æ = ¥!) . Then it is easy to see that tn are stopping times. Indeed, it is an induction: t1 is a stopping time and {tk+1 = n} = tk = j,Xj+1 Ï B , … , Xn-1 Ï B, XnÎB} Î Fn (since the first set is Fj Ì Fn), where B = (b,¥) if k is odd and B = (-¥,a) if k is even.

Let ba,b(w) = max{n ½ t2k(w) < ¥}. Then ba,b means the number of times the sequence X(w) crossed the interval (a,b) (the number of upcrossings)

The idea of the proof (belonging to Dubins) is that the sequence X(w) is convergent iff ba,b(w) is finite for any a,b Î Q+.

Notice the crucial fact that

(2.2) ba,b(w) ³ k Û t2k(w) < ¥

Lemma 2.1. The bounded sequence Xn is convergent iff ba,b < ¥ a.s. " a,bÎ Q+, a < b.

Proof. Let E = {w½(Xn(w))n is divergent}. Then wÎ E Û $ a,bÎ Q+, a < b such that ba,b(w) = ¥. In other words E = . Clearly P(E) = 0 Û P(ba,b = ¥) = 0 " a < b, a,bÎ Q+.

Proposition 2.2 (Dubins’ inequality)

(2.3)  P(ba,b ³ k ) £ ()k

Proof.

Let k be fixed and define the sequence Z of random variables as follows:

Zn(w) = 1 if n < t1(w)

if t1(w) £ n < t2(w) (notice that t1(w) <¥ Þ < 1!)

if t2(w) £ n < t3(w) (notice that t2(w) <¥ Þ < !)

if t3(w) £ n < t4(w) (notice that t3(w) <¥ Þ !)

()2 if t4(w) £ n < t5(w) (notice that t4(w) <¥ Þ ()2 < !)

…………

()k-1 if t2k-1(w) £ n < t2k(w) ( t2k-1(w) <¥ Þ ()k-1<()k-2!)

()k if t2k(w) £ n (notice that t2k(w) <¥ Þ ()k <()k-1!)

Because the constant sequences X(j)n = ()j and the sequences Y(j)n = ()j-1are nonnegative supermartingales and we took care that at the combining moment tj the jump be downward, it means that we can apply Proposition (1.1) with the result that Z is a non-negative supermartingale. Moreover, Zn ³ ()k. Therefore E()k £ EZn £ EZ1 £ 1. We obtain the inequality P(t2k £ n ) £ ()k " n . Letting n ® ¥, we get P(t2k < ¥ ) £ ()k which, corroborated with (2.2) gives us (2.3).

Corollary. 2.3. Any non-negative supermartingale X converges a.s. to a random variable X¥ such that E(X¥½Fn) £ Xn. In words, we can add to X its tail X¥ such that (X,X¥) remains a supermartingale.

Proof. From (2.3) we infer that P(ba,b = ¥) = 0 " a < b positive rationales which, together with Lemma 2.1 implies the first assertion. The second one comes from Fatou’s lemma (see the lesson about conditioning!) : E(X¥½Fn) = E(liminfk®¥Xn+k½Fn) £ liminfn®¥ E(Xn+k½Fn) £ Xn.

Remarks.1. Example 4 points out that we cannot automatically replace “nonnegative supermartingale” with “nonnegative martingale” to get a similar result for martingales. In that example X¥ = 0 while EXn = 1. So (X,X¥) , while supermartingale, is not a martingale.

2.  Changing signs one gets a similar result for non-positive submartingales.

3.  Example 5 points out that not all martingales converge. Rather the contrary, if xn are i.i.d such Exn = 0 then the martingale Xn = x1 + … + xn never converges, except in the trivial case xn = 0. Use CLT to check that!

We study now the convergence of the submartingales.

Proposition 2.4. Let X be a submartingale with the property that supn E(Xn)+ < ¥. Then Xn converges a.s. to some X¥ Î L1.

Proof. Let Yn = (Xn)+. As x  x+ is convex and non-decreasing, Y is another submartingale. Let Zp = E(Yp½Fn), p ³ n. Then Zp+1 = E(Yp+1½Fn) ³ E(E(Yp+1½Fp) ½Fn) ³ E(Yp½Fn) hence (Zp)p³n is nondecreasing. Let Mn = limp®¥Zp .

We claim that (Mn)n is a non-negative martingale. First of all, EMn = E(limp®¥Zp) = limp®¥E(Zp) (Beppo-Levi) = limp®¥E(Yp) = supp E(Xp)+ < ¥ (as Y is a submartingale). Therefore Mn Î L1. Next, E(Mn+1½ Fn) = E(limp®¥ E(Yp½Fn+1)½Fn) = limp®¥ E(E(Yp½Fn+1)½Fn) (conditioned Beppo-Levi!) = limp®¥ E(Yp½Fn) = Mn. Thus M is a martingale. Being non-negative, it has an a.s limit, M¥ , by Corollary 2.3.

Let Un = Mn - Xn .

Then U is a supermartingale and Un ³ 0 (clearly, since Un = limp®¥ E(Yp½Fn) - Xn = limp®¥ E(Yp - Xn ½Fn) = limp®¥ E((Xp)+ - Xn ½Fn) ³ limp®¥ E(Xp - Xn ½Fn) ³ 0 (keep in mind that X is a submartingale!).

By Corollary 2.3, U has a limit, too , in L1. Denote it by U¥.

It follows that X = M – U is a diference between two convergent sequences. As both M¥ and U¥ are finite, the meaning is that X has a limit itself, X¥ Î L1.

Corollary 2.5. If X is a martingale, supn E(Xn)+ < ¥ is equivalent with supn E(½Xn½) < ¥ . In that case X has an almost sure limit, X¥.

Proof. ½x½ = 2x+ - x Þ E(½Xn½) = 2E(Xn)+ - EXn . But EXn is a constant, say a . Therefore supn E½Xn½ = 2supnEXn+ - a..

Here is a very interesting consequence of this theory, consequence that deals with random walks.

Corollary 2.6. Let x = (xn)n i.i.d. rev. from L¥. Let Sn = x1+…+xn, S0 = 0 and let m = Ex1. Let a Î Â and t = ta be the hitting time of (a,¥), that is, t = inf {n ½ Sn > a}. Suppose that xn are not constants.

Then m ³ 0 Þ t < ¥ (a.s.).

The same holds for the hitting time of the interval (-¥,a).

Proof. If m > 0 , it is simple. The sequence Sn converges a.s. to ¥ due to the LLN. (Sn/n ® m > 0 Þ Sn ® ¥!) . The problem is if m = 0 . In that case let Xn = a - Sn. Then X is a martingale and EXn = a. If a < 0, t=0 and there is nothing to prove. So we shall suppose that a³0. In this case X0 = a ³ 0 and

(2.4) t = inf{n ½Xn < 0} .

Here is how we shall use the boundedness of the steps xn. Let M = ║xn║¥. Then –M £ xn £ M a.s.

The stopping theorem tells us that Y = (XnÙt)n is another martingale, since every bounded stopping time (we mean tÙn !) is regular. But Yn ³ - M since for n > t Þ Yn = Xn ³ 0 (from (2.4)) and n £ t Þ Yn = Xt = Xt-1 + xt ³ Xt-1 – M ³ 0 – M = M. So Yn+M is another martingale, this time nonnegative. By Corollary 2.5 Yn+M should converge a.s. . Subtracting M, it follows that Yn ® f for some f Î L1. So XnÙt ® f Þ a - SnÙt ® f Þ SnÙt ® a-f . Let E = {t=¥}. If w Î E, then a-f(w) = limSn(w). Meaning that Sn(w) is convergent.