Deviations from uniformity in random strings View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

1988-12

AUTHORS

P. Flajolet, P. Kirschenhofer, R. F. Tichy

ABSTRACT

We show that almost all binary strings of length n contain all blocks of size (1-ε)log2n a close to uniform number of times. From this, we derive tight bounds on the discrepancy of random infinite strings. Our results are obtained through explicit generating function expressions and contour integration estimates.

PAGES

139-150

References to SciGraph publications

  • 1985-03. Some distribution properties of 0,1-sequences in MANUSCRIPTA MATHEMATICA
  • 1985. Enumeration of Strings in COMBINATORIAL ALGORITHMS ON WORDS
  • Identifiers

    URI

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

    DOI

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

    DIMENSIONS

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


    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/0104", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Statistics", 
            "type": "DefinedTerm"
          }, 
          {
            "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"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "French Institute for Research in Computer Science and Automation", 
              "id": "https://www.grid.ac/institutes/grid.5328.c", 
              "name": [
                "INRIA, Rocquencourt, F-78150, Le Chesnay, France"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Flajolet", 
            "givenName": "P.", 
            "id": "sg:person.013431037475.89", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013431037475.89"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "TU Wien", 
              "id": "https://www.grid.ac/institutes/grid.5329.d", 
              "name": [
                "Technische Universit\u00e4t Wien, Wiedner Hauptstra\u00dfe 8-10, A-1040, Vienna, Austria"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Kirschenhofer", 
            "givenName": "P.", 
            "id": "sg:person.014144322056.01", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014144322056.01"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "TU Wien", 
              "id": "https://www.grid.ac/institutes/grid.5329.d", 
              "name": [
                "Technische Universit\u00e4t Wien, Wiedner Hauptstra\u00dfe 8-10, A-1040, Vienna, Austria"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Tichy", 
            "givenName": "R. F.", 
            "id": "sg:person.015312676677.43", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015312676677.43"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "https://doi.org/10.1016/0097-3165(81)90038-8", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1001383778"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0097-3165(81)90005-4", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1022924510"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf01171708", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1037754142", 
              "https://doi.org/10.1007/bf01171708"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf01171708", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1037754142", 
              "https://doi.org/10.1007/bf01171708"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-82456-2_14", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1042555787", 
              "https://doi.org/10.1007/978-3-642-82456-2_14"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1137/0135034", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062839762"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "1988-12", 
        "datePublishedReg": "1988-12-01", 
        "description": "We show that almost all binary strings of length n contain all blocks of size (1-\u03b5)log2n a close to uniform number of times. From this, we derive tight bounds on the discrepancy of random infinite strings. Our results are obtained through explicit generating function expressions and contour integration estimates.", 
        "genre": "research_article", 
        "id": "sg:pub.10.1007/bf00348756", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": false, 
        "isPartOf": [
          {
            "id": "sg:journal.1053886", 
            "issn": [
              "0178-8051", 
              "1432-2064"
            ], 
            "name": "Probability Theory and Related Fields", 
            "type": "Periodical"
          }, 
          {
            "issueNumber": "1", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "80"
          }
        ], 
        "name": "Deviations from uniformity in random strings", 
        "pagination": "139-150", 
        "productId": [
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/bf00348756"
            ]
          }, 
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "d46f33f2571e8e8c86bbcb43bb83cdf07c13a5cfd6f33d704e9e7fdc8740383b"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1044597458"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/bf00348756", 
          "https://app.dimensions.ai/details/publication/pub.1044597458"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2019-04-15T08:54", 
        "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
        "sdPublisher": {
          "name": "Springer Nature - SN SciGraph project", 
          "type": "Organization"
        }, 
        "sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000374_0000000374/records_119752_00000001.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "http://link.springer.com/10.1007/BF00348756"
      }
    ]
     

    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/bf00348756'

    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/bf00348756'

    Turtle is a human-readable linked data format.

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

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

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


     

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

    95 TRIPLES      21 PREDICATES      32 URIs      19 LITERALS      7 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/bf00348756 schema:about anzsrc-for:01
    2 anzsrc-for:0104
    3 schema:author N9d1d94a538404a418316f09e2ff02574
    4 schema:citation sg:pub.10.1007/978-3-642-82456-2_14
    5 sg:pub.10.1007/bf01171708
    6 https://doi.org/10.1016/0097-3165(81)90005-4
    7 https://doi.org/10.1016/0097-3165(81)90038-8
    8 https://doi.org/10.1137/0135034
    9 schema:datePublished 1988-12
    10 schema:datePublishedReg 1988-12-01
    11 schema:description We show that almost all binary strings of length n contain all blocks of size (1-ε)log2n a close to uniform number of times. From this, we derive tight bounds on the discrepancy of random infinite strings. Our results are obtained through explicit generating function expressions and contour integration estimates.
    12 schema:genre research_article
    13 schema:inLanguage en
    14 schema:isAccessibleForFree false
    15 schema:isPartOf N7f7ccc6b92114bbf8b25cc026e883ef8
    16 Nfdadb38b8213417e84e9508e9de1ce04
    17 sg:journal.1053886
    18 schema:name Deviations from uniformity in random strings
    19 schema:pagination 139-150
    20 schema:productId N19f521a0bb9e49b5a82deedc875b486e
    21 N27335888ab2f48f2a37ea1a56ba6a84f
    22 Nf04eea7fedad4683b2273250bf18b558
    23 schema:sameAs https://app.dimensions.ai/details/publication/pub.1044597458
    24 https://doi.org/10.1007/bf00348756
    25 schema:sdDatePublished 2019-04-15T08:54
    26 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    27 schema:sdPublisher N4b7b4a6f6d3849baacd889bd272cc5fd
    28 schema:url http://link.springer.com/10.1007/BF00348756
    29 sgo:license sg:explorer/license/
    30 sgo:sdDataset articles
    31 rdf:type schema:ScholarlyArticle
    32 N19f521a0bb9e49b5a82deedc875b486e schema:name readcube_id
    33 schema:value d46f33f2571e8e8c86bbcb43bb83cdf07c13a5cfd6f33d704e9e7fdc8740383b
    34 rdf:type schema:PropertyValue
    35 N27335888ab2f48f2a37ea1a56ba6a84f schema:name dimensions_id
    36 schema:value pub.1044597458
    37 rdf:type schema:PropertyValue
    38 N30b84c77a476417b9e7d0ae9cc1727bb rdf:first sg:person.014144322056.01
    39 rdf:rest Ndae866b17760477983765030bb5b2d59
    40 N4b7b4a6f6d3849baacd889bd272cc5fd schema:name Springer Nature - SN SciGraph project
    41 rdf:type schema:Organization
    42 N7f7ccc6b92114bbf8b25cc026e883ef8 schema:issueNumber 1
    43 rdf:type schema:PublicationIssue
    44 N9d1d94a538404a418316f09e2ff02574 rdf:first sg:person.013431037475.89
    45 rdf:rest N30b84c77a476417b9e7d0ae9cc1727bb
    46 Ndae866b17760477983765030bb5b2d59 rdf:first sg:person.015312676677.43
    47 rdf:rest rdf:nil
    48 Nf04eea7fedad4683b2273250bf18b558 schema:name doi
    49 schema:value 10.1007/bf00348756
    50 rdf:type schema:PropertyValue
    51 Nfdadb38b8213417e84e9508e9de1ce04 schema:volumeNumber 80
    52 rdf:type schema:PublicationVolume
    53 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
    54 schema:name Mathematical Sciences
    55 rdf:type schema:DefinedTerm
    56 anzsrc-for:0104 schema:inDefinedTermSet anzsrc-for:
    57 schema:name Statistics
    58 rdf:type schema:DefinedTerm
    59 sg:journal.1053886 schema:issn 0178-8051
    60 1432-2064
    61 schema:name Probability Theory and Related Fields
    62 rdf:type schema:Periodical
    63 sg:person.013431037475.89 schema:affiliation https://www.grid.ac/institutes/grid.5328.c
    64 schema:familyName Flajolet
    65 schema:givenName P.
    66 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013431037475.89
    67 rdf:type schema:Person
    68 sg:person.014144322056.01 schema:affiliation https://www.grid.ac/institutes/grid.5329.d
    69 schema:familyName Kirschenhofer
    70 schema:givenName P.
    71 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014144322056.01
    72 rdf:type schema:Person
    73 sg:person.015312676677.43 schema:affiliation https://www.grid.ac/institutes/grid.5329.d
    74 schema:familyName Tichy
    75 schema:givenName R. F.
    76 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015312676677.43
    77 rdf:type schema:Person
    78 sg:pub.10.1007/978-3-642-82456-2_14 schema:sameAs https://app.dimensions.ai/details/publication/pub.1042555787
    79 https://doi.org/10.1007/978-3-642-82456-2_14
    80 rdf:type schema:CreativeWork
    81 sg:pub.10.1007/bf01171708 schema:sameAs https://app.dimensions.ai/details/publication/pub.1037754142
    82 https://doi.org/10.1007/bf01171708
    83 rdf:type schema:CreativeWork
    84 https://doi.org/10.1016/0097-3165(81)90005-4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1022924510
    85 rdf:type schema:CreativeWork
    86 https://doi.org/10.1016/0097-3165(81)90038-8 schema:sameAs https://app.dimensions.ai/details/publication/pub.1001383778
    87 rdf:type schema:CreativeWork
    88 https://doi.org/10.1137/0135034 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062839762
    89 rdf:type schema:CreativeWork
    90 https://www.grid.ac/institutes/grid.5328.c schema:alternateName French Institute for Research in Computer Science and Automation
    91 schema:name INRIA, Rocquencourt, F-78150, Le Chesnay, France
    92 rdf:type schema:Organization
    93 https://www.grid.ac/institutes/grid.5329.d schema:alternateName TU Wien
    94 schema:name Technische Universität Wien, Wiedner Hauptstraße 8-10, A-1040, Vienna, Austria
    95 rdf:type schema:Organization
     




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


    ...