El contaje aproximado fue inventado en 1977 por Robert Morris en Bell Labs como una forma de contar grandes cantidades utilizando poca memoria.

La idea del contaje aproximado es sencilla. Por cada evento individual a contar, en vez de incrementar un contador, se decide al azar si se incrementa el contador o no. Además la probabilidad de que esto suceda depende del valor propio contador.

Un ejemplo.

1. Se inicializa el contador a cero.
2. Cuando se observa el primer evento, se incrementa en una unidad.
3. Al detectar un segundo evento, se tira una moneda al aire. Si sale cara, se incrementa el contador, si sale cruz, se deja como está.
4. Luego, al recibir los sucesivos eventos, se tiran al aire un número de monedas igual al valor del contador en ese momento. Si salen todas caras, se incrementa el contador, si sale alguna cruz, se deja como está.
5. El valor aproximado de eventos sucedidos es 2 elevado al valor del contador.
   

Este tipo de contadores se siguen utilizando en la actualidad a la hora de monitorizar eventos que no requieren mucha precisión. Por ejemplo, Google lo utiliza para contar el número de veces que la gente hace click en una palabra de una página de resultados. El contaje aproximado es suficiente para conocer estadísticas y a una empresa como Google le supone un ahorro de miles de ordenadores dedicados a "contar clicks".

Saber más: 1