Testing Support Size More Efficiently Than Learning Histograms

Renato Ferreira Pinto, Nathaniel Harms

Consider two problems about an unknown probability distribution $p$: 1. How many samples from $p$ are required to test if $p$ is supported on $n$ elements or not? Specifically, giv…