Abstract-We studie problem i distribution egendom testning: Med tanke på prov tillgång till en eller flera okända diskreta distributioner, vi vill avgöra om de har någon global egendom eller är epsilon-långt från att ha fastigheten i L1 avstånd (likvärdigt, total variation avstånd, eller "statistiskt avstånd"). I detta arbete ger vi ett nytt allmänt tillvägagångssätt för distributionstestning. Vi beskriver två tekniker: vår första teknik ger provoptimala testare, medan vår andra teknik ger matchande prov lägre gränser. Som en följd av detta löser vi urvalet komplexiteten i en mängd olika testproblem. Våra övre gränser erhålls genom en modulär reduktionsbaserad metod. Vårt tillvägagångssätt ger optimala testare för många problem genom att använda en standard L2-identitetstestare som en svart låda. Med hjälp av detta recept får vi enkla skattningar för ett brett spektrum av problem, omfattande många problem som tidigare studerats i TCS-litteraturen, nämligen: (1) identitetstestning till en fast distribution, (2) närhetstestning mellan två okända distributioner (med lika/ojämlika provstorlekar), (3) oberoende testning (i alla dimensioner), (4) närhetstestning för samlingar av distributioner, och (5) testning histogram. För alla dessa problem, våra testare är provoptimala, upp till konstanta faktorer. Med undantag för (1) är våra första provoptimala testare för motsvarande problem. Dessutom är våra kalkylatorer betydligt enklare att ange och analysera jämfört med tidigare resultat. Som en viktig tillämpning av vår reduktionsbaserade teknik får vi den första adaptiva algoritmen för att testa ekvivalens mellan två okända distributioner. Provets komplexitet i vår algoritm beror på strukturen hos de okända distributionerna -till skillnad från bara deras domänstorlek - och är betydligt bättre jämfört med det värsta fallet optimal L1-tester i många naturliga fall. Dessutom generaliserar vår teknik naturligt till andra mått bortom L1-avståndet. Som en illustration av dess flexibilitet använder vi den för att få den första nästan optimala ekvivalenstestaren under Hellinger-avståndet. Våra nedre gränser erhålls genom en direkt informationsteori: Med tanke på en kandidat hård instans, våra bevis fortsätter genom att begränsa den ömsesidiga informationen mellan lämpliga slumpmässiga variabler. Även om detta är en klassisk metod i informationsteorin, hade det före vårt arbete inte använts i detta sammanhang. Tidigare lägre gränser förlitade sig antingen på födelsedagsparadoxen, eller på ögonblicksmatchning och var därmed begränsade till symmetriska egenskaper. Vår strategi med lägre gränser lider inte av några sådana begränsningar och ger snäva urval lägre gränser för de ovannämnda problemen.
På senare tid föreslog Ref ett modulärt reduktionsbaserat tillvägagångssätt för problem med testning av distributionsfastigheter, som återvann alla resultat av närhets- och identitetstester ovan.
A New Approach for Testing Properties of Discrete Distributions
{'venue': '2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS)', 'journal': '2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS)', 'mag_field_of_study': ['Computer Science', 'Mathematics']}