Compteurs probabilistiques

Comment compter informatiquement des objets en très grande quantité ? C'est ce à quoi répond ce développement. On montre que : Soit $\varepsilon >0$ et $\delta > 0$. Il existe $(X_n)$ une suite de variable aléatoires telles que $P( |X_n-n| \ge \varepsilon n ) < \delta$ pour tout entier $n$ et presque sûrement $X_n$ se code en $O( \log \log(n))$ bits. En anglais c'est connu sous le nom de \"log log counter\" (Flajolet et al.).