The Optional Stopping Theorem

Someone once asked my what my favourite theorem was. This seemed an odd question. I sort of blustered and said “bluh, uh, optional stopping?”, although later wondered if I should have gone for max-flow min-cut.

Sometime later, I decided to make a blog. “Optional Stopping” seemed to be a terribly good title for two reasons: 1) because it is Officially My Favourite Theorem, and 2) because it’s hi-lar-ious pun on the fact that I only write blog posts when I’m bored with doing proper work. Optional stopping. I choose to stop work. Geddit? Oh, never mind.

So, in case you don’t know, It thought this would be a good opportunity to explain what the optional stopping theorem is.

In this article, we look at stopping times, martingales and the OST itself, before giving a couple of (I think) nifty applications to random walks.

Apparatus

Martingales

OK. Let’s say I come over, and you’re playing a card game. You’ve been playing for a while, and have got £M(n) in your kitty. If this is a fair game, I would expect you to have, on average, the same amount after the next go. You might be lucky and win some, you might be unlucky and lose some, but on average – if it’s a fair game – you will have the same, no matter how you got the £M(n) in the first place. In maths, this is

…(1)

A random sequence (M(0), M(1), M(2), …) satisfying (1) is called a martingale.

By taking the expectation of both sides of (1) for each n, we get

…(2)

If your conditional expectation isn’t up to that, think about the fair game: we expect to neither lose nor gain money, which is exactly what this says.

Stopping time

A stopping time is an integer valued random variable dependent on the sequence (M(n)) such that you know when you’ve got there. So for instance “when you first have £10″ or “after 3 hours” are both stopping times, as is “when you either have £10 or after 3 hours, which ever is first”. You just keep an eye on your kitty and your watch, and as soon as you either have £10 or the clock strikes three, you can stop and walk away. “Just before you first lose money” isn’t a stopping time – by the time you know you’re there, you’ve already lost the money and it’s too late.

So a stopping time is any time when you can decide to cash in your chips and go home.

But looking at (2), we might ask “when can we replace n with a random time T to get ?” The optional stopping theorem tells us when.

The theorem

Optional stopping theorem. Let (M(n)) be a martingale and T a stopping time. Then if one of the following holds:

a) T is bounded,

b) second thing,

c) third thing.

The proof is not to difficult – it rests upon showing that (M(max(n,T)) is still a martingale – but I’ll spare you the details. The full proof will be in any text book that covers martingales; my favourite is Probability with Martingales by David Williams. You can also find them in Grégory Miermont’s Advanced Probability notes from the University of Cambridge.

Applications

More to come…