Get 20M+ Full-Text Papers For Less Than $1.50/day. Start a 14-Day Trial for You or Your Team.

Learn More →

High-confidence predictions under adversarial uncertainty

High-confidence predictions under adversarial uncertainty High-Confidence Predictions under Adversarial Uncertainty ANDREW DRUCKER, MIT We study the setting in which the bits of an unknown infinite binary sequence x are revealed sequentially to an observer. We show that very limited assumptions about x allow one to make successful predictions about unseen bits of x. First, we study the problem of successfully predicting a single 0 from among the bits of x. 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 "safe" time-interval to perform it. Letting Nt denote the number of 1s among the first t bits of x, we say that x is "-weakly sparse" if lim inf (Nt /t) . Our main result is a randomized algorithm that, given any -weakly sparse sequence x, predicts a 0 of x with success probability as close as desired to 1 - . Thus, we can perform this task with essentially the same success probability as under the much stronger assumption that each bit of x takes http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png ACM Transactions on Computation Theory (TOCT) Association for Computing Machinery

High-confidence predictions under adversarial uncertainty

Download PDF
18 pages

Loading next page...
 
/lp/association-for-computing-machinery/high-confidence-predictions-under-adversarial-uncertainty-90C0sz0a91
Publisher
Association for Computing Machinery
Copyright
Copyright © 2013 by ACM Inc.
ISSN
1942-3454
DOI
10.1145/2493252.2493257
Publisher site
See Article on Publisher Site

Abstract

High-Confidence Predictions under Adversarial Uncertainty ANDREW DRUCKER, MIT We study the setting in which the bits of an unknown infinite binary sequence x are revealed sequentially to an observer. We show that very limited assumptions about x allow one to make successful predictions about unseen bits of x. First, we study the problem of successfully predicting a single 0 from among the bits of x. 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 "safe" time-interval to perform it. Letting Nt denote the number of 1s among the first t bits of x, we say that x is "-weakly sparse" if lim inf (Nt /t) . Our main result is a randomized algorithm that, given any -weakly sparse sequence x, predicts a 0 of x with success probability as close as desired to 1 - . Thus, we can perform this task with essentially the same success probability as under the much stronger assumption that each bit of x takes

Journal

ACM Transactions on Computation Theory (TOCT) – Association for Computing Machinery

Published: Aug 1, 2013

There are no references for this article.