Random sparse bit strings at the threshold of adjacency

Joel H. Spencer, Katherine St. John

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We give a complete characterization for the limit probabilities of first order sentences over sparse random bit strings at the threshold of adjacency. For strings of length n, we let the probability that a bit is "on" be c/√n, for a real positive number c. For every first order sentence φ, we show that the limit probability function: fφ(c) = lim n→∞ Pr[Un, c/√n has the property φ] (where Un, c/√n is the random bit string of length n) is infinitely differentiable. Our methodology for showing this is in itself interesting. We begin with finite models, go to the infinite (via the almost sure theories) and then characterize fφ(c) as an infinite sum of products of polynomials and exponentials. We further show that if a sentence φ has limiting probability 1 for some c, then φ has limiting probability identically 1 for every c. This gives the surprising result that the almost sure theories are identical for every c.

Original languageEnglish (US)
Title of host publicationSTACS 98 - 15th Annual Symposium on Theoretical Aspects of Computer Science, Proceedings
Pages94-104
Number of pages11
DOIs
StatePublished - 1998
Event15th Annual Symposium on Theoretical Aspects of Computer Science, STACS 98 - Paris, France
Duration: Feb 25 1998Feb 27 1998

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume1373 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other15th Annual Symposium on Theoretical Aspects of Computer Science, STACS 98
Country/TerritoryFrance
CityParis
Period2/25/982/27/98

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint

Dive into the research topics of 'Random sparse bit strings at the threshold of adjacency'. Together they form a unique fingerprint.

Cite this