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

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

Other articles
by authors

[Back to Top]