Développement #531

Titre : Compteurs probabilistiques

Contenu : Comment compter informatiquement des objets en très grande quantité ?\rC'est ce à quoi répond ce développement.\rOn montre que :\r\rSoit $\varepsilon >0$ et $\delta > 0$.\rIl 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.\r\rEn anglais c'est connu sous le nom de \"log log counter\" (Flajolet et al.).

Créé le : 23/07/2026 12:42

Mis à jour : 23/07/2026 12:42