Lemme: Soit $X$ variable aléatoire réelle, bornée presque sûrement par 1, centrée.
Alors: $\forall t\in\mathbf{R}, \mathbf{E}[exp(tX)]\leq exp(\frac{t^2}{2})$.
Théorème: (inégalité de Hoeffding) Soit $(X_n)_{n\in\mathbf{N}}$ suite de variables aléatoires réelles indépendantes, centrées, presque sûrement bornées: $\forall n\in\mathbf{N}, \exists c_n>0\ | X_n| \leq c_n$. Soit $(S_n = \sum ^n_{j=1} X_j)_{n\in\mathbf{N}}$.
Alors: $\forall n\in\mathbf{N}, \forall \epsilon >0, \mathbf{P}(| S_n| > \epsilon)\leq 2exp(-\frac{\epsilon^2}{2\sum^n_{j=1} c_j^2})$.
Application n°1: Soit $(X_i)_{i=1}^n$ variables aléatoires iid de loi $\mathcal{B}(1;p)$ avec $p\in ]0;1[$, soit $\alpha\in ]0;1[$.
Alors: un intervalle de confiance par excès de niveau $1-\alpha$ du paramètre $p$ est: $[\frac{1}{n}S_n-\sqrt{\frac{2}{n}ln(\frac{2}{\alpha})} ; \frac{1}{n}S_n+\sqrt{\frac{2}{n}ln(\frac{2}{\alpha})}]$.
Application n°2: Soit $\alpha\in\mathbf{R}^*_+$ et $\beta\in\mathbf{R}^*_+$ tels que: $\forall n\in\mathbf{N}, \sum ^n_{k=1} c_k^2\leq n^{2\alpha - \beta}$.
Alors: $(\frac{S_n}{n^\alpha})$ tend presque sûrement vers $0$.