# Verify the Optimal Stopping Theorem

First a definition:

• Theorem: Let $$\{ M_n, n \ge 0 \}$$ be a martingale. Suppose the the stopping time T is bounded, that is $$T \le k$$, then, $$E[M_T] = E[M_0]$$.

• Optimal Stopping Theorem: Suppose that $$\{M_n, n \ge 0 \}$$ is a martingale, and T is a stopping time. If all 3 conditions hold:

1. $$E[T] < \infty$$

2. $$E[|M_T|] < \infty$$

3. $$\lim \limits_{n \to \infty} E\Big[|M_n|~I_{\{T>n\}} \Big]=0$$

Then, $$E[M_T] = E[M_0]$$

Problem: Verify the Optional Stopping Theorem:

So the workbook gives the solution to the problem as follows:

Consider the stopping time:

$$T_n = \text{min}\{T, n\}\tag{1}$$

Note that:

$$M_T = M_{T_n} + M_T~I_{\{T>n\}} - M_n~ I_{\{T>n\}}\tag{2}$$

Hence:

$$E[M_T] = E[M_{T_n}] + E[M_T~ I_{\{T>n\}}] - E[M_n~ I_{\{T>n\}}]\tag{3}$$

Since, $$T_n$$ is a bounded stopping time, we have:

$$\boxed{E[M_{T_n}] = E[M_0]}\tag{4}$$

Further, we need to verify Conditions (1), (2), and (3) of the Optimal Stopping.

Condition 1: of Optimal stopping theorem say that: $$E[T] < \infty$$

Condition 2: of Optimal stopping theorem say that: $$E[|M_T|] < \infty$$

Condition 3: of Optimal Stopping theorem says that: $$\lim \limits_{n \to \infty} E[|M_n|~I_{\{T>n\}}] = 0$$

For condition 1, T is a finited bounded stopping time. Thus condition 1 is satisfied.

For condition 2, $$\lim \limits_{n \to \infty} \Pr(T > 0) = 0$$, then $$E[|M_T|] < \infty$$. Thus, condition 2 is satisfied.

