Optimal entropy estimation on large alphabet: fundamental limits and fast algorithms

entropy estimation;large alphabet

Yang, Pengkun ; Wu ; Yihong

关键词: entropy estimation;    large alphabet;   

Others  :  https://www.ideals.illinois.edu/bitstream/handle/2142/90776/YANG-THESIS-2016.pdf?sequence=1&isAllowed=y

美国|英语

来源: The Illinois Digital Environment for Access to Learning and Scholarship

【 摘 要 】

Consider the problem of estimating the Shannon entropy of a distributionover k elements from n independent samples. We obtain the minimax mean-square error within universal multiplicative constant factors if n exceeds aconstant factor of k/log(k); otherwise there exists no consistent estimator.This refines the recent result of Valiant and Valiant (2011) that the mini-mal sample size for consistent entropy estimation scales. The apparatus ofbest polynomial approximation plays a key role in both the construction ofoptimal estimators and, via a duality argument, the minimax lower bound.