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 \(\tfrac{c}{{\sqrt n }}\), for a real positive number c. For every first order sentence Ø, we show that the limit probability function:
(where U n, \(\tfrac{c}{{\sqrt 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.
Preview
Unable to display preview. Download preview PDF.
References
N. Alon, J. Spencer, & P. Erdős. The Probabilistic Method. Wiley and Sons, 1992.
P. Dolan. A zero-one law for a random subset. Random Structures & Algorithms, 2:317–326, 1991.
H. Ebbinghaus & J. Flum. Finite Model Theory. Springer, Berlin, 1995.
R. Fagin. Generalized first-order spectra and polynomial-time recognizable sets. In Complexity of Computation, SIAM-AMS Proceedings, pages 43–73, 1974.
E. Graedel. Subclasses of Presburger arithmetic and the polynomial-time hierarchy. Theoretical Computer Science, 56:289–301, 1988.
N. Immerman. Expressibility as a complexity measure: results and directions. In Second Structure in Complexity Conference, pages 194–202. Springer, 1987.
H. Lewis & C. Papadimitriou. Elements of the theory of computation. Prentice-Hall, 1981.
J. Lynch. On sets of relations definable by addition. J. Sym. Logic, 47:659–668.
J. Lynch. Probabilities of sentences about very sparse random graphs. Random Structures & Algorithms, 3:33–54, 1992.
S. Shelah & J. Spencer. Can you feel the double jump. Random Structures & Algorithms, 5(1):191–204, 1994.
S. Shelah & J. Spencer. Random sparse unary predicates. Random Structures & Algorithms, 5(3):375–394, 1994.
J. Spencer & K. St. John. Random unary predicates: Almost sure theories and countable models. Submitted for publication, 1997.
J. Spencer & L. Thoma. On the limit values of probabilities for the first order properties of graphs. Technical Report 97-35, DIMACS, 1997.
K. St. John. Limit probabilities for random sparse bit strings. Electronic Journal of Combinatorics, 4(1):R23, 1997.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1998 Springer-Verlag
About this paper
Cite this paper
Spencer, J.H., St. John, K. (1998). Random sparse bit strings at the threshold of adjacency. In: Morvan, M., Meinel, C., Krob, D. (eds) STACS 98. STACS 1998. Lecture Notes in Computer Science, vol 1373. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0028552
Download citation
DOI: https://doi.org/10.1007/BFb0028552
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-64230-5
Online ISBN: 978-3-540-69705-3
eBook Packages: Springer Book Archive