For condition 3, we have $$\lim \limits_{n \to \infty} (|M_T|~I_{\{T > n\}}=0$$, Hence, condition 2 is satisfied.

Therefore: $$E[M_t] = E[M_0]$$

QUESTION: could somebody please translate the syntax from equations (1), (2), and (3) above into a plain English explanation so that i can understand it.

\begin{aligned}(T_n &= \text{min}\{T, n\} \\ M_T &= M_{T_n} + M_T~I_{\{T>n\}} - M_n~ I_{\{T>n\}} \\ E[M_T] &= E[M_{T_n}] + E[M_T~ I_{\{T>n\}}] - E[M_n~ I_{\{T>n\}}]\\E[M_{T_n}] &= E[M_0]\end{aligned}

(Anyways... this is the last problem in the chapter, and then i will never see it again... just wanted to finish it for the sake of completion)

• So is $T$ constant?
– Alex
Commented Aug 16, 2020 at 13:06
• @Alex T is the stop time. You could think of T as a random variable that indicates the step at which the game ends. Of course, you don't know the value of T until the game ends. The game consists of many Win/Loss matches, and you get a different T stop time when the game ends because you have no money or all of the money after playing several rounds. One game T could equal 9, the next game T could equal 15, for example.
– pico
Commented Aug 16, 2020 at 13:34
• The syntax on this problem is driving me a little crazy... somewhere there needs to be a Rosetta stone.
– pico
Commented Aug 16, 2020 at 13:51
• Also, if I understand correctly, $M_T$ is the amount of money the player has at stopping time T? Which would need to be zero, or all of the money. Is that a correct interpretation correct?
– pico
Commented Aug 16, 2020 at 13:53
• Writing answer, request you to wait. Commented Aug 16, 2020 at 14:43

## 1 Answer

I think I understand your question. You just want, in the context of playing a chance game like a slot machine, the result and the proof of the optional stopping theorem. Most of this explanation below is a wordy explanation of that, as you demand.

What is the optional stopping theorem, first of all? See, it is like this : imagine you are playing a game of chance (which is a sequence of stages where you do something, and then either win money or lose money) where in each stage, your expected gain or loss from the previous stage is nil. That (with a few conditions missing, but key idea captured) is a martingale.

Example : You start with $$100$$ dollars, and conduct independent (fair) coin flips, where for each coin flip that is heads you get $$1$$ dollar, and if tails you lose $$1$$ dollar. Then this is a martingale, because , at each stage, the chance of gaining a dollar is $$\frac 12$$, and that of losing a dollar is $$\frac 12$$, so the expected gain or loss is nil. Note that if, for example you gained $$2$$ dollars instead of $$1$$ if the coin fell heads, then you would not get a martingale this way, but turns out some adjustment of that works.

Now, the point is this : imagine you wanted to get money by playing the game above. It feels like a complete game of chance, because there's no strategy. But there is something : imagine you could predict the future, at least for a short while. Then, stopping strategies can be made : these are rules that tell you when to stop gambling (and are called stopping times, formally). For example, you might say : "Ah, let me get to a point where I see $$10$$ straight heads in front of me. I would then play exactly $$10$$ turns and quit, content with what I have and I don't want to lose more". Or, keep it simpler : "I'll get to $$110$$ and then quit".

However, you can't predict the future (so the first strategy "should not work"), and the second strategy doesn't make sense, otherwise everybody would use it and get rich. The optional stopping theorem basically tells you the following : it tells you that there's no "reasonable strategy" that can make you win money. By reasonable, basically the three conditions of the Optional stopping theorem.

To see this, look at the conclusion of the optional stopping theorem. $$M_T$$ is what you have when you stop, and $$M_0$$ is your initial beginning. The conclusion is then that the expected gain or loss, whenever you use a reasonable strategy to gamble, is nil. So basically, you can't do anything reasonable that maximizes your chances to win.

Let us now look at the conditions of the stopping strategy. The first and foremost thing, is the condition $$\{T = n\} \in F_n$$, which is to define a stopping time. This tells you, that your stopping time cannot depend upon the future ($$F_n$$ is like "information up till time $$n$$", and $$T= n$$ belonging here basically says "you stopping at the $$n$$th turn better depend upon only what you've seen in the first $$n$$ stages"). Any strategy not following this is not in consideration, even in general (that is, outside the context of the OST).

Now, it turns out that other conditions are required.

For example, your strategy obviously has to end in finite time, so you can walk away after using it, and not wait ad infinitum for the strategy to work! It turns out that the technicality required here is that the chance you proceed beyond a certain stage, reduces at a certain rate with the stage number you are at (By applying Markov's inequality, $$E[T]<\infty$$ means $$P(T > n) < \frac {E[T]}{n}$$ so there is $$\frac 1n$$ decay) .

It turns out that the strategy "wait till you get to $$110$$" falls victim : if you start the game and want to stop with this strategy, you could be "expected" to wait forever! To see this, one can actually calculate $$P(T\geq n)$$ for $$T$$ being the hitting time of $$110$$, and see that $$E[T] = \sum P(T \geq n)$$ is infinite.

You also cannot use strategies which demand too much, i.e. $$E[|M_T|] = \infty$$. Basically, any strategy that guarantees an expected infinite wealth upon stopping, cannot be considered. Note that this provides a decay condition by Markov's inequality : $$P[|M_T| > m] \leq \frac{E[|M_T|]}{m}$$, so this means that the chances of your strategy getting you above a certain amount of money decays at a certain rate with the amount of money you want!

The next condition is this : imagine you are at a certain stage, and your strategy urges you to play beyond it. Then, the amount of money you have at that point, should get smaller, and closer to zero, with the stage. Basically, any strategy should get weaker and weaker(i.e. you should be having lesser and lesser money by proceeding with this strategy) as time proceeds. The strategy "play till you get to $$110$$" again falls foul because as time proceeds your strategy is not any weaker.

Any strategy which follows all these conditions, which we call reasonable, ain't good enough! (But hey, you ain't losing anything, so it ain't bad enough either!)

Proof? Suppose you are following a reasonable strategy. Fix a stage $$n$$, and create a new strategy : you play with the old strategy, but will definitely stop if you hit the $$n$$th stage. This strategy is called $$T_n$$. Equation $$2$$ links the winnings between these strategies.

Either you've stopped before $$n$$ or continue if the strategy $$T$$ tells you to. If you stop before stage $$n$$, you've basically used the strategy $$T_n$$ (because $$T$$ and $$T_n$$ coincide before stage $$n$$),so you've got $$M_{T_n}$$ money. If you go on beyond $$n$$, that means you got to stage $$n$$, at which time you've got $$M_n$$ money, and then with strategy $$T$$ you've got $$M_T$$ money, which is $$M_T - M_n$$ more money than $$M_n$$, the same as $$M_{T_n}$$ because you decided to go beyond. (The indicator is just notation : if what's there in the bracket is true , it's value is $$1$$, else it is $$0$$). This is exactly equation $$2$$ : breaking the winnings of a strategy into whether you stop at stage $$n$$ or stop later. (Note that this is valid for any $$n$$).

Now, taking expectations gives you equation $$3$$. But the point is, expectations should be allowed to be taken! The earlier "win when I reach $$110$$" strategy would fail at this stage, if you were trying the proof for it. Here, the term $$M_T1_{T > n}$$ is just $$110 \mathbf{1}_{T>n}$$, which one checks from the definition of $$T$$ has infinite expectation!

The reason for taking the expectations, is that any strategy like $$T_n$$ that is bounded (in the sense that you will definitely never play beyond some fixed number of stages) has expectation same as initial. In words, this is because you can break this strategy into finitely many "fixed-time-stop-strategies", which are strategies of the form "definitely stop at this time, and at no previous time" (so $$T$$ is a constant), and for these, the martingale property gives you what you need. (Because stopping at a fixed time, say $$N$$, means you earn $$M_N$$ if you stop as per the strategy, but $$E[M_N] = E[M_0]$$).

Now, when expectations are taken, we have the terms $$E[M_T \mathbf 1{T>n}]$$ and $$E[M_n \mathbf 1_{T > n}]$$, which we want to make zero. But then , $$E[|M_T|]$$ is finite, so this means that going on further is not going to aid a rise in your money (by Markov's inequality), and similarly the second one is zero.

Sliding $$n$$ to infinity, $$T$$ starts looking more and more like $$T_n$$ as a strategy, but $$T_n$$ gives no earnings, so neither does $$T$$. (No losings either!).

The whole thing above , in short : the earnings for strategy $$T$$ and for strategy $$T_n$$ can differ only in that proceeding beyond $$n$$ somehow means one is gaining more money upon stopping on expectation. The point is to make $$T$$ look more and more like $$T_n$$ by cutting any advantage one can ever get by going further than $$n$$ for a given $$n$$ : cut both the expectation of the strategy , and cut your gains if you continue to use this strategy, down with time! (The two conditions, one with Markov's inequality).

It turns out there are other conditions for the OST to hold too, which can be explained differently, but that's for another post.