Vi anser att problemet med att uppskatta stödstorleken för en diskret fördelning vars minsta icke-noll massa är minst 1 k. Under den oberoende provtagningsmodellen, visar vi att minimax prov komplexitet för att uppnå ett additivt fel av k med sannolikhet minst 0,5 ligger inom universella konstanta faktorer k log k log 2 1, vilket förbättrar det state-of-the-art resultat k 2 log k på grund av Valiant och Valiant. Det optimala förfarandet är en linjär estimator baserad på Chebysjev polynom och dess approximativa-teoretiska egenskaper. Vi studerar också det närbesläktade artproblemet där målet är att uppskatta antalet distinkta färger i en urna som innehåller k-kulor från upprepade dragningar. Samtidigt som uppnå ett additivt fel proportionellt till k fortfarande kräver  på k log k ) prover, visar vi att med  på k) prov man kan strikt överträffa en allmän stöd storlek uppskattning med hjälp av interpolerande polynom.
Antag för alla x-x-D, om p x-x-x {0}-[ 1 k, 1], då REF visade att den optimala prov komplexiteten för att uppskatta stöd inom additiv noggrannhet k är O( k log k log 2 1 ).
Chebyshev polynomials, moment matching, and optimal estimation of the unseen
{'venue': None, 'journal': 'arXiv: Statistics Theory', 'mag_field_of_study': ['Mathematics']}