# American Institute of Mathematical Sciences

May  2014, 8(2): 119-127. doi: 10.3934/amc.2014.8.119

## Nearest-neighbor entropy estimators with weak metrics

 1 Department of Computer Science, Yaroslavl State University, Yaroslavl, Russian Federation 2 Department of Physics and Computer Science, Wilfrid Laurier University, Waterloo, Ontario N2L3C5

Received  June 2012 Published  May 2014

A problem of improving the accuracy of nonparametric entropy estimation for a stationary ergodic process is considered. New weak metrics are introduced and relations between metrics, measures, and entropy are discussed. A new nonparametric entropy estimator is constructed based on weak metrics and has a parameter with which the estimator is optimized to reduce its bias. It is shown that estimator's variance is upper-bounded by a nearly optimal Cramér-Rao lower bound.
Citation: Evgeniy Timofeev, Alexei Kaltchenko. Nearest-neighbor entropy estimators with weak metrics. Advances in Mathematics of Communications, 2014, 8 (2) : 119-127. doi: 10.3934/amc.2014.8.119
##### References:
 [1] D. Aldous and P. Shields, A diffusion limit for a class of randomly-growing binary trees, Probab. Th. Rel. Fields, 79 (1988), 509-542. doi: 10.1007/BF00318784. [2] L. Devroye, Exponentional inequalities in nonpametric estimation, in Nonparametric Functional Estimation and Related Topics (eds. G. Roussas), Kluwer Academic Publishers, 1991, 31-44. [3] M. Deza and T. Deza, Encyclopedia of Distances, Springer, 2009. doi: 10.1007/978-3-642-00234-2. [4] I. S. Gradshtein and I. M. Ryzhik, Table of Integrals, Series, and Products, Fifth edition, Academic Press, 1994. [5] P. Grassberger, Estimating the information content of symbol sequences and efficient codes, IEEE Trans. Inform. Theory, 35 (1989), 669-675. doi: 10.1109/18.30993. [6] A. Kaltchenko and N. Timofeeva, Entropy estimators with almost sure convergence and an $O(n^{-1})$ variance, Adv. Math. Commun., 2 (2008), 1-13. doi: 10.3934/amc.2008.2.1. [7] A. Kaltchenko and N. Timofeeva, Rate of convergence of the nearest neighbor entropy estimator, AEU-Int. J. Electr. Commun., 64 (2010), 75-79. doi: 10.1016/j.aeue.2008.09.006. [8] I. Kontoyiannis and Yu. M. Suhov, Prefixes and the entropy rate for long-range sources, in Probability Statistics and Optimization (eds. F.P. Kelly), Wiley, 1994, 89-98. [9] N. Martin and J. England, Mathematical Theory of Entropy, Cambridge Univ. Press, 1984. doi: 10.1063/1.2915804. [10] C. McDiarmid, On the method of bounded differences, in Surveys in Combinatorics, Cambridge Univ. Press, 1989, 148-188. [11] E. A. Timofeev, Statistical estimation of measure invariants, St. Petersburg Math. J., 17 (2006), 527-551. [12] E. A. Timofeev, Bias of a nonparametric entropy estimator for Markov measures, J. Math. Sci., 176 (2011), 255-269. doi: 10.1007/s10958-011-0416-5. [13] J. Ziv and A. Lempel, Compression of individual sequences by variable rate coding, IEEE Trans. Inform. Theory, 24 (1978), 530-536. doi: 10.1109/TIT.1978.1055934.

show all references

