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, for any $t_0$,

$$\mathbb{P}(\exists t\ge t_0:M_t\ge x)\le \frac{\mathbb{E}[M_{t_0}]}{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.

Reverse Ville

There is also a reverse-time Ville’s inequality which holds for nonnegative reverse submartingales. If $(R_t)$ is a reverse submartingale with respect to a reverse filtration, then for all $t_0$,

$$\mathbb{P}(\exists t\ge t_0:R_t>1/\alpha )\le \alpha \mathbb{E}[R_{t_0}].$$

Proof of Ville

Define the stopping-time $\tau =\inf \{t\in \mathbb{N}\cup \{\infty \}:M_t\ge 1/\alpha \}$. The optional stopping theorem (which says that $\mathbb{E}{M}_{\tau }\le \mathbb{E}{M}_0$) gives

$$1\ge \mathbb{E}{M}_0\ge \mathbb{E}{M}_{\tau }\ge \mathbb{E}[M_{\tau }1\{\tau <\infty \}]\ge \frac{1}{\alpha }\mathbb{E}1\{\tau <\infty \},$$

since $M_{\tau }\ge 1/\alpha$ by construction. Noting that $\mathbb{E}1\tau <\infty =\mathbb{P}({\sup }_t{M}_t\ge 1/\alpha )$ concludes the proof.