# 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.  doi: 10.1007/BF00318784.  Google Scholar [2] L. Devroye, Exponentional inequalities in nonpametric estimation,, in Nonparametric Functional Estimation and Related Topics (eds. G. Roussas), (1991), 31.   Google Scholar [3] M. Deza and T. Deza, Encyclopedia of Distances,, Springer, (2009).  doi: 10.1007/978-3-642-00234-2.  Google Scholar [4] I. S. Gradshtein and I. M. Ryzhik, Table of Integrals, Series, and Products,, Fifth edition, (1994).   Google Scholar [5] P. Grassberger, Estimating the information content of symbol sequences and efficient codes,, IEEE Trans. Inform. Theory, 35 (1989), 669.  doi: 10.1109/18.30993.  Google Scholar [6] A. Kaltchenko and N. Timofeeva, Entropy estimators with almost sure convergence and an $O(n^{-1})$ variance,, Adv. Math. Commun., 2 (2008), 1.  doi: 10.3934/amc.2008.2.1.  Google Scholar [7] A. Kaltchenko and N. Timofeeva, Rate of convergence of the nearest neighbor entropy estimator,, AEU-Int. J. Electr. Commun., 64 (2010), 75.  doi: 10.1016/j.aeue.2008.09.006.  Google Scholar [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), (1994), 89.   Google Scholar [9] N. Martin and J. England, Mathematical Theory of Entropy,, Cambridge Univ. Press, (1984).  doi: 10.1063/1.2915804.  Google Scholar [10] C. McDiarmid, On the method of bounded differences,, in Surveys in Combinatorics, (1989), 148.   Google Scholar [11] E. A. Timofeev, Statistical estimation of measure invariants,, St. Petersburg Math. J., 17 (2006), 527.   Google Scholar [12] E. A. Timofeev, Bias of a nonparametric entropy estimator for Markov measures,, J. Math. Sci., 176 (2011), 255.  doi: 10.1007/s10958-011-0416-5.  Google Scholar [13] J. Ziv and A. Lempel, Compression of individual sequences by variable rate coding,, IEEE Trans. Inform. Theory, 24 (1978), 530.  doi: 10.1109/TIT.1978.1055934.  Google Scholar

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.  doi: 10.1007/BF00318784.  Google Scholar [2] L. Devroye, Exponentional inequalities in nonpametric estimation,, in Nonparametric Functional Estimation and Related Topics (eds. G. Roussas), (1991), 31.   Google Scholar [3] M. Deza and T. Deza, Encyclopedia of Distances,, Springer, (2009).  doi: 10.1007/978-3-642-00234-2.  Google Scholar [4] I. S. Gradshtein and I. M. Ryzhik, Table of Integrals, Series, and Products,, Fifth edition, (1994).   Google Scholar [5] P. Grassberger, Estimating the information content of symbol sequences and efficient codes,, IEEE Trans. Inform. Theory, 35 (1989), 669.  doi: 10.1109/18.30993.  Google Scholar [6] A. Kaltchenko and N. Timofeeva, Entropy estimators with almost sure convergence and an $O(n^{-1})$ variance,, Adv. Math. Commun., 2 (2008), 1.  doi: 10.3934/amc.2008.2.1.  Google Scholar [7] A. Kaltchenko and N. Timofeeva, Rate of convergence of the nearest neighbor entropy estimator,, AEU-Int. J. Electr. Commun., 64 (2010), 75.  doi: 10.1016/j.aeue.2008.09.006.  Google Scholar [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), (1994), 89.   Google Scholar [9] N. Martin and J. England, Mathematical Theory of Entropy,, Cambridge Univ. Press, (1984).  doi: 10.1063/1.2915804.  Google Scholar [10] C. McDiarmid, On the method of bounded differences,, in Surveys in Combinatorics, (1989), 148.   Google Scholar [11] E. A. Timofeev, Statistical estimation of measure invariants,, St. Petersburg Math. J., 17 (2006), 527.   Google Scholar [12] E. A. Timofeev, Bias of a nonparametric entropy estimator for Markov measures,, J. Math. Sci., 176 (2011), 255.  doi: 10.1007/s10958-011-0416-5.  Google Scholar [13] J. Ziv and A. Lempel, Compression of individual sequences by variable rate coding,, IEEE Trans. Inform. Theory, 24 (1978), 530.  doi: 10.1109/TIT.1978.1055934.  Google Scholar
 [1] Xufeng Guo, Gang Liao, Wenxiang Sun, Dawei Yang. On the hybrid control of metric entropy for dominated splittings. Discrete & Continuous Dynamical Systems - A, 2018, 38 (10) : 5011-5019. doi: 10.3934/dcds.2018219 [2] Huyi Hu, Miaohua Jiang, Yunping Jiang. Infimum of the metric entropy of volume preserving Anosov systems. Discrete & Continuous Dynamical Systems - A, 2017, 37 (9) : 4767-4783. doi: 10.3934/dcds.2017205 [3] Dong Chen. Positive metric entropy in nondegenerate nearly integrable systems. Journal of Modern Dynamics, 2017, 11: 43-56. doi: 10.3934/jmd.2017003 [4] Paulina Grzegorek, Michal Kupsa. Exponential return times in a zero-entropy process. Communications on Pure & Applied Analysis, 2012, 11 (3) : 1339-1361. doi: 10.3934/cpaa.2012.11.1339 [5] Ugo Bessi. The stochastic value function in metric measure spaces. Discrete & Continuous Dynamical Systems - A, 2017, 37 (4) : 1819-1839. doi: 10.3934/dcds.2017076 [6] 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 [7] Huyi Hu, Miaohua Jiang, Yunping Jiang. Infimum of the metric entropy of hyperbolic attractors with respect to the SRB measure. Discrete & Continuous Dynamical Systems - A, 2008, 22 (1&2) : 215-234. doi: 10.3934/dcds.2008.22.215 [8] Jean René Chazottes, E. Ugalde. Entropy estimation and fluctuations of hitting and recurrence times for Gibbsian sources. Discrete & Continuous Dynamical Systems - B, 2005, 5 (3) : 565-586. doi: 10.3934/dcdsb.2005.5.565 [9] 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 [10] 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 & Continuous Dynamical Systems - A, 2013, 33 (9) : 4123-4155. doi: 10.3934/dcds.2013.33.4123 [11] Fritz Colonius. Invariance entropy, quasi-stationary measures and control sets. Discrete & Continuous Dynamical Systems - A, 2018, 38 (4) : 2093-2123. doi: 10.3934/dcds.2018086 [12] 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 [13] W. Y. Tan, L.-J. Zhang, C.W. Chen. Stochastic modeling of carcinogenesis: State space models and estimation of parameters. Discrete & Continuous Dynamical Systems - B, 2004, 4 (1) : 297-322. doi: 10.3934/dcdsb.2004.4.297 [14] Francisco de la Hoz, Anna Doubova, Fernando Vadillo. Persistence-time estimation for some stochastic SIS epidemic models. Discrete & Continuous Dynamical Systems - B, 2015, 20 (9) : 2933-2947. doi: 10.3934/dcdsb.2015.20.2933 [15] 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 & Optimization, 2015, 5 (4) : 381-392. doi: 10.3934/naco.2015.5.381 [16] Hongjun Gao, Fei Liang. On the stochastic beam equation driven by a Non-Gaussian Lévy process. Discrete & Continuous Dynamical Systems - B, 2014, 19 (4) : 1027-1045. doi: 10.3934/dcdsb.2014.19.1027 [17] Daoyi Xu, Yumei Huang, Zhiguo Yang. Existence theorems for periodic Markov process and stochastic functional differential equations. Discrete & Continuous Dynamical Systems - A, 2009, 24 (3) : 1005-1023. doi: 10.3934/dcds.2009.24.1005 [18] Zhongming Chen, Liqun Qi. Circulant tensors with applications to spectral hypergraph theory and stochastic process. Journal of Industrial & Management Optimization, 2016, 12 (4) : 1227-1247. doi: 10.3934/jimo.2016.12.1227 [19] Linlin Tian, Xiaoyi Zhang, Yizhou Bai. Optimal dividend of compound poisson process under a stochastic interest rate. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-17. doi: 10.3934/jimo.2019047 [20] Yanan Zhao, Yuguo Lin, Daqing Jiang, Xuerong Mao, Yong Li. Stationary distribution of stochastic SIRS epidemic model with standard incidence. Discrete & Continuous Dynamical Systems - B, 2016, 21 (7) : 2363-2378. doi: 10.3934/dcdsb.2016051

2018 Impact Factor: 0.879

## Metrics

• HTML views (0)
• Cited by (0)

• on AIMS