{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:48:48Z","timestamp":1781077728144,"version":"3.54.1"},"reference-count":12,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2013,8,1]],"date-time":"2013-08-01T00:00:00Z","timestamp":1375315200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000121","name":"Division of Mathematical Sciences","doi-asserted-by":"publisher","award":["CCF-0832797, Sub-Contract No. 00001583, and DMS-0835373"],"award-info":[{"award-number":["CCF-0832797, Sub-Contract No. 00001583, and DMS-0835373"]}],"id":[{"id":"10.13039\/100000121","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000185","name":"Defense Advanced Research Projects Agency","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100000185","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["CCF-0832797, Sub-Contract No. 00001583, and DMS-0835373"],"award-info":[{"award-number":["CCF-0832797, Sub-Contract No. 00001583, and DMS-0835373"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Theory"],"published-print":{"date-parts":[[2013,8]]},"abstract":"\n We study the setting in which the bits of an unknown infinite binary sequence\n x<\/jats:italic>\n are revealed sequentially to an observer. We show that very limited assumptions about\n x<\/jats:italic>\n allow one to make successful predictions about unseen bits of\n x<\/jats:italic>\n . First, we study the problem of successfully predicting a single 0 from among the bits of\n x<\/jats:italic>\n . In our model, we have only one chance to make a prediction, but may do so at a time of our choosing. This model is applicable to a variety of situations in which we want to perform an action of fixed duration, and need to predict a \u201csafe\u201d time-interval to perform it.\n <\/jats:p>\n \n Letting\n N<\/jats:italic>\n \n t<\/jats:italic>\n <\/jats:sub>\n denote the number of 1s among the first\n t<\/jats:italic>\n bits of\n x<\/jats:italic>\n , we say that\n x<\/jats:italic>\n is \u201c\u03b5-weakly sparse\u201d if lim inf (\n N<\/jats:italic>\n \n t<\/jats:italic>\n <\/jats:sub>\n \/t) \u2264 \u03b5. Our main result is a randomized algorithm that, given any \u03b5-weakly sparse sequence\n x<\/jats:italic>\n , predicts a 0 of\n x<\/jats:italic>\n with success probability as close as desired to 1 - \u03b5. Thus, we can perform this task with essentially the same success probability as under the much stronger assumption that each bit of\n x<\/jats:italic>\n takes the value 1 independently with probability \u03b5.\n <\/jats:p>\n \n We apply this result to show how to successfully predict a bit (0 or 1) under a broad class of possible assumptions on the sequence\n x<\/jats:italic>\n . The assumptions are stated in terms of the behavior of a finite automaton\n M<\/jats:italic>\n reading the bits of\n x<\/jats:italic>\n . We also propose and solve a variant of the well-studied \u201cignorant forecasting\u201d problem. For every \u03b5>0, we give a randomized forecasting algorithm S\n \u03b5<\/jats:sub>\n that, given sequential access to a binary sequence\n x<\/jats:italic>\n , makes a prediction of the form: \u201cA\n p<\/jats:italic>\n fraction of the next\n N<\/jats:italic>\n bits will be 1s.\u201d (The algorithm gets to choose\n p<\/jats:italic>\n ,\n N<\/jats:italic>\n , and the time of the prediction.) For any fixed sequence\n x<\/jats:italic>\n , the forecast fraction\n p<\/jats:italic>\n is accurate to within \u00b1\u03b5 with probability 1 - \u03b5.\n <\/jats:p>","DOI":"10.1145\/2493252.2493257","type":"journal-article","created":{"date-parts":[[2013,8,20]],"date-time":"2013-08-20T14:07:13Z","timestamp":1377007633000},"page":"1-18","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["High-confidence predictions under adversarial uncertainty"],"prefix":"10.1145","volume":"5","author":[{"given":"Andrew","family":"Drucker","sequence":"first","affiliation":[{"name":"MIT, Princeton, NJ"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2013,8,22]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539703446912"},{"key":"e_1_2_1_2_1","unstructured":"Billingsley P. 1965. Ergodic Theory and Information. John Wiley and Sons. Billingsley P. 1965. Ergodic Theory and Information. John Wiley and Sons."},{"key":"e_1_2_1_3_1","article-title":"The well-calibrated Bayesian","volume":"77","author":"Dawid A.","year":"1982","journal-title":"J. Amer. Statist. Assoc."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1093\/qmath\/os-20.1.31"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.3982\/ECTA7163"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1093\/biomet\/85.2.379"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1086649.1086662"},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of the 25th Annual Conference on Neural Information Processing Systems. 828--836","author":"Kapralov M."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539701417723"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0890-5401(03)00187-1"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.720534"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/s001820300153"}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2493252.2493257","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2493252.2493257","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T07:28:32Z","timestamp":1750231712000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2493252.2493257"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,8]]},"references-count":12,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2013,8]]}},"alternative-id":["10.1145\/2493252.2493257"],"URL":"https:\/\/doi.org\/10.1145\/2493252.2493257","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"value":"1942-3454","type":"print"},{"value":"1942-3462","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,8]]},"assertion":[{"value":"2012-09-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-03-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-08-22","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}