{"entities":{"Q1736500":{"pageid":1747241,"ns":120,"title":"Item:Q1736500","lastrevid":72377196,"modified":"2026-04-14T04:29:46Z","type":"item","id":"Q1736500","labels":{"en":{"language":"en","value":"A note on sequence prediction over large alphabets"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7042114"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736500$49B7F96B-1365-4C23-8554-3D4B0AF198AC","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"c97364689b910debb7bd56a7fe8c03fe93af169a","datavalue":{"value":{"text":"A note on sequence prediction over large alphabets","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1736500$9059EE58-B1E6-40FE-86E8-82A0BB61B831","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"f8fdbe84df288d62bac1b3f137c5e01b86e35fbc","datavalue":{"value":"1461.68077","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736500$C1D53D3F-F5D1-4174-A61B-6FB3959D9873","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"8a86b93d0edba1c47d7a5176784c441eefd7868d","datavalue":{"value":{"entity-type":"item","numeric-id":390357,"id":"Q390357"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736500$D868A96B-5363-4D7A-BE07-B70E78E11858","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"18e3aed7ec2baba1bc6b2c08988b16bb9ac0e77f","datavalue":{"value":{"entity-type":"item","numeric-id":82263,"id":"Q82263"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736500$FB907AEB-2FF8-4365-A029-85CA7027308E","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"d660e31d569d3203bec6d5e897b7f6ed7f6a3a72","datavalue":{"value":{"time":"+2019-03-26T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1736500$FE061961-F040-4E18-ABEA-E9B626B802F7","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"96198ec965f5abed37a2160391d0a1d408b252b3","datavalue":{"value":"Summary: Building on results from data compression, we prove nearly tight bounds on how well sequences of length \\(n\\) can be predicted in terms of the size \\(\\sigma\\) of the alphabet and the length \\(k\\) of the context considered when making predictions. We compare the performance achievable by an adaptive predictor with no advance knowledge of the sequence, to the performance achievable by the optimal static predictor using a table listing the frequency of each \\((k+1)\\)-tuple in the sequence. We show that, if the elements of the sequence are chosen uniformly at random, then an adaptive predictor can compete in the expected case if \\(k\\leq\\log_\\sigma n-3-\\epsilon\\), for a constant \\(\\epsilon >0\\), but not if \\(k\\geq\\log_\\sigma n\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1736500$3215200E-30ED-4E2B-AF1C-B6E5FFFD3EF4","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"4264b8bf260e532ba12469970b36fcaf09f85467","datavalue":{"value":"68P30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736500$DB1E3249-9FFB-4349-B77C-1350D736198B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"cfe779e91fe9c53ee133568259955801965765ae","datavalue":{"value":"68T05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736500$F0E5D500-1F9F-4A6A-9223-A6A7BDC91375","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"8960a9ec2d60e0c21dae7fdbfa074c605635812f","datavalue":{"value":"7042114","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736500$A876E7FE-0A4C-42A4-9055-B751B20BA3F1","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"79b17a3cdd7c334adb54df948c838f42a304e9e6","datavalue":{"value":"sequence prediction","type":"string"},"datatype":"string"},"type":"statement","id":"Q1736500$73CF4F03-B4EB-4A77-A5B9-EDABC48072B4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2ee1116134bc7e8ffb1595a5c825ba9ca4f7be53","datavalue":{"value":"alphabet size","type":"string"},"datatype":"string"},"type":"statement","id":"Q1736500$2556F6A9-B3D3-4F1F-BBCB-41B9EE37087C","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736500$1E394EC9-4D5A-4EBC-B9DA-E56A51D44B6F","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"f1133a9c19055cd230a0a80d3e14d0ec6c3a7aa3","datavalue":{"value":"https://doi.org/10.3390/a5010050","type":"string"},"datatype":"url"},"type":"statement","id":"Q1736500$B3679ADE-AF72-4808-86EE-7BFBF1F03E57","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"2074971fab1012da814e7aa5d35813cac153fd5f","datavalue":{"value":"W2164470077","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736500$80C00932-7459-461C-885F-1256C85782AC","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"6cce76ac619fc85ccf6306bddf414040d11e2a2f","datavalue":{"value":"10.3390/A5010050","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736500$E0E4623D-4B06-4C7E-8F20-A5DEEAD498AE","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6245015d5f82590d08bfece3afd512cc305962ae","datavalue":{"value":{"entity-type":"item","numeric-id":3604743,"id":"Q3604743"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e4ff87baac225ba445711db01766490e47c80f02","datavalue":{"value":{"amount":"+0.8153254389762878","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1736500$DD344055-19A7-4826-97B0-6E4BD298D3D8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6dc1369d135bfe64b7ff970f4ebd7f837eb00f5b","datavalue":{"value":{"entity-type":"item","numeric-id":3548806,"id":"Q3548806"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"30f2504813315a7771a313d8108477229410dec1","datavalue":{"value":{"amount":"+0.7953792214393616","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1736500$1097A848-D8F2-4642-8512-FA11D28C7B25","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"71b9594bbaf5e7f42172f63a9105ba5589133f75","datavalue":{"value":{"entity-type":"item","numeric-id":4014142,"id":"Q4014142"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a0a6f4831b7b48809025d196f2653110e7c111af","datavalue":{"value":{"amount":"+0.7844138741493225","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1736500$259A1397-8684-4B19-BBCB-0C68EE515A3F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f623f568437f83a3405f312d6e94e8edd33b43fa","datavalue":{"value":{"entity-type":"item","numeric-id":1336479,"id":"Q1336479"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"18681d6d92dab46095a25e77c5f15dbed3619678","datavalue":{"value":{"amount":"+0.7781792283058167","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1736500$69D62DBE-6BD7-4010-AF6F-32FC6DA9B6C9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"92e40d126e948e36e204ff3aac971f3b2dad501c","datavalue":{"value":{"entity-type":"item","numeric-id":1854565,"id":"Q1854565"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e338454652372916b25d686e771ebe03b19c832f","datavalue":{"value":{"amount":"+0.7773873209953308","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1736500$6DB24148-09EF-4208-8C88-909B84D223B9","rank":"normal"}],"P163":[{"mainsnak":{"snaktype":"value","property":"P163","hash":"45fcd4163b5f33e6e8c784f5522d7246c0a1a61e","datavalue":{"value":{"entity-type":"item","numeric-id":57056,"id":"Q57056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736500$724BD462-AC8E-4892-B0EE-5510B77DB23F","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A note on sequence prediction over large alphabets","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/A_note_on_sequence_prediction_over_large_alphabets"}}}}}