The Query Complexity of Estimating Entropy

Summary:

We investigate the query complexity of additively estimating entropy of a discrete probability distribution in two settings. Let p be an unknown probability distribution on [n]:= {1, 2, ..., n}, and define two kinds of queries: A SAMP query takes no input and returns x with probability p[x]; a PMF query takes as input x and returns the value p[x]. In the SAMP model of query complexity, the only allowed interaction with p is via SAMP queries. In the SAMP+PMF model, both SAMP and PMF queries are utilized to interact with p. In particular, we consider the task of estimating the entropy of a probability distribution. For the usual Shannon entropy, we review the matching upper and lower bounds established by Valiant and Valiant in the SAMP model, and describe the algorithm constructed by Canonne and Rubinfeld in the SAMP+PMF model. For the Renyi entropy, we analyze three different matching upper and lower bound pairs introduced by Acharya et al. in the SAMP model. We show that at least poly-logarithmic number of queries are necessary to estimate the Shannon entropy in the SAMP+PMF model, matching a recent upper bound of Canonne and Rubinfeld. In addition, we prove matching upper and lower bounds to estimate the Renyi entropy in the SAMP+PMF model.

Özet:

Bu çalışmada, ayrık olasılık dağılımının entropisinin toplanır hata payıyla kestirimi iki farklı kurguda irdelenmektedir. Buna göre bilinmeyen bir olasılık dağılımı p'ye erişim iki farklı sorgu türüyle sağlanmaktadır. Herhangi bir girdisi olmayan SAMP sorgusu p[x] olasılığıyla x döndürmektedir. Girdi olarak x alan PMF sorgusunun ise çıktısı p[x]'dir. SAMP modeli ismini verdiğimiz ilk kurguda p ile sadece SAMP sorgusu vasıtasıyla iletişim sağlanmaktadır. SAMP+PMF modeli olarak adlandırdığımız ikinci kurgudaysa hem SAMP hem de PMF sorguları kullanılabilmektedir. Daha kesin bir ifadeyle, çalışmanın odak noktası olasılık dağılımı p'nin entropisinin yüksek ihtimalle toplanır hata payıyla kestirimi problemidir. Shannon entropisinin kestirimini incelediğimiz bölümde Valiant ve Valiant'ın SAMP modelinde göstermiş olduğu eşleşen alt ve üst sınırları ve Canonne ve Rubinfeld'in SAMP+PMF modelinde inşa etmiş olduğu algoritmayı tasvir ediyoruz. Renyi entropisini incelediğimiz bölümdeyse Acharya ve diğerleri tarafından sunulan üç farklı eşleşen alt ve üst sınır çiftini analiz ediyoruz. Kendi katkımız olarak, önce SAMP+PMF modelinde Shannon entropisinin kestirimi probleminin en az poli-logaritmik sayıda sorgu gerektirdiğini kanıtlayarak Canonne ve Rubinfeld'in sunduğu üst sınırın optimal olduğunu gösteriyoruz. İkinci olarak, yine SAMP+PMF modelinde Renyi entropisinin kestirimi probleminin eşleşen üst ve alt sınırlarını inşa ediyoruz.