PC Seminar: Unseen Species Problem and Edge Exchangeable Random Graphs

Abstract: Unseen Species Problem asks one to predict, given access to i.i.d. samples from a discrete distribution, how many new outcomes (species) would be observed if additional samples were collected. We generalize the unseen species problem to i.i.d. samples from a set valued distribution, which we argue is a better model in many problems of practical interest. The set of observed species is then precisely the vertex set of an edge exchangeable hypergraph. The spirit of our results is that if the hyperedges are of bounded arity then one can give guarantees for the generalized unseen species problem which differ from the classical problem only in constant factors.

This is a seminar in our seminar series on Probability and Combinatorics (PC).