“Distinct Elements in Streams: An Algorithm for the (Text) Book”, Sourav Chakraborty, N. V. Vinodchandran, Kuldeep S. Meel2023-01-24 (algorithms, order statistics, probability theory)⁠:

[media] Given a data stream 𝒜 = ⟨a₁, a₂, …, a_m⟩ of m elements where each a_i ∈ [n], the Distinct Elements problem is to estimate the number of distinct elements in 𝒜.

Distinct Elements has been a subject of theoretical and empirical investigations over the past 4 decades resulting in space optimal algorithms for it. All the current state-of-the-art algorithms are, however, beyond the reach of an undergraduate textbook owing to their reliance on the usage of notions such as pairwise independence and universal hash functions.

We present a simple, intuitive, sampling-based space-efficient algorithm whose description and the proof are accessible to undergraduates with the knowledge of basic probability theory.