On estimating the alphabet size of a discrete random source

11/20/2017
by   Philip Ginzboorg, et al.
0

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.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset