The Daily Ledger

ScienceNews

How HyperLogLog counts the internet with coin flips

A Scientific American explainer describes how the HyperLogLog algorithm estimates unique visitors using a tiny amount of memory, based on the logic of coin-flip streaks.

The Daily Ledger Staff · Updated 3 min read

Every website wants to know how many people saw a page, an ad or a post. A new explainer in Scientific American, written by math writer Jack Murtagh and published on 9 November 2026, describes the algorithm that quietly answers that question at enormous scale: HyperLogLog.

The problem with counting readers

Counting total page loads is simple, because a single running number is enough. Counting unique readers is harder. To avoid counting a returning visitor twice, an exact method must keep every reader's ID on file. Across millions of articles, posts and advertisements, those lists become enormous. According to the article, HyperLogLog trades a small amount of accuracy for a dramatic drop in the memory needed.

The coin-flip idea

Murtagh explains the core idea with a game. A coin is flipped until it lands heads, and the number of tails before that point is recorded. If the longest streak across many rounds turns out to be 10 tails, that is a clue about how many rounds were played, because a streak that long shows up in roughly one of every 1,024 rounds. The longer the record streak, the more rounds there probably were.

Turning visitors into rounds

In the web version, each visitor counts as one round. Their sequence of flips comes from a hash function, which converts an input such as a username into a string of 0s and 1s that looks random but is always identical for the same input. Because a returning visitor produces the same sequence, they do not inflate the estimate.

In the article's small example, ten visitors produce a longest streak of three, so the site estimates two to the power of three, or about eight visitors, which is close to the true figure of ten. The site only needs to store that one number. The article gives rough scales: an audience of 1,000 would likely yield a longest streak near 10, a million near 20 and a billion near 30. Even every person on Earth would produce a record only in the low 30s, so a two-digit number can stand in for billions of stored IDs.

Guarding against flukes

One visitor with an unusually long streak could distort the result. HyperLogLog handles this by splitting visitors into groups based on the first few bits of their hash. Each group estimates its own size, and the estimates are then averaged, so a single outlier can corrupt only one group. Murtagh says real systems use thousands of groups and a harmonic mean, which further reduces the influence of extreme values.

Accuracy and uses

The article cites Redis documentation to say estimates are typically off by less than 1 percent, and that systems can count billions of unique users using about as much memory as the article itself takes up. It says Google Analytics, which tracks traffic on nearly half of all websites, relies on an augmented version of the algorithm. Murtagh also notes uses in cybersecurity, where it can help detect swarms of bots, and in genomics, where it helps biologists compare genomes. He calls the method "ridiculously elegant."

The takeaway is that whenever someone needs to estimate the number of distinct items in a very large dataset, HyperLogLog is likely doing the counting behind the scenes.

Sources

Written with automated tools from the sources above and published without editor review. Spotted an error? Tell us · Corrections Policy

Report a problem with this story · Copyright & takedown