NDLI: High-confidence predictions under adversarial uncertainty

Please wait, while we are loading the content...

High-confidence predictions under adversarial uncertainty

Content Provider	ACM Digital Library
Author	Drucker, Andrew
Copyright Year	2013
Abstract	We study the setting in which the bits of an unknown infinite binary sequence $\textit{x}$ are revealed sequentially to an observer. We show that very limited assumptions about $\textit{x}$ allow one to make successful predictions about unseen bits of $\textit{x}.$ First, we study the problem of successfully predicting a single 0 from among the bits of $\textit{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 $N_{t}$ denote the number of 1s among the first $\textit{t}$ bits of $\textit{x},$ we say that $\textit{x}$ is “&epsis;-weakly sparse” if lim inf $(N_{t}/t)$ ≤ ϵ. Our main result is a randomized algorithm that, given any ϵ-weakly sparse sequence $\textit{x},$ predicts a 0 of $\textit{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 $\textit{x}$ takes the value 1 independently with probability ϵ. 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 $\textit{x}.$ The assumptions are stated in terms of the behavior of a finite automaton $\textit{M}$ reading the bits of $\textit{x}.$ We also propose and solve a variant of the well-studied “ignorant forecasting” problem. For every ϵ>0, we give a randomized forecasting algorithm $S_{ϵ}$ that, given sequential access to a binary sequence $\textit{x},$ makes a prediction of the form: “A $\textit{p}$ fraction of the next $\textit{N}$ bits will be 1s.” (The algorithm gets to choose $\textit{p},$ $\textit{N},$ and the time of the prediction.) For any fixed sequence $\textit{x},$ the forecast fraction $\textit{p}$ is accurate to within ±ϵ with probability 1 - ϵ.
Starting Page	1
Ending Page	18
Page Count	18
File Format	PDF
ISSN	19423454
e-ISSN	19423462
DOI	10.1145/2493252.2493257
Volume Number	5
Issue Number	3
Journal	ACM Transactions on Computation Theory (TOCT)
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2013-08-22
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Prediction Binary sequences Worst-case prediction
Content Type	Text
Resource Type	Article
Subject	Computational Theory and Mathematics Theoretical Computer Science

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

High-confidence predictions under adversarial uncertainty

High-Confidence Predictions under Adversarial Uncertainty

High-Confidence Predictions under Adversarial Uncertainty

A classical decision theoretic perspective on worst-case analysis

Some New Results on Average Worst Case Carry

The Design of Shift Register Generators for Finite Sequences

Relativized Worlds without Worst-Case to Average-Case Reductions for NP

Special Issue On Worst-case Versus Average-case Complexity Editors’ Foreword

Worst-case versus average case complexity of ray-shooting

High-confidence predictions under adversarial uncertainty

Similar Documents

High-confidence predictions under adversarial uncertainty

High-Confidence Predictions under Adversarial Uncertainty

High-Confidence Predictions under Adversarial Uncertainty

A classical decision theoretic perspective on worst-case analysis

Some New Results on Average Worst Case Carry

The Design of Shift Register Generators for Finite Sequences

Relativized Worlds without Worst-Case to Average-Case Reductions for NP

Special Issue On Worst-case Versus Average-case Complexity Editors’ Foreword

Worst-case versus average case complexity of ray-shooting

High-confidence predictions under adversarial uncertainty