Développement : Compteurs probabilistiques

Détails/Enoncé :

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.).

Recasages pour l'année 2024 :

Versions :

Références utilisées dans les versions de ce développement :

L'oral à l'agrégation de mathématiques - Une sélection de développements , Isenmann, Pecatte (utilisée dans 123 versions au total)