Some extremal problems arising from discrete control processes View Full Text


Ontology type: schema:ScholarlyArticle      Open Access: True


Article Info

DATE

1989-09

AUTHORS

D. Lichtenstein, N. Linial, M. Saks

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 ofn bits and is a “success” or “failure” depending on whether the string produced belongs to a prespecified setL. 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 withn (so the probability of success with no interventions is 0(1)) then withO(√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. More... »

PAGES

269-287

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/bf02125896

DOI

http://dx.doi.org/10.1007/bf02125896

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1041716457


Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

JSON-LD is the canonical representation for SciGraph data.

TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

[
  {
    "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
    "about": [
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/01", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Mathematical Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0101", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Pure Mathematics", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Bell Laboratories, 07733, Holmdel, NJ, USA", 
          "id": "http://www.grid.ac/institutes/grid.469490.6", 
          "name": [
            "Bell Laboratories, 07733, Holmdel, NJ, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Lichtenstein", 
        "givenName": "D.", 
        "id": "sg:person.011650375761.34", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011650375761.34"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Computer Science, Hebrew University, Givat Ram, Jerusalem, Israel", 
          "id": "http://www.grid.ac/institutes/grid.9619.7", 
          "name": [
            "Department of Computer Science, Hebrew University, Givat Ram, Jerusalem, Israel"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Linial", 
        "givenName": "N.", 
        "id": "sg:person.015760032537.47", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015760032537.47"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Computer Science and Engineering, University of California at San Diego, 92122, La Jolla, Calif., USA", 
          "id": "http://www.grid.ac/institutes/grid.266100.3", 
          "name": [
            "Department of Computer Science and Engineering, University of California at San Diego, 92122, La Jolla, Calif., USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Saks", 
        "givenName": "M.", 
        "id": "sg:person.011520224512.05", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011520224512.05"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "sg:pub.10.1007/bf02579325", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1008027143", 
          "https://doi.org/10.1007/bf02579325"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-94-009-5315-4_10", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1005978541", 
          "https://doi.org/10.1007/978-94-009-5315-4_10"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "1989-09", 
    "datePublishedReg": "1989-09-01", 
    "description": "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 ofn bits and is a \u201csuccess\u201d or \u201cfailure\u201d depending on whether the string produced belongs to a prespecified setL. In an uninfluenced process each bit is chosen by a fair coin toss, and hence the probability of success is \u00a6L\u00a6/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 \u00a6L\u00a6what is the expected number of interventions needed to guarantee success? In particular our results imply that if \u00a6L\u00a6/2n=1/\u03a9(n) where \u03a9(n) tends to infinity withn (so the probability of success with no interventions is 0(1)) then withO(\u221an log\u03a9(n)) interventions the probability of success is 1\u22120(1).Our main results and the proof techniques are related to well-known results of Kruskal, Katona and Harper in extremal set theory.", 
    "genre": "article", 
    "id": "sg:pub.10.1007/bf02125896", 
    "isAccessibleForFree": true, 
    "isPartOf": [
      {
        "id": "sg:journal.1136493", 
        "issn": [
          "0209-9683", 
          "1439-6912"
        ], 
        "name": "Combinatorica", 
        "publisher": "Springer Nature", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "3", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "9"
      }
    ], 
    "keywords": [
      "discrete control processes", 
      "imperfect random sources", 
      "extremal set theory", 
      "fair coin toss", 
      "probability of success", 
      "extremal problems", 
      "random sources", 
      "infinity withn", 
      "control process", 
      "simple abstract model", 
      "set theory", 
      "proof technique", 
      "average case", 
      "coin toss", 
      "expected number", 
      "main results", 
      "computer algorithm", 
      "probability", 
      "abstract model", 
      "string", 
      "Kruskal", 
      "recent work", 
      "controller", 
      "theory", 
      "algorithm", 
      "withn", 
      "problem", 
      "class", 
      "Katona", 
      "bits", 
      "number", 
      "model", 
      "toss", 
      "results", 
      "terms", 
      "process", 
      "technique", 
      "cases", 
      "behavior", 
      "work", 
      "values", 
      "source", 
      "part", 
      "players", 
      "Harper", 
      "questions", 
      "success", 
      "ability", 
      "failure", 
      "number of interventions", 
      "intervention"
    ], 
    "name": "Some extremal problems arising from discrete control processes", 
    "pagination": "269-287", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1041716457"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/bf02125896"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/bf02125896", 
      "https://app.dimensions.ai/details/publication/pub.1041716457"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2022-10-01T06:28", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20221001/entities/gbq_results/article/article_209.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "https://doi.org/10.1007/bf02125896"
  }
]
 

Download the RDF metadata as:  json-ld nt turtle xml License info

HOW TO GET THIS DATA PROGRAMMATICALLY:

JSON-LD is a popular format for linked data which is fully compatible with JSON.

curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/bf02125896'

N-Triples is a line-based linked data format ideal for batch operations.

curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/bf02125896'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/bf02125896'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/bf02125896'


 

This table displays all metadata directly associated to this object as RDF triples.

136 TRIPLES      21 PREDICATES      78 URIs      68 LITERALS      6 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/bf02125896 schema:about anzsrc-for:01
2 anzsrc-for:0101
3 schema:author N853bdbb8a8504f46a02540e92a67bf7e
4 schema:citation sg:pub.10.1007/978-94-009-5315-4_10
5 sg:pub.10.1007/bf02579325
6 schema:datePublished 1989-09
7 schema:datePublishedReg 1989-09-01
8 schema:description 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 ofn bits and is a “success” or “failure” depending on whether the string produced belongs to a prespecified setL. 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 withn (so the probability of success with no interventions is 0(1)) then withO(√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.
9 schema:genre article
10 schema:isAccessibleForFree true
11 schema:isPartOf N775a300d941145c7bbbc01662de7e269
12 Nf1a3fd8688e04672b9c9fb286d98ab23
13 sg:journal.1136493
14 schema:keywords Harper
15 Katona
16 Kruskal
17 ability
18 abstract model
19 algorithm
20 average case
21 behavior
22 bits
23 cases
24 class
25 coin toss
26 computer algorithm
27 control process
28 controller
29 discrete control processes
30 expected number
31 extremal problems
32 extremal set theory
33 failure
34 fair coin toss
35 imperfect random sources
36 infinity withn
37 intervention
38 main results
39 model
40 number
41 number of interventions
42 part
43 players
44 probability
45 probability of success
46 problem
47 process
48 proof technique
49 questions
50 random sources
51 recent work
52 results
53 set theory
54 simple abstract model
55 source
56 string
57 success
58 technique
59 terms
60 theory
61 toss
62 values
63 withn
64 work
65 schema:name Some extremal problems arising from discrete control processes
66 schema:pagination 269-287
67 schema:productId N1e9ad84df72347b0828d81a47f83fb90
68 Nfda1cc2b7c4146369906a500f11db7a2
69 schema:sameAs https://app.dimensions.ai/details/publication/pub.1041716457
70 https://doi.org/10.1007/bf02125896
71 schema:sdDatePublished 2022-10-01T06:28
72 schema:sdLicense https://scigraph.springernature.com/explorer/license/
73 schema:sdPublisher Ne5e81ecd96d7491b992c2cbd9a7397a8
74 schema:url https://doi.org/10.1007/bf02125896
75 sgo:license sg:explorer/license/
76 sgo:sdDataset articles
77 rdf:type schema:ScholarlyArticle
78 N1e9ad84df72347b0828d81a47f83fb90 schema:name dimensions_id
79 schema:value pub.1041716457
80 rdf:type schema:PropertyValue
81 N775a300d941145c7bbbc01662de7e269 schema:volumeNumber 9
82 rdf:type schema:PublicationVolume
83 N853bdbb8a8504f46a02540e92a67bf7e rdf:first sg:person.011650375761.34
84 rdf:rest Nb51c7436dd97498a949f00c8ca05af9f
85 N9be7c656bd55436a9fce35ac64cb5155 rdf:first sg:person.011520224512.05
86 rdf:rest rdf:nil
87 Nb51c7436dd97498a949f00c8ca05af9f rdf:first sg:person.015760032537.47
88 rdf:rest N9be7c656bd55436a9fce35ac64cb5155
89 Ne5e81ecd96d7491b992c2cbd9a7397a8 schema:name Springer Nature - SN SciGraph project
90 rdf:type schema:Organization
91 Nf1a3fd8688e04672b9c9fb286d98ab23 schema:issueNumber 3
92 rdf:type schema:PublicationIssue
93 Nfda1cc2b7c4146369906a500f11db7a2 schema:name doi
94 schema:value 10.1007/bf02125896
95 rdf:type schema:PropertyValue
96 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
97 schema:name Mathematical Sciences
98 rdf:type schema:DefinedTerm
99 anzsrc-for:0101 schema:inDefinedTermSet anzsrc-for:
100 schema:name Pure Mathematics
101 rdf:type schema:DefinedTerm
102 sg:journal.1136493 schema:issn 0209-9683
103 1439-6912
104 schema:name Combinatorica
105 schema:publisher Springer Nature
106 rdf:type schema:Periodical
107 sg:person.011520224512.05 schema:affiliation grid-institutes:grid.266100.3
108 schema:familyName Saks
109 schema:givenName M.
110 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011520224512.05
111 rdf:type schema:Person
112 sg:person.011650375761.34 schema:affiliation grid-institutes:grid.469490.6
113 schema:familyName Lichtenstein
114 schema:givenName D.
115 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011650375761.34
116 rdf:type schema:Person
117 sg:person.015760032537.47 schema:affiliation grid-institutes:grid.9619.7
118 schema:familyName Linial
119 schema:givenName N.
120 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015760032537.47
121 rdf:type schema:Person
122 sg:pub.10.1007/978-94-009-5315-4_10 schema:sameAs https://app.dimensions.ai/details/publication/pub.1005978541
123 https://doi.org/10.1007/978-94-009-5315-4_10
124 rdf:type schema:CreativeWork
125 sg:pub.10.1007/bf02579325 schema:sameAs https://app.dimensions.ai/details/publication/pub.1008027143
126 https://doi.org/10.1007/bf02579325
127 rdf:type schema:CreativeWork
128 grid-institutes:grid.266100.3 schema:alternateName Department of Computer Science and Engineering, University of California at San Diego, 92122, La Jolla, Calif., USA
129 schema:name Department of Computer Science and Engineering, University of California at San Diego, 92122, La Jolla, Calif., USA
130 rdf:type schema:Organization
131 grid-institutes:grid.469490.6 schema:alternateName Bell Laboratories, 07733, Holmdel, NJ, USA
132 schema:name Bell Laboratories, 07733, Holmdel, NJ, USA
133 rdf:type schema:Organization
134 grid-institutes:grid.9619.7 schema:alternateName Department of Computer Science, Hebrew University, Givat Ram, Jerusalem, Israel
135 schema:name Department of Computer Science, Hebrew University, Givat Ram, Jerusalem, Israel
136 rdf:type schema:Organization
 




Preview window. Press ESC to close (or click here)


...