{"data":{"id":"10.48550/arxiv.cs/0410002","type":"dois","attributes":{"doi":"10.48550/arxiv.cs/0410002","prefix":"10.48550","suffix":"arxiv.cs/0410002","identifiers":[{"identifier":"cs/0410002","identifierType":"arXiv"}],"alternateIdentifiers":[{"alternateIdentifierType":"arXiv","alternateIdentifier":"cs/0410002"}],"creators":[{"name":"Grunwald, Peter","nameType":"Personal","givenName":"Peter","familyName":"Grunwald","affiliation":["CWI"],"nameIdentifiers":[]},{"name":"Vitanyi, Paul","nameType":"Personal","givenName":"Paul","familyName":"Vitanyi","affiliation":["CWI,University of Amsterdam"],"nameIdentifiers":[]}],"titles":[{"title":"Shannon Information and Kolmogorov Complexity"}],"publisher":"arXiv","container":{},"publicationYear":2004,"subjects":[{"lang":"en","subject":"Information Theory (cs.IT)","subjectScheme":"arXiv"},{"subject":"FOS: Computer and information sciences","subjectScheme":"Fields of Science and Technology (FOS)"},{"subject":"FOS: Computer and information sciences","schemeUri":"http://www.oecd.org/science/inno/38235147.pdf","subjectScheme":"Fields of Science and Technology (FOS)"},{"lang":"en","subject":"E.4, H.1.1","subjectScheme":"ACM"}],"contributors":[],"dates":[{"date":"2004-10-01T16:54:45Z","dateType":"Submitted","dateInformation":"v1"},{"date":"2020-07-21T00:14:46Z","dateType":"Updated","dateInformation":"v1"},{"date":"2004-10","dateType":"Available","dateInformation":"v1"},{"date":"2004","dateType":"Issued"}],"language":null,"types":{"ris":"RPRT","bibtex":"article","citeproc":"article-journal","schemaOrg":"ScholarlyArticle","resourceType":"Article","resourceTypeGeneral":"Text"},"relatedIdentifiers":[],"relatedItems":[],"sizes":[],"formats":[],"version":"1","rightsList":[{"rights":"Assumed arXiv.org perpetual, non-exclusive license to distribute this article for submissions made before January 2004","rightsUri":"http://arxiv.org/licenses/assumed-1991-2003/"}],"descriptions":[{"description":"We compare the elementary theories of Shannon information and Kolmogorov complexity, the extent to which they have a common purpose, and where they are fundamentally different. We discuss and relate the basic notions of both theories: Shannon entropy versus Kolmogorov complexity, the relation of both to universal coding, Shannon mutual information versus Kolmogorov (`algorithmic') mutual information, probabilistic sufficient statistic versus algorithmic sufficient statistic (related to lossy compression in the Shannon theory versus meaningful information in the Kolmogorov theory), and rate distortion theory versus Kolmogorov's structure function. Part of the material has appeared in print before, scattered through various publications, but this is the first comprehensive systematic comparison. The last mentioned relations are new.","descriptionType":"Abstract"},{"description":"Survey, LaTeX 54 pages, 3 figures, Submitted to IEEE Trans Information Theory","descriptionType":"Other"}],"geoLocations":[],"fundingReferences":[],"xml":"PD94bWwgdmVyc2lvbj0iMS4wIiBlbmNvZGluZz0idXRmLTgiPz4KPHJlc291cmNlIHhtbG5zPSJodHRwOi8vZGF0YWNpdGUub3JnL3NjaGVtYS9rZXJuZWwtNCIgeG1sbnM6eHNpPSJodHRwOi8vd3d3LnczLm9yZy8yMDAxL1hNTFNjaGVtYS1pbnN0YW5jZSIgeHNpOnNjaGVtYUxvY2F0aW9uPSJodHRwOi8vZGF0YWNpdGUub3JnL3NjaGVtYS9rZXJuZWwtNCBodHRwOi8vc2NoZW1hLmRhdGFjaXRlLm9yZy9tZXRhL2tlcm5lbC00LjMvbWV0YWRhdGEueHNkIj4KICA8aWRlbnRpZmllciBpZGVudGlmaWVyVHlwZT0iRE9JIj4xMC40ODU1MC9BUlhJVi5DUy8wNDEwMDAyPC9pZGVudGlmaWVyPgogIDxhbHRlcm5hdGVJZGVudGlmaWVycz4KICAgIDxhbHRlcm5hdGVJZGVudGlmaWVyIGFsdGVybmF0ZUlkZW50aWZpZXJUeXBlPSJhclhpdiI+Y3MvMDQxMDAwMjwvYWx0ZXJuYXRlSWRlbnRpZmllcj4KICA8L2FsdGVybmF0ZUlkZW50aWZpZXJzPgogIDxjcmVhdG9ycz4KICAgIDxjcmVhdG9yPgogICAgICA8Y3JlYXRvck5hbWUgbmFtZVR5cGU9IlBlcnNvbmFsIj5HcnVud2FsZCwgUGV0ZXI8L2NyZWF0b3JOYW1lPgogICAgICA8Z2l2ZW5OYW1lPlBldGVyPC9naXZlbk5hbWU+CiAgICAgIDxmYW1pbHlOYW1lPkdydW53YWxkPC9mYW1pbHlOYW1lPgogICAgICA8YWZmaWxpYXRpb24+Q1dJPC9hZmZpbGlhdGlvbj4KICAgIDwvY3JlYXRvcj4KICAgIDxjcmVhdG9yPgogICAgICA8Y3JlYXRvck5hbWUgbmFtZVR5cGU9IlBlcnNvbmFsIj5WaXRhbnlpLCBQYXVsPC9jcmVhdG9yTmFtZT4KICAgICAgPGdpdmVuTmFtZT5QYXVsPC9naXZlbk5hbWU+CiAgICAgIDxmYW1pbHlOYW1lPlZpdGFueWk8L2ZhbWlseU5hbWU+CiAgICAgIDxhZmZpbGlhdGlvbj5DV0ksVW5pdmVyc2l0eSBvZiBBbXN0ZXJkYW08L2FmZmlsaWF0aW9uPgogICAgPC9jcmVhdG9yPgogIDwvY3JlYXRvcnM+CiAgPHRpdGxlcz4KICAgIDx0aXRsZT5TaGFubm9uIEluZm9ybWF0aW9uIGFuZCBLb2xtb2dvcm92IENvbXBsZXhpdHk8L3RpdGxlPgogIDwvdGl0bGVzPgogIDxwdWJsaXNoZXI+YXJYaXY8L3B1Ymxpc2hlcj4KICA8cHVibGljYXRpb25ZZWFyPjIwMDQ8L3B1YmxpY2F0aW9uWWVhcj4KICA8c3ViamVjdHM+CiAgICA8c3ViamVjdCB4bWw6bGFuZz0iZW4iIHN1YmplY3RTY2hlbWU9ImFyWGl2Ij5JbmZvcm1hdGlvbiBUaGVvcnkgKGNzLklUKTwvc3ViamVjdD4KICAgIDxzdWJqZWN0IHN1YmplY3RTY2hlbWU9IkZpZWxkcyBvZiBTY2llbmNlIGFuZCBUZWNobm9sb2d5IChGT1MpIj5GT1M6IENvbXB1dGVyIGFuZCBpbmZvcm1hdGlvbiBzY2llbmNlczwvc3ViamVjdD4KICAgIDxzdWJqZWN0IHhtbDpsYW5nPSJlbiIgc3ViamVjdFNjaGVtZT0iQUNNIj5FLjQsIEguMS4xPC9zdWJqZWN0PgogIDwvc3ViamVjdHM+CiAgPGRhdGVzPgogICAgPGRhdGUgZGF0ZVR5cGU9IlN1Ym1pdHRlZCIgZGF0ZUluZm9ybWF0aW9uPSJ2MSI+MjAwNC0xMC0wMVQxNjo1NDo0NVo8L2RhdGU+CiAgICA8ZGF0ZSBkYXRlVHlwZT0iVXBkYXRlZCIgZGF0ZUluZm9ybWF0aW9uPSJ2MSI+MjAyMC0wNy0yMVQwMDoxNDo0Nlo8L2RhdGU+CiAgICA8ZGF0ZSBkYXRlVHlwZT0iQXZhaWxhYmxlIiBkYXRlSW5mb3JtYXRpb249InYxIj4yMDA0LTEwPC9kYXRlPgogIDwvZGF0ZXM+CiAgPHJlc291cmNlVHlwZSByZXNvdXJjZVR5cGVHZW5lcmFsPSJUZXh0Ij5BcnRpY2xlPC9yZXNvdXJjZVR5cGU+CiAgPHZlcnNpb24+MTwvdmVyc2lvbj4KICA8cmlnaHRzTGlzdD4KICAgIDxyaWdodHMgcmlnaHRzVVJJPSJodHRwOi8vYXJ4aXYub3JnL2xpY2Vuc2VzL2Fzc3VtZWQtMTk5MS0yMDAzLyI+QXNzdW1lZCBhclhpdi5vcmcgcGVycGV0dWFsLCBub24tZXhjbHVzaXZlIGxpY2Vuc2UgdG8gZGlzdHJpYnV0ZSB0aGlzIGFydGljbGUgZm9yIHN1Ym1pc3Npb25zIG1hZGUgYmVmb3JlIEphbnVhcnkgMjAwNDwvcmlnaHRzPgogIDwvcmlnaHRzTGlzdD4KICA8ZGVzY3JpcHRpb25zPgogICAgPGRlc2NyaXB0aW9uIGRlc2NyaXB0aW9uVHlwZT0iQWJzdHJhY3QiPldlIGNvbXBhcmUgdGhlIGVsZW1lbnRhcnkgdGhlb3JpZXMgb2YgU2hhbm5vbiBpbmZvcm1hdGlvbiBhbmQgS29sbW9nb3JvdiBjb21wbGV4aXR5LCB0aGUgZXh0ZW50IHRvIHdoaWNoIHRoZXkgaGF2ZSBhIGNvbW1vbiBwdXJwb3NlLCBhbmQgd2hlcmUgdGhleSBhcmUgZnVuZGFtZW50YWxseSBkaWZmZXJlbnQuIFdlIGRpc2N1c3MgYW5kIHJlbGF0ZSB0aGUgYmFzaWMgbm90aW9ucyBvZiBib3RoIHRoZW9yaWVzOiBTaGFubm9uIGVudHJvcHkgdmVyc3VzIEtvbG1vZ29yb3YgY29tcGxleGl0eSwgdGhlIHJlbGF0aW9uIG9mIGJvdGggdG8gdW5pdmVyc2FsIGNvZGluZywgU2hhbm5vbiBtdXR1YWwgaW5mb3JtYXRpb24gdmVyc3VzIEtvbG1vZ29yb3YgKGBhbGdvcml0aG1pYycpIG11dHVhbCBpbmZvcm1hdGlvbiwgcHJvYmFiaWxpc3RpYyBzdWZmaWNpZW50IHN0YXRpc3RpYyB2ZXJzdXMgYWxnb3JpdGhtaWMgc3VmZmljaWVudCBzdGF0aXN0aWMgKHJlbGF0ZWQgdG8gbG9zc3kgY29tcHJlc3Npb24gaW4gdGhlIFNoYW5ub24gdGhlb3J5IHZlcnN1cyBtZWFuaW5nZnVsIGluZm9ybWF0aW9uIGluIHRoZSBLb2xtb2dvcm92IHRoZW9yeSksIGFuZCByYXRlIGRpc3RvcnRpb24gdGhlb3J5IHZlcnN1cyBLb2xtb2dvcm92J3Mgc3RydWN0dXJlIGZ1bmN0aW9uLiBQYXJ0IG9mIHRoZSBtYXRlcmlhbCBoYXMgYXBwZWFyZWQgaW4gcHJpbnQgYmVmb3JlLCBzY2F0dGVyZWQgdGhyb3VnaCB2YXJpb3VzIHB1YmxpY2F0aW9ucywgYnV0IHRoaXMgaXMgdGhlIGZpcnN0IGNvbXByZWhlbnNpdmUgc3lzdGVtYXRpYyBjb21wYXJpc29uLiBUaGUgbGFzdCBtZW50aW9uZWQgcmVsYXRpb25zIGFyZSBuZXcuPC9kZXNjcmlwdGlvbj4KICAgIDxkZXNjcmlwdGlvbiBkZXNjcmlwdGlvblR5cGU9Ik90aGVyIj5TdXJ2ZXksIExhVGVYIDU0IHBhZ2VzLCAzIGZpZ3VyZXMsIFN1Ym1pdHRlZCB0byBJRUVFIFRyYW5zIEluZm9ybWF0aW9uIFRoZW9yeTwvZGVzY3JpcHRpb24+CiAgPC9kZXNjcmlwdGlvbnM+CjwvcmVzb3VyY2U+","url":"https://arxiv.org/abs/cs/0410002","contentUrl":null,"metadataVersion":0,"schemaVersion":"http://datacite.org/schema/kernel-4","source":"mds","isActive":true,"state":"findable","reason":null,"viewCount":0,"viewsOverTime":[],"downloadCount":0,"downloadsOverTime":[],"referenceCount":0,"citationCount":1,"citationsOverTime":[{"year":"2025","total":1}],"partCount":0,"partOfCount":0,"versionCount":0,"versionOfCount":0,"created":"2022-03-18T03:41:11.000Z","registered":"2022-03-18T03:41:12.000Z","published":"2004","updated":"2025-02-03T10:17:05.000Z"},"relationships":{"client":{"data":{"id":"arxiv.content","type":"clients"}},"provider":{"data":{"id":"arxiv","type":"providers"}},"media":{"data":{"id":"10.48550/arxiv.cs/0410002","type":"media"}},"references":{"data":[]},"citations":{"data":[{"id":"10.4230/lipics.csl.2025.17","type":"dois"}]},"parts":{"data":[]},"partOf":{"data":[]},"versions":{"data":[]},"versionOf":{"data":[]}}}}