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

Metrics

  • PDF downloads (84)
  • HTML views (0)
  • Cited by (0)

Other articles
by authors

[Back to Top]