On estimating the alphabet size of a discrete random source

2017/11/20 by Philip Ginzboorg, Ginzboorg, Philip
Biochemistry, Genetics and Molecular Biology · Computer Science · #68W27 #68W40 #Algorithms and Data Compression #Cellular Automata and Applications #DNA and Biological Computing #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #cs.DS #msc:68W27 #msc:68W40

paper · pdf · doi:10.48550/arxiv.1711.07545

arxiv created 2017/11/20 · openalex publication_date 2017/11/20 · arxiv updated 2017/11/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We are concerned with estimating alphabet size N from a stream of symbols taken uniformly at random from that alphabet. We define and analyze a memory-restricted variant of an algorithm that have been earlier proposed for this purpose. The alphabet size N can be estimated in O(√(N)) time and space by the memory-restricted variant of this algorithm.

Citations

• Birthday paradox, coupon collectors, caching algorithms and self-organizing search

Related

• Beyond Countable Alphabets: An Extension of the Information-Spectrum Approach
• Prediction of Large Alphabet Processes and Its Application to Adaptive Source Coding
• Estimation of Entropy in Constant Space with Improved Sample Complexity
• Efficient Representation of Large-Alphabet Probability Distributions
• On principles of large deviation and selected data compression