##### References:
 [1] D. Aldous and P. Shields, A diffusion limit for a class of randomly-growing binary trees, Probab. Th. Rel. Fields, 79 (1988), 509-542. doi: 10.1007/BF00318784. [2] L. Devroye, Exponentional inequalities in nonpametric estimation, in Nonparametric Functional Estimation and Related Topics (eds. G. Roussas), Kluwer Academic Publishers, 1991, 31-44. [3] M. Deza and T. Deza, Encyclopedia of Distances, Springer, 2009. doi: 10.1007/978-3-642-00234-2. [4] I. S. Gradshtein and I. M. Ryzhik, Table of Integrals, Series, and Products, Fifth edition, Academic Press, 1994. [5] P. Grassberger, Estimating the information content of symbol sequences and efficient codes, IEEE Trans. Inform. Theory, 35 (1989), 669-675. doi: 10.1109/18.30993. [6] A. Kaltchenko and N. Timofeeva, Entropy estimators with almost sure convergence and an $O(n^{-1})$ variance, Adv. Math. Commun., 2 (2008), 1-13. doi: 10.3934/amc.2008.2.1. [7] A. Kaltchenko and N. Timofeeva, Rate of convergence of the nearest neighbor entropy estimator, AEU-Int. J. Electr. Commun., 64 (2010), 75-79. doi: 10.1016/j.aeue.2008.09.006. [8] I. Kontoyiannis and Yu. M. Suhov, Prefixes and the entropy rate for long-range sources, in Probability Statistics and Optimization (eds. F.P. Kelly), Wiley, 1994, 89-98. [9] N. Martin and J. England, Mathematical Theory of Entropy, Cambridge Univ. Press, 1984. doi: 10.1063/1.2915804. [10] C. McDiarmid, On the method of bounded differences, in Surveys in Combinatorics, Cambridge Univ. Press, 1989, 148-188. [11] E. A. Timofeev, Statistical estimation of measure invariants, St. Petersburg Math. J., 17 (2006), 527-551. [12] E. A. Timofeev, Bias of a nonparametric entropy estimator for Markov measures, J. Math. Sci., 176 (2011), 255-269. doi: 10.1007/s10958-011-0416-5. [13] J. Ziv and A. Lempel, Compression of individual sequences by variable rate coding, IEEE Trans. Inform. Theory, 24 (1978), 530-536. doi: 10.1109/TIT.1978.1055934.
 [1] Xufeng Guo, Gang Liao, Wenxiang Sun, Dawei Yang. On the hybrid control of metric entropy for dominated splittings. Discrete and Continuous Dynamical Systems, 2018, 38 (10) : 5011-5019. doi: 10.3934/dcds.2018219 [2] Yunping Jiang. Global graph of metric entropy on expanding Blaschke products. Discrete and Continuous Dynamical Systems, 2021, 41 (3) : 1469-1482. doi: 10.3934/dcds.2020325 [3] Huyi Hu, Miaohua Jiang, Yunping Jiang. Infimum of the metric entropy of volume preserving Anosov systems. Discrete and Continuous Dynamical Systems, 2017, 37 (9) : 4767-4783. doi: 10.3934/dcds.2017205 [4] Dong Chen. Positive metric entropy in nondegenerate nearly integrable systems. Journal of Modern Dynamics, 2017, 11: 43-56. doi: 10.3934/jmd.2017003 [5] Kendry J. Vivas, Víctor F. Sirvent. Metric entropy for set-valued maps. Discrete and Continuous Dynamical Systems - B, 2022  doi: 10.3934/dcdsb.2022010 [6] Paulina Grzegorek, Michal Kupsa. Exponential return times in a zero-entropy process. Communications on Pure and Applied Analysis, 2012, 11 (3) : 1339-1361. doi: 10.3934/cpaa.2012.11.1339 [7] Jean René Chazottes, E. Ugalde. Entropy estimation and fluctuations of hitting and recurrence times for Gibbsian sources. Discrete and Continuous Dynamical Systems - B, 2005, 5 (3) : 565-586. doi: 10.3934/dcdsb.2005.5.565 [8] Robert Azencott, Yutheeka Gadhyan. Accurate parameter estimation for coupled stochastic dynamics. Conference Publications, 2009, 2009 (Special) : 44-53. doi: 10.3934/proc.2009.2009.44 [9] Huyi Hu, Miaohua Jiang, Yunping Jiang. Infimum of the metric entropy of hyperbolic attractors with respect to the SRB measure. Discrete and Continuous Dynamical Systems, 2008, 22 (1&2) : 215-234. doi: 10.3934/dcds.2008.22.215 [10] Ugo Bessi. The stochastic value function in metric measure spaces. Discrete and Continuous Dynamical Systems, 2017, 37 (4) : 1819-1839. doi: 10.3934/dcds.2017076 [11] Zhiming Li, Lin Shu. The metric entropy of random dynamical systems in a Hilbert space: Characterization of invariant measures satisfying Pesin's entropy formula. Discrete and Continuous Dynamical Systems, 2013, 33 (9) : 4123-4155. doi: 10.3934/dcds.2013.33.4123 [12] Deena Schmidt, Janet Best, Mark S. Blumberg. Random graph and stochastic process contributions to network dynamics. Conference Publications, 2011, 2011 (Special) : 1279-1288. doi: 10.3934/proc.2011.2011.1279 [13] Fritz Colonius. Invariance entropy, quasi-stationary measures and control sets. Discrete and Continuous Dynamical Systems, 2018, 38 (4) : 2093-2123. doi: 10.3934/dcds.2018086 [14] Gianni Gilioli, Sara Pasquali, Fabrizio Ruggeri. Nonlinear functional response parameter estimation in a stochastic predator-prey model. Mathematical Biosciences & Engineering, 2012, 9 (1) : 75-96. doi: 10.3934/mbe.2012.9.75 [15] W. Y. Tan, L.-J. Zhang, C.W. Chen. Stochastic modeling of carcinogenesis: State space models and estimation of parameters. Discrete and Continuous Dynamical Systems - B, 2004, 4 (1) : 297-322. doi: 10.3934/dcdsb.2004.4.297 [16] Francisco de la Hoz, Anna Doubova, Fernando Vadillo. Persistence-time estimation for some stochastic SIS epidemic models. Discrete and Continuous Dynamical Systems - B, 2015, 20 (9) : 2933-2947. doi: 10.3934/dcdsb.2015.20.2933 [17] Yanyan Hu, Fubao Xi, Min Zhu. Least squares estimation for distribution-dependent stochastic differential delay equations. Communications on Pure and Applied Analysis, 2022, 21 (4) : 1505-1536. doi: 10.3934/cpaa.2022027 [18] Onur Teymur, Sarah Filippi. A Bayesian nonparametric test for conditional independence. Foundations of Data Science, 2020, 2 (2) : 155-172. doi: 10.3934/fods.2020009 [19] Yan Wang, Lei Wang, Yanxiang Zhao, Aimin Song, Yanping Ma. A stochastic model for microbial fermentation process under Gaussian white noise environment. Numerical Algebra, Control and Optimization, 2015, 5 (4) : 381-392. doi: 10.3934/naco.2015.5.381 [20] Hongjun Gao, Fei Liang. On the stochastic beam equation driven by a Non-Gaussian Lévy process. Discrete and Continuous Dynamical Systems - B, 2014, 19 (4) : 1027-1045. doi: 10.3934/dcdsb.2014.19.1027

2021 Impact Factor: 1.015