Betting on "Fair Games": A Simple Guide to Martingales and Stopping Times

Margtingale is always right!

Stopping times are a core concept in martingale theory because they define when a "fair game" can end. Unlike deterministic times, a stopping time is a random variable whose value depends only on the information available up to that moment. It cannot "look into the future." This property is fundamental to proving deep results about martingales, which are processes modeling these fair games. The following theorems are cornerstones of this theory.

The Optional Sampling/Stopping Theorem

The optional sampling theorem, also called the optional stopping theorem, asserts that if you have a martingale and halt the process at a specific, well-defined stopping time, the expected value at that stopping time matches its initial expected value.

This theorem underpins the intuitive notion that no gambling strategy can alter your long-term average result in a fair game. You can decide to stop playing at any moment—such as when you've doubled your money or gone broke—but on average, you will end up with the same amount of money you began with.

However, the theorem is valid only under certain conditions regarding the stopping time. For example, the stopping time must be almost surely bounded, or the process must have bounded increments. A classic scenario where the theorem does not apply is a gambler who continues playing until they win $1, even if it takes an infinite amount of time. Here, the stopping time is unbounded, and the expected value at the stopping time is $1, not the initial $0.

Doob's Maximal Inequalities

Doob's maximal inequalities offer an upper limit on the likelihood that a martingale will surpass a certain value at any point up to a specified time. They connect the maximum value a martingale can achieve with its final value.

This inequality is a valuable tool for demonstrating convergence theorems for martingales. It essentially indicates that if the final expected value of a non-negative submartingale is finite, the probability of it ever becoming very large is also small.

Doob's Upcrossing Lemma

The upcrossing lemma is an essential technical result that plays a key role in establishing the martingale convergence theorems. It connects the expected number of times a martingale "upcrosses" an interval with the change in its expected value.

An upcrossing of an interval [a,b] occurs when the process moves from a value below a to a value above b. The lemma asserts that for a submartingale Xn and an interval [a,b], the expected number of upcrossings of [a,b] is limited by a term associated with the final expected value of the process.

The importance of this result lies in its implication that if a martingale is bounded in some manner (such as having a bounded expected absolute value), it can only upcross any given interval a finite number of times. This consequently means the process must converge to a finite limit almost surely. This lemma is a fundamental part of the proof of the Doob's martingale convergence theorems.