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.