Ville's inequality

Let $M=(M_t)$ be a $P$-supermartingale. Ville’s inequality is a time-uniform version of Markov’s inequality (basic inequalities:Markov’s inequality), stating that

$$\mathbb{P}(\exists t\ge 1:M_t\ge x)\le \frac{\mathbb{E}[M_1]}{x},$$

for all $x>0$. Note this bound is uniform over all time. If we take $x=1/\alpha$, then this says that the probability that $M$ will ever exceed $1/\alpha$ is at most $\mathbb{E}[M_1]/x$.

Ville’s inequality can also be written as

$$\forall \tau :\mathbb{P}(M_{\tau }\ge x)\le \frac{\mathbb{E}[M_1]}{x},$$

where $\tau$ represents a stopping-time. This is what enables statistical inference procedures based on Ville’s inequality to be valid at arbitrary stopping times (which are data dependent).

Ville’s inequality also holds for an e-process, since they are upper bounded by a test-martingale. The composite generalization of Ville’s inequality actually requires the notion of an e-process, and reads

$$\underset{P\in \mathcal{P}}{\sup }\mathbb{P}(\exists t\ge 1:E_t\ge 1/\alpha )\le \alpha ),$$

if $(E_t)$ is an e-process for $\mathcal{P}$. Ville’s inequality has also been extended to nonintegrable processes.

Ville’s inequality also implies the classical result that a nonnegative supermartingale will reach infinity with probability 0. Let $(M_t)$ be a nonnegative supermartingale and define the event $A_k=\{{\sup }_t{M}_t\ge 2^k\}$. By Ville, $\mathbb{P}(A_k)\le 2^{-k}\mathbb{E}[M_1]$. Since the events $(A_k)$ are monotonically decreasing, i.e., $A_{k+1}\subset A_k$ for all $k$, we have

$$\mathbb{P}(\underset{t}{\sup }{M}_t=\infty )=\mathbb{P}({\cap }_{k\ge 1}{A}_k)=\underset{k}{\lim }\mathbb{P}(A_k)=\underset{k}{\lim }{2}^{-k}\mathbb{E}[M_1]=0.$$

Much of game-theoretic statistics, and sequential hypothesis testing in particular, relies on Ville’s inequality, where we often construct some test-martingale or e-process under the null. Ville’s implies that this process is unlikely to ever become large. Thus, if it does became large, this is evidence against the null.