Some extremal problems arising from discrete control processes

D. Lichtenstein, N. Linial, M. Saks

Research output: Contribution to journalArticlepeer-review

30 Scopus citations

Abstract

We consider a simple abstract model for a class of discrete control processes, motivated in part by recent work about the behavior of imperfect random sources in computer algorithms. The process produces a string of n bits and is a "success" or "failure" depending on whether the string produced belongs to a prespecified set L. In an uninfluenced process each bit is chosen by a fair coin toss, and hence the probability of success is |L|/2n. A player called the controller, is introduced who has the ability to intervene in the process by specifying the value of some of the bits of the string. We answer the following questions for both worst and average case: (1) how much can the player increase the probability of success given a fixed number of interventions? (2) in terms of |L|what is the expected number of interventions needed to guarantee success? In particular our results imply that if |L|/2n=1/Ω(n) where Ω(n) tends to infinity with n (so the probability of success with no interventions is 0(1)) then with O(√n log Ω(n)) interventions the probability of success is 1-0(1). Our main results and the proof techniques are related to well-known results of Kruskal, Katona and Harper in extremal set theory.

Original languageEnglish (US)
Pages (from-to)269-287
Number of pages19
JournalCombinatorica
Volume9
Issue number3
DOIs
StatePublished - Sep 1 1989
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Discrete Mathematics and Combinatorics
  • Computational Mathematics

Keywords

  • AMS subject classification (1980): 68R10, 05C80

Fingerprint Dive into the research topics of 'Some extremal problems arising from discrete control processes'. Together they form a unique fingerprint.

Cite this