1. Random
  2. 16. Martingales
  3. 1
  4. 2
  5. 3
  6. 4
  7. 5
  8. 6

4. Inequalities

Basic Theory

In this section, we will study a number of interesting inequalities associated with martingales and their sub-martingale and super-martingale cousins. These turn out to be very important for both theoretical reasons and for applications. You many need to review infimums and supremums.

Basic Assumptions

As in the introduction, we start with a stochastic process X={Xt:tT} on an underlying probability space (Ω,F,P), having state space R, and where the index set T (representing time) is either N (discrete time) or [0,) (continuous time). Next, we have a filtration F={Ft:tT}, and we assume that X is adapted to F. So F is an increasing family of sub σ-algebras of F and Xt is measurable with respect to Ft for tT. We think of Ft as the collection of events up to time tT. We assume that E(|Xt|)<, so that the mean of Xt exists as a real number, for each tT. Finally, in continuous time where T=[0,), we make the standard assumptions that tXt is right continuous and has left limits, and that the filtration F is right continuous and complete.

Maximal Inequalites

For motivation, let's review a modified version of Markov's inequality, named for Andrei Markov.

If X is a real-valued random variable then P(Xx)1xE(X;Xx),x(0,)

Details:

The modified version has essentially the same elegant proof as the original. Clearly x1(Xx)X1(Xx),x(0,) Taking expected values through the inequality gives xP(Xx)E(X;Xx). Dividing both sides by x gives the result (and it is at this point that we need x>0.).

So Markov's inequality gives an upper bound on the probability that X exceeds a given positive value x, in terms of a monent of X. Now let's return to our stochastic process X={Xt:tT}. To simplify the notation, let Tt={sT:st} for tT. Here is the main definition:

For the process X, define the corresponding maximal process U={Ut:tT} by Ut=sup{Xs:sTt},tT

