Entropi kestiriminin sorgu karmaşıklığı

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.