Markov bound for super-martingales

For any non-negative super-martingale, the probability that it ever exceeds its initial value by a factor of is at most .

Alice goes to the casino with $1. At the casino, she plays the following game repeatedly: she bets half her current balance on a fair coin flip. (For example, on the first flip, she bets 50 cents, so she wins 50 cents with probability 1/2 and loses 50 cents with probability 1/2.) Will Alice’s winnings ever reach$10 or more? The bound here says this happens with probability at most 1/10.

Markov bound for super-martingales

Let be a non-negative super-martingale — a sequence of non-negative random variables that is non-increasing in expectation: , and for each .

Lemma (Markov for super-martingales).

(a) The event occurs with probability at most .
(b) The event occurs with probability strictly less than .

Proof idea

Here’s a seemingly weaker bound: if is any stopping time with finite expectation, then, by Wald’s equation, is at most , so by Markov, is at most . That is, the desired bound holds for the single value .

The idea of the proof of the stronger bound (in the lemma) is to use exactly this argument, with defined to be the first time such that . (Thus, if the inequality fails for any , it fails for this . This is analogous to Alice quitting as soon as her winnings exceed the threshold.) This is indeed a stopping time. A technicality is that this might not have finite expectation. The proof work around this using a limit argument.

Pessimistic estimator

(a) Given the value at the current time , as long as the bad event has not yet happened (that is, as long as ), the value is a pessimistic estimator for the conditional probability of the event . The value is initially , it is non-increasing in expectation with each step, and, as long as it remains less than 1, the event in question doesn’t happen.

(b) The same is a pessimistic estimator for the event in part (b): the value is initially , it is non-increasing in expectation with each step, and, as long as it remains less than or equal to 1, the event in question doesn’t happen.