Clearly, the maximal process is increasing, so that if s,tT with st then UsUt. A trivial application of Markov's inequality above would give P(Utx)1xE(Ut;Utx),x>0 But when X is a sub-martingale, the following theorem gives a much stronger result by replacing the first occurrent of Ut on the right with Xt. The theorem is known as Doob's sub-martingale maximal inequality (or more simply as Doob's inequaltiy), named once again for Joseph Doob who did much of the pioneering work on martingales. A sub-martingale has an increasing property of sorts in the sense that if s,tT with st then E(XtFs)Xs, so it's perhaps not entirely surprising that such a bound is possible.

Suppose that X is a sub-martingale. For tT, let Ut=sup{Xs:sTt}. Then P(Utx)1xE(Xt;Utx),x(0,)

Details:

Proof in the discrete time: So T=N and the maximal process is given by Un=max{Xk:kNn} for nN. Let x(0,), and define τx=min{kN:Xkx} where as usual, min()=. The random time τx is a stopping time relative to F. Moreover, the processes {Un:nN} and {τx:x(0,)} are inverses in the sense that for nN and x(0,), Unx if and only if τxn We have seen this type of duality before—in the Poisson process and more generally in renewal processes. Let nN. First note that E(Xτxn)=E(Xτxn;τxn)+E(Xτxn;τx>n) If τxn then Xτxn=Xτxx. On the other hand if τx>n then Xτxn=Xn. So we have E(Xτxn)xP(τxn)+E(Xn;τx>n)=xP(Utx)+E(Xn;τx>n) Similarly, E(Xn)=E(Xn;τxn)+E(Xn;τx>n)=E(Xn;Utx)+E(Xn;τx>n) But by the optional stopping theorem, E(Xτxn)E(Xn). Hence we have xP(Utx)+E(Xn;τx>n)E(Xn;Utx)+E(Xn;τx>n) Subtracting the common term and then dividing both sides by x gives the result

Proof in continuous time: For kN, let Dk+={j/2k:jN} denote the set of nonnegative dyadic rationals (or binary rationals) of rank k or less. For t[0,) let Ttk=(Dk+[0,t]){t}, so that Ttk is the finite set of such dyadic rationals that are less than t, with t added to the set. Note that Ttk has an ordered enumeration, so Xk={Xs:sTtk} is a discrete-time sub-martingale for each kN. Let Utk=sup{Xs:sTtk} for kN. Note that TtjTtk[0,t] for t[0,) and for j,kN with j<k and therefore UtjUtkUt. It follows that for x(0,), {Utjx}{Utkx}{Utx} The set D+ of all nonnegative dyadic rationals is dense in [0,) and so since X is right continuous and has left limits, it follows that if Utx then Utkx for some kN. That is, we have {Utx}=k=0{Utkx} The maximal inequality applies to the discrete-time sub-martingale Xk and so P(Utkx)1xE(Xt;Utkx) for each kN. By the monotone convergence theorem, the left side converges to P(Utx) as k and the right side converges to E(X;Utx) as k.

There are a number of simple corollaries of the maximal inequality. For the first, recall that the positive part of xR is x+=x0, so that x+=x if x>0 and x+=0 if x0.

Suppose that X is a sub-martingale. For tT, let Vt=sup{Xs+:sTt}. Then P(Vtx)1xE(Xt+;Vtx),x(0,)

Details:

Recall that since X is a sub-martingale and xx+ is increasing and convex, X+={Xt+:tT} is also a sub-martingale. Hence the result follows from the general maximal inequality for sub-martingales.

As a further simple corollary, note that P(Vtx)1xE(Xt+),x(0,) This is sometimes how the maximal inequality is given in the literature.

Suppose that X is a martingale. For tT, let Wt=sup{|Xs|:sTt}. Then P(Wtx)1xE(|Xt|;Wtx),x(0,)

Details:

Recall from the basic properties that since X is a martingale, and x|x| is convex, |X|={|Xt|:tT} is a sub-martingale. Hence the result follows from the general maximal inequality for sub-martingales.

Once again, a further simple corollary is P(Wtx)1xE(|Xt|),x(0,) Next recall that for k(1,), the k-norm of a real-valued random variable X is Xk=[E(|X|k)]1/k, and the vector space Lk consists of all real-valued random variables for which this norm is finite. The following theorem is the norm version of the Doob's maximal inequality.

Suppose again that X is a martingale. For tT, let Wt=sup{|Xs|:sTt}. Then for k>1, Wtkkk1Xtk

Details:

Fix tT. If E(|Xt|k)=, the inequality trivial holds, so assume that E(|Xt|k)<, and thus that XtLk. The proof relies fundamentally on Hölder's inequality, and for that inequality to work, we need to truncate the variable Wt and consider instead the the bounded random variable Wtc where c(0,). First we need to show that P(Wtcx)1xE(|Xt|;Wtcx),x(0,) If c<x, both sides are 0. If cx, {Wtcx}={Wtx} and so from the maximal inequality [5], P(Wtcx)=P(Wtx)1xE(|Xt|;Wtx)=E(|Xt|;Wtcx) Next recall from the properties that Wtckk=E[(Wtc)k]=0kxk1P(Wtcx)dx Applying the inequality gives E[(Wtc)k]0kxk2E[|Xt|;Wtcx]dx By Fubini's theorem we can interchange the expected value and the integral which gives E[(Wtc)k]E[0Wtckxk2|Xt|dx]=kk1E[|Xt|(Wtc)k1] But XtLk and (Wtc)k1Lj where j=k/(k1) is the exponent conjugate to k. So an application of Hölder's inequality gives Wtckkkk1Xtk(Wtc)k1j=kk1XtkWtckk1 where we have used the simple fact that (Wtc)k1j=Wtckk1. Dividing by this factor gives Wtckkk1Xtk Finally, WtckWtk as c by the monotone convergence theorem. So letting c in the last displayed equation gives Wtkkk1Xtk

Once again, W={Wt:tT} is the maximal process associated with |X|={|Xt|:tT}. As noted in the proof, j=k/(k1) is the exponent conjugate to k, satisfying 1/j+1/k=1. So this version of the maximal inequality states that the k norm of the maximum of the martingale X on Tt is bounded by j times the k norm of Xt, where j and k are conjugate exponents. Stated just in terms of expected value, rather than norms, the Lk maximal inequality is E(|Wt|k)(kk1)kE(|Xt|k) Our final result in this discussion is a variation of the maximal inequality for super-martingales.

Suppose that X={Xt:tT} is a nonnegative super-martingale, and let U=sup{Xt:tT}. Then P(Ux)1xE(X0),x(0,)

Details:

Let Yt=Xt for tT. Since X is a super-martingale, Y is a sub-martinagle. And since X is nonnegative, Yt+=Xt for tT. Let Ut=sup{Xs:sTt}=sup{Ys+:sTt} for tT. By the maximal inequality for sub-martingales, and since X is a super-martingale we have for tT, P(Utx)1xE(Yt+)=1xE(Xt)1xE(X0),x(0,) Next note that UtU as t. Let x(0,) and ϵ(0,x). If Ux then Utxϵ for sufficiently large tT. Hence {Ux}k=1{Ukxϵ} Using the continuity theorem for increasing events, and our result above we have P(Ux)limkP(Ukxϵ)1xϵE(X0) Since this holds for all ϵ(0,x), it follows that P(Ux)1xE(X0).

The Up-Crossing Inequality

The up-crossing inequality gives a bound on how much a sub-martingale (or super-martingale) can oscillate, and is the main tool in the martingale convergence theorems that will be studied in the next section. It should come as no surprise by now that the inequality is due to Joseph Doob. We start with the discrete-time case.

Suppose that x=(xn:nN) is a sequence of real numbers, and that a,bR with a<b. Define t0(x)=0 and then recursively define sk+1(x)=inf{nN:ntk(x),xna},kNtk+1(x)=inf{nN:nsk+1(x),xnb},kN

  1. The number of up-crossings of the interval [a,b] by the sequence x up to time nN is un(a,b,x)=sup{kN:tk(x)n}
  2. The total number of up-crossings of the interval [a,b] by the sequence x is u(a,b,x)=sup{kN:tk(x)<}
Details:

As usual, we define inf()=. Note that if tk(x)< for kN+, then (xn:n=sk(x),tk(x)) is the kth up-crossing of the interval [a,b] by the sequence x.

So informally, as the name suggests, un(a,b,x) is the number of times that the sequence (x0,x1,,xn) goes from a value below a to one above b, and u(a,b,x) is the number of times the entire sequence x goes from a value below a to one above b. Here are a few of simple properties:

Suppose again that x=(xn:nN) is a sequence of real numbers and that a,bR with a<b.

  1. un(a,b,x) is increasing in nN.
  2. un(a,b,x)u(a,b,x) as n.
  3. If c,dR with a<c<d<b then un(c,d,x)un(a,b,x) for nN, and u(c,d,x)u(a,b,x).
Details:
  1. Note that {kN:tk(x)n}{kN:tk(x)n+1}.
  2. Note that n=0{kN:tk(x)n}={kN:tk(x)}.
  3. Every up-crossing of [a,b] is also an up-crossing of [c,d].

The importance of the definitions is found in the following theorem. Recall that R=R{,} is the set of extended real numbers, and Q is the set of rational real numbers.

Suppose again that x=(xn:nN) is a sequence of real numbers. Then limnxn exists in R is and only if u(a,b,x)< for every a,bQ with a<b.

Details:

We prove the contrapositive. Note that the following statements are equivalent:

  1. limnxn does not exist in in R.
  2. lim infnxn<lim supnxn.
  3. There exists a,bQ with a<b and with xna for infinitely many nN and xnb for infinitely many nN.
  4. There exists a,bQ with a<b and u(a,b,x)=.

Clearly [10] is true with Q replaced with R, but the countability of Q will be important in the martingale convergence theorem. As a simple corollary, if x is bounded and u(a,b,x)< for every a,bQ with a<b, then x converges in R. The up-crossing inequality for a discrete-time martingale X gives an upper bound on the expected number of up-crossings of X up to time nN in terms of a moment of Xn.

Suppose that X={Xn:nN} satisfies the basic assumptions with respect to the filtration F={Fn:nN}, and let a,bR with a<b. Let Un=un(a,b,X), the random number of up-crossings of [a,b] by X up to time nN.

  1. If X is a super-martingale relative to F then E(Un)1baE[(Xna)]1ba[E(Xn)+|a|]1ba[E(|Xn|)+|a|],nN
  2. If X is a sub-martingale relative to F then E(Un)1baE[(Xna)+]1ba[E(Xn+)+|a|]1ba[E(|Xn|)+|a|],nN
Details:

In the context definition [8], let σk=sk(X) and τk=tk(X). These are the random times that define the up-crossings of X. Let Yk=XτknXσkn and then define Zn=k=1nYk. To understand the sum, let's take cases for the kth term Yk:

Hence Zn(ba)Un+(Xna)1(σUn+1n) and so (ba)UnZn(Xna)1(σUn+1n) Next note that σkn and τkn are bounded stopping times and of course σknτkn.

  1. If X is a super-martingale, it follows from the optional stopping theorem that E(Yk)=E(Xτkn)E(Xσkn)0 and therefore E(Zn)0. Finally, (Xna)1(σUn+1n)(Xna). Taking expected values gives (ba)E(Un)E(Zn)+E[(Xna)]E[(Xna)] The remaining parts of the inequality follow since (xa)x+|a||x|+|a| for xR.

The process Z={Zn:nN} in the proof can be viewed as a transform of X={Xn:nN} by a predictable process. Specifically, for nN+, let In=1 if σk<nτk for some kN, and let In=0 otherwise. Since σk and τk are stopping times, note that {In=1}Fn1 for nN+. Hence the process I={In:nN+} is predictable with respect to F. Moreover, the transform of X by I is (IX)n=j=1nIj(XjXj1)=k=1n(XτknXσkn)=Zn,nN Since I is a nonnegative process, if X is a martingale (sub-martingale, super-martingale), then IX is also a martingale (sub-martingale, super-martingale).

Of course if X is a martingale with respect to F then both inequalities apply. In continuous time, as usual, the concepts are more complicated and technical.

Suppose that x:[0,)R and that that a,bR with a<b.

  1. If I[0,) is finite, define t0I(x)=0 and then recursively define sk+1I(x)=inf{tI:ttkI(x),xta},kNtk+1I(x)=inf{tI:tsk+1I(x),xtb},kN The number of up-crossings of the interval [a,b] by the function x restricted to I is uI(a,b,x)=sup{kN:tkI(x)<}
  2. If I[0,) is infinte, the number of up-crossings of the interval [a,b] by x restricted to I is uI(a,b,x)=sup{uJ(a,b,x):J is finite and JI}

To simplify the notation, we will let ut(a,b,x)=u[0,t](a,b,x), the number of up-crossings of [a,b] by x on [0,t], and u(a,b,x)=u[0,)(a,b,x), the total number of up-crossings of [a,b] by x. In continuous time, the definition of up-crossings is built out of finte subsets of [0,) for measurability concerns, which arise when we replace the deterministic function x with a stochastic process X. Here are the simple properties that are analogous to our previous ones.

Suppose again that x:[0,)R and that a,bR with a<b.

  1. If I,J[0,) with IJ, then uI(a,b,x)uJ(a,b,x).
  2. If (In:nN) is an increasing sequence of sets in [0,) and J=n=0In then uIn(a,b,x)uJ(a,b,x) as n.
  3. If c,dR with a<c<d<b and I[0,) then uI(c,d,x)uI(a,b,x).
Details:
  1. The result follows easily from the definitions if I is finite (and J either finite or infinite). If I is infinite (and hence so is J), note that {uK(a,b,x):K is finite and KI}{uK(a,b,x):K is finite and KJ}
  2. Since In is increasing in nN (in the subset partial order), note that if K[0,) is finite, then KJ if and only if KIn for some nN.
  3. Every up-crossing of [a,b] is an up-crossing of [c,d].

The following result is the reason for studying up-crossings in the first place. Note that the definition built from finite set is sufficient.

Suppose that x:[0,)R. Then limtxt exists in R if and only if u(a,b,x)< for every a,bQ with a<b.

Details:

As in the discrete-time case, we prove the contrapositive. The proof is almost the same: The following statements are equivalent:

  1. limtxt does not exist in in R.
  2. lim inftxt<lim suptxt.
  3. There exists a,bQ with a<b and there exists sn,tn[0,) with xsna for nN and xtnb for nN.
  4. There exists a,bQ with a<b and u(a,b,x)=.

Finally, here is the up-crossing inequality for martingales in continuous time. Once again, the inequality gives a bound on the expected number of up-crossings.

Suppose that X={Xt:t[0,)} satisfies the basic assumptions with respect to the filtration F={Ft:t[0,)}, and let a,bR with a<b. Let Ut=ut(a,b,X), the random number of up-crossings of [a,b] by X up to time t[0,).

  1. If X is a super-martingale relative to F then E(Ut)1baE[(Xta)]1ba[E(Xt)+|a|]1ba[E(|Xt|)+|a|],t[0,)
  2. If X is a sub-martingale relative to F then E(Ut)1baE[(Xta)+]1ba[E(Xt+)+|a|]1ba[E(|Xt|)+|a|],t[0,)
Details:

Suppose that X is a sub-martingale; the proof for a super-martingale is analogous. Fix t[0,) and a,bR with a<b. For I[0,) let UI=uI(a,b,X), the number of up-crossings of [a,b] by X restricted to I. Suppose that I is finite and that tI is the maximum of I. Since X restricted to I is also a sub-martingale, the discrete-time up-crossing theorem applies and so E(UI)1baE[(Xta)+] Since Ut=sup{UI:I is finite and I[0,t]}, there exists finite In for nN with UInUt as n. In particular, Ut is measurable. By property (a) in [13], there exists such a sequence with In increasing in n and tIn for each nN. By the monotone convergence theorem, E(UIn)E(Ut) as n. So by the displayed equation above, E(Ut)1baE[(Xta)+]

Examples and Applications

Kolmogorov's Inequality

Suppose that X={Xn:nN+} is a sequence of independent variables with E(Xn)=0 and var(Xn)=E(Xn2)< for nN+. Let Y={Yn:nN} be the partial sum process associated with X, so that Yn=i=1nXi,nN From the introduction we know that Y is a martingale. A simple application of the maximal inequality gives the following result, which is known as Kolmogorov's inequality, named for Andrei Kolmogorov.

For nN, let Un=max{|Yi|:iNn}. Then P(Unx)1x2var(Yn)=1x2i=1nE(Xi2),x(0,)

Details:

As noted above, Y is a martingale. Since the function xx2 on R is convex, Y2={Yn2:nN} is a sub-martingale. Let Vn=max{Yi2:iNn} for nN, and let x(0,). Applying the maximal inequality for sub-martingales we have P(Unx)=P(Vnx2)1x2E(Yn2)=1x2var(Yn) Finally, since X is an independent sequence, var(Yn)=i=1nvar(Xi)=i=1nE(Xi2)

Red and Black

In the game of red and black, a gambler plays a sequence of Bernoulli games with success parameter p(0,1) at even stakes. The gambler starts with an initial fortune x and plays until either she is ruined or reaches a specified target fortune a, where x,a(0,) with x<a. When p12, so that the games are fair or unfair, an optimal strategy is bold play: on each game, the gambler bets her entire fortune or just what is needed to reach the target, whichever is smaller. In the section on bold play we showed that when p=12, so that the games are fair, the probability of winning (that is, reaching the target a starting with x) is x/a. We can use the maximal inequality for super-martingales to show that indeed, one cannot do better.

To set up the notation and review various concepts, let X0 denote the gambler's initial fortune and let Xn denote the outcome of game nN+, where 1 denotes a win and 1 a loss. So {Xn:nN} is a sequence of independent variables with P(Xn=1)=p and P(Xn=1)=1p for nN+. (The initial fortune X0 has an unspecified distribution on (0,).) The gambler is at a casino after all, so of course p12. Let Yn=i=0nXi,nN so that Y={Yn:nN} is the partial sum process associated with X={Xn:nN}. Recall that Y is also known as the simple random walk with parameter p, and since p12, is a super-martingale. The process {Xn:nN+} is the difference sequence associated with Y. Next let Zn denote the amount that the gambler bets on game nN+. The process Z={Zn:nN+} is predictable with respect to X={Xn:nN}, so that Zn is measurable with respect to σ{X0,X1,,Xn1} for nN+. So the gambler's fortune after n games is Wn=X0+i=1nZiXi=X0+i=1nZi(YiYi1) Recall that W={Wn:nN} is the transform of Z with Y, denoted W=ZY. The gambler is not allowed to go into debt and so we must have ZnWn1 for nN+: the gambler's bet on game n cannot exceed her fortune after game n1. What's the probability that the gambler can ever reach or exceed the target a starting with fortune x<a?

Let U=sup{Wn:nN}. Suppose that x,a(0,) with x<a and that X0=x. Then P(Ua)xa

Details:

Since Y is a super-martingale and Z is nonnegative, the transform W=ZY is also a super-martingale. By [5]: P(Ua)1aE(W0)=xa

Note that the only assumptions made on the gambler's sequence of bets Z is that the sequence is predictable, so that the gambler cannot see into the future, and that gambler cannot go into debt. Under these basic assumptions, no strategy can do any better than bold play. However, there are strategies that do as well as bold play; these are variations on bold play.

Open the simulation of the bold play and set p=12. Play the game with various values of initial and target fortunes.