Large alphabet inference
Amichai Painsky · Information and Inference A Journal of the IMA · 2023
Abstract Consider a finite sample from an unknown multinomial distribution. Inferring the underlying multinomial parameters is a basic problem in statistics and related fields. Currently known methods focus on classical regimes where the sample is large, or both the sample and the alphabet are small. In this work we study the complementary large alphabet regime, as we consider the case where the number of samples is comparable with (or even smaller than) the alphabet size. We introduce a novel inference scheme that significantly improves upon currently known methods. Our proposed scheme is robust, easy to apply and provides favourable performance guarantees.