Ville's inequality

In probability theory, Ville's inequality provides an upper bound on the probability that a supermartingale exceeds a certain value. The inequality is named after Jean Ville, who proved it in 1939.{{cite thesis

| first=Jean | last=Ville

| title=Etude Critique de la Notion de Collectif

| year=1939

| url=http://www.numdam.org/item/THESE_1939__218__1_0.pdf

}}

{{cite book

| first=Rick | last=Durrett

| title=Probability Theory and Examples

| edition=Fifth

| year=2019

| publisher=Cambridge University Press

| location=Exercise 4.8.2

}}

{{cite thesis

| first=Steven R. | last=Howard

| title=Sequential and Adaptive Inference Based on Martingale Concentration

| year=2019

}}

{{cite journal

| first=K. P. | last=Choi

| title=Some sharp inequalities for Martingale transforms

| year=1988

| journal=Transactions of the American Mathematical Society

| volume=307

| number=1

| pages=279–300

| doi=10.1090/S0002-9947-1988-0936817-3

| s2cid=121892687

| doi-access=free

}}

The inequality has applications in statistical testing.

Statement

Let $X_0, X_1, X_2, \dots$ be a non-negative supermartingale. Then, for any real number $a > 0,$

: $\operatorname{P} \left[ \sup_{n \ge 0} X_n \ge a \right] \le \frac{\operatorname{E}[X_0]}{a} \ .$