Abstract
The notion of a strong sufficient statistic was introduced in [8]. In this paper, we give a survey of nice properties of strong sufficient statistics and show that there are strings for which complexity of every strong sufficient statistic is much larger than complexity of its minimal sufficient statistic.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Bauwens, B., Makhlin, A., Vereshchagin, N., Zimand, M.: Short lists with short programs in short time. ECCC report TR13-007, http://eccc.hpi-web.de/report/2013/007/
Gács, P., Tromp, J., Vitányi, P.M.B.: Algorithmic statistics. IEEE Trans. Inform. Th. 47(6), 2443–2463 (2001)
Kolmogorov, A.N.: Talk at the Information Theory Symposium in Tallinn, Estonia (1974)
Li, M., Vitányi, P.M.B.: An Introduction to Kolmogorov Complexity and its Applications, 2nd edn. Springer, New York (1997)
Kh, A.: Shen, Discussion on Kolmogorov complexity and statistical analysis. The Computer Journal 42(4), 340–342 (1999)
Shen, A.: Game Arguments in Computability Theory and Algorithmic Information Theory. In: Cooper, S.B., Dawar, A., Löwe, B. (eds.) CiE 2012. LNCS, vol. 7318, pp. 655–666. Springer, Heidelberg (2012)
Vereshchagin, N.K., Vitányi, P.M.B.: Kolmogorov’s structure functions and model selection. IEEE Trans. Information Theory 50(12), 3265–3290 (2004)
Vereshchagin, N.: Algorithmic Minimal Sufficient Statistic Revisited. In: Ambos-Spies, K., Löwe, B., Merkle, W. (eds.) CiE 2009. LNCS, vol. 5635, pp. 478–487. Springer, Heidelberg (2009)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Vereshchagin, N. (2013). On Algorithmic Strong Sufficient Statistics. In: Bonizzoni, P., Brattka, V., Löwe, B. (eds) The Nature of Computation. Logic, Algorithms, Applications. CiE 2013. Lecture Notes in Computer Science, vol 7921. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-39053-1_50
Download citation
DOI: https://doi.org/10.1007/978-3-642-39053-1_50
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-39052-4
Online ISBN: 978-3-642-39053-1
eBook Packages: Computer ScienceComputer Science (R0)