Markov bound for super-martingales

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

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 X_0,X_1,X_2,\ldots be a non-negative super-martingale — a sequence of non-negative random variables that is non-increasing in expectation: \textrm{E}[X_ t\, |\, X_{t-1}] \le X_{t-1}, and X_ t \ge 0 for each t.

Lemma (Markov for super-martingales).

 
(a) The event \exists t.~ X_ t \ge c\, X_0 occurs with probability at most 1/c.
(b) The event \exists t.~ X_ t \gt c\, X_0 occurs with probability strictly less than 1/c.

Proof idea

Here’s a seemingly weaker bound: if T is any stopping time with finite expectation, then, by Wald’s equation, \textrm{E}[X_ T] is at most X_0, so by Markov, \Pr [X_ T \ge c\, X_0] is at most 1/c. That is, the desired bound holds for the single value X_ T.

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

Proof

Pessimistic estimator

(a) Given the value X_{t} at the current time t, as long as the bad event has not yet happened (that is, as long as \forall s \lt t. ~ X_ s \lt c X_0), the value \phi _ t = X_ t/(c X_0) is a pessimistic estimator for the conditional probability of the event \exists t.~ X_ t \ge c X_0. The value is initially 1/c, 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 \phi _ t is a pessimistic estimator for the event in part (b): the value is initially 1/c, 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.

MathJax is loading, equations are not yet displayed...