On estimating the alphabet size of a discrete random source

Philip Ginzboorg

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 al…