TY - GEN
T1 - Random sparse bit strings at the threshold of adjacency
AU - Spencer, Joel H.
AU - St. John, Katherine
PY - 1998
Y1 - 1998
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=78649823425&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=78649823425&partnerID=8YFLogxK
U2 - 10.1007/BFb0028552
DO - 10.1007/BFb0028552
M3 - Conference contribution
AN - SCOPUS:78649823425
SN - 3540642307
SN - 9783540642305
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 94
EP - 104
BT - STACS 98 - 15th Annual Symposium on Theoretical Aspects of Computer Science, Proceedings
T2 - 15th Annual Symposium on Theoretical Aspects of Computer Science, STACS 98
Y2 - 25 February 1998 through 27 February 1998
